Graphe de Hamming

Pour les articles homonymes, voir Hamming.

Graphe de Hamming
${\displaystyle H(4,2)}$
Notation	${\displaystyle H(d,q)}$
Nombre de sommets	${\displaystyle q^{d}}$
Nombre d'arêtes	${\displaystyle {\frac {d(q-1)q^{d}}{2}}}$
Distribution des degrés	${\displaystyle d(q-1)}$-régulier
Diamètre	${\displaystyle d}$
Utilisation	Code correcteur Parallélisation
modifier

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 : ${\displaystyle H(d,q)}$ est le graphe dont les sommets sont ${\displaystyle S^{d}}$, l'ensemble des mots de longueur ${\displaystyle d}$ sur un alphabet ${\displaystyle S}$, où ${\displaystyle |S|=q}$. Deux sommets sont adjacents dans ${\displaystyle H(d,q)}$ s'ils sont à une distance de Hamming de 1, c'est-à-dire si leurs étiquettes ne diffèrent que d'un symbole^[1].

Construction

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}}}}$

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 ${\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)}$.

Aspects algébriques

Graphe de Cayley

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

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

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