Accueil🇫🇷Chercher

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[1].

Graphe de Hamming
Image illustrative de l’article Graphe de Hamming

Notation
Nombre de sommets
Nombre d'arêtes
Distribution des degrés -régulier
Diamètre
Utilisation Code correcteur
Parallélisation

Construction

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 :

Propriétés

Fondamentales

  • 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[2].
  • 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 .

Graphe de Cayley

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[3].

Symétrie

Le graphe de Hamming est symétrique. Cela signifie que son groupe d'automorphismes agit transitivement sur l'ensemble de ses sommets et sur l'ensemble de ses arêtes. En d'autres termes, tous les sommets et toutes les arêtes d'un graphe de Hamming jouent exactement le même rôle d'un point de vue d'isomorphisme de graphe.

La symétrie se démontre en deux points : l'arête-transitivité et la sommet-transitivité. La sommet-transitivité découle directement du fait que le graphe de Hamming est un graphe de Cayley. Par construction, tous les graphes de Cayley sont sommet-transitifs[4].

Une démonstration alternative s'appuie sur le fait que le graphe de Hamming est un produit cartésien de graphes complets, donc de graphes sommets-transitifs. Un théorème statue que le produit de deux graphes sommets-transitifs est sommet-transitif[5].

L'arête-transitivité peut se démontrer en constatant que le graphe de Hamming est un G-graphe[6].

Références

  1. (en) Andries E. Brouwer - Brouwer home page Hamming Graphs].
  2. (en) Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "Hamming Graphs." §9.2 in Distance-Regular Graphs. New York: Springer-Verlag, pp. 261-267, 1989.
  3. (en) Cai Heng Li - on-line Cayley graph in Encyclopaedia of Mathematics, Springer, (ISBN 1402006098).
  4. (en) Pegg, Ed Jr.; Rowland, Todd; and Weisstein, Eric W - Cayley Graph, wolfram.com.
  5. (en) Wilfried Imrich & Sandi Klavžar, Product Graphs: Structure and Recognition. Wiley, 2000, (ISBN 0-471-37039-8)
  6. (en) Alain Bretto, Cerasela Jaulin, Luc Gillibert, Bernard Laget: "A New Property of Hamming Graphs and Mesh of d-ary Trees". ASCM 2007: 139-150
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.