Graphe de Hamming

Les graphes de Hamming forment une famille de graphes. Le graphe de Hamming de dimension d sur un alphabet de taille q est défini de la manière suivante : est le graphe dont les sommets sont , l'ensemble des mots de longueur sur un alphabet , où . Deux sommets sont adjacents dans s'ils sont à une distance de Hamming de 1, c'est-à-dire si leurs étiquettes ne diffèrent que d'un symbole. On peut construire le graphe de Hamming directement en appliquant sa définition : disposons sommets, chacun avec une étiquette . Deux sommets sont reliés par une arête si leurs étiquettes différent exactement d'un symbole, soit formellement pour le graphe : On peut aussi définir comme le produit cartésien de graphes complets , soit : Degré. Deux sommets sont connectés s'ils diffèrent exactement sur un symbole de leurs étiquettes. Comme chaque étiquette a d symboles, chaque sommet est connecté à exactement d(q-1) voisins : tout sommet a donc degré d(q-1), autrement dit le graphe est d(q-1)-régulier. Nombre de sommets. Les sommets de sont étiquetés par l'ensemble des mots de longueur sur un alphabet de cardinalité . L'ordre de est donc égal à . Diamètre. Le diamètre du graphe de Hamming est égal à d. En effet, une des propriétés du produit cartésien est que le diamètre de est égal à . Comme est le produit cartésien de graphes complets , son diamètre est égal à . Distance régulier. Le graphe de Hamming est un graphe distance-régulier. Eulérien. Un graphe a un chemin eulérien si et seulement si tout sommet est de degré pair. Comme est d(q-1)-régulier, il en résulte qu'il n'y a un chemin eulérien que pour d(q-1) pair. Cas particuliers : Graphe complet. Par construction, est le graphe complet . Graphe trivial. Quel que soit d, est le graphe trivial à un sommet. Hypercube. L'hypercube est isomorphe par construction avec le graphe de Hamming . Le graphe de Hamming est un graphe de Cayley Cay(G, S) avec : C'est un des exemples de référence en théorie algébrique des graphes. Le graphe de Hamming est symétrique.