Graphe de Hamming

On peut construire le graphe de Hamming directement en appliquant sa définition : disposons ${\displaystyle q^{d}}$ sommets, chacun avec une étiquette ${\displaystyle (x_{1},x_{2},...,x_{d}),x_{i}\in \{0,1,2,...,q-1\}}$. Deux sommets sont reliés par une arête si leurs étiquettes différent exactement d'un symbole, soit formellement pour le graphe ${\displaystyle G=(V,E)}$ :

${\displaystyle \exists e_{uv}\in E\Leftrightarrow u=\{x_{1},...,x_{i-1},x_{i},x_{i+1},...,x_{d}\},v=\{x_{1},...,x_{i-1},x'_{i},x_{i+1},...,x_{d}\},x_{i}\neq x'_{i}}$

On peut aussi définir ${\displaystyle H(d,q)}$ comme le produit cartésien de ${\displaystyle d}$ graphes complets ${\displaystyle K_{q}}$, soit :

${\displaystyle H(d,q)=H(d-1,q)\square K_{q}=H(d-2,q)\square K_{q}\square K_{q}=...=\underbrace {K_{q}\square K_{q}\square ...\square K_{q}} _{d{\text{ fois}}}}$

• 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 ${\displaystyle H(d,q)}$ sont étiquetés par l'ensemble des mots de longueur ${\displaystyle d}$ sur un alphabet de cardinalité ${\displaystyle q}$. L'ordre de ${\displaystyle H(d,q)}$ est donc égal à ${\displaystyle q^{d}}$.
• Diamètre. Le diamètre du graphe de Hamming ${\displaystyle H(d,q)}$ est égal à d. En effet, une des propriétés du produit cartésien est que le diamètre ${\displaystyle D(C)}$ de ${\displaystyle C=A\square B}$ est égal à ${\displaystyle D(A)+D(B)}$. Comme ${\displaystyle H(d,q)}$ est le produit cartésien de ${\displaystyle d}$ graphes complets ${\displaystyle K_{q}}$, son diamètre est égal à ${\displaystyle d\times D(K_{q})=d\times 1=d}$.
• 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 ${\displaystyle H(d,q)}$ 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, ${\displaystyle H(1,q)}$ est le graphe complet ${\displaystyle K_{q}}$.
  • Graphe trivial. Quel que soit d, ${\displaystyle H(d,1)}$ est le graphe trivial à un sommet.
  • Hypercube. L'hypercube ${\displaystyle Q_{d}}$ est isomorphe par construction avec le graphe de Hamming ${\displaystyle H(d,2)}$.

Le graphe de Hamming ${\displaystyle H(d,q)}$ est un graphe de Cayley Cay(G, S) avec :

${\displaystyle G=\underbrace {{\frac {\mathbb {Z} }{q\mathbb {Z} }}\times {\frac {\mathbb {Z} }{q\mathbb {Z} }}\times ...\times {\frac {\mathbb {Z} }{q\mathbb {Z} }}} _{d{\text{ fois}}}}$ ${\displaystyle S=\{(i,0,0,...,0),(0,i,0,...,0),...,(0,0,...,i,0),(0,0,...,0,i)|1\leq i\leq q-1\}}$

C'est un des exemples de référence en théorie algébrique des graphes^[3].

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

• Portail des mathématiques
• Portail de l'informatique théorique