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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (4)

Hypercube (graphe)

Les hypercubes, ou n-cubes, forment une famille de graphes. Dans un hypercube , chaque sommet porte une étiquette de longueur sur un alphabet , et deux sommets sont adjacents si leurs étiquettes ne diffèrent que d'un symbole. C'est le graphe squelette de l'hypercube, un polytope n-dimensionnel, généralisant la notion de carré (n = 2) et de cube (n = 3). Dans les années 1980, des ordinateurs furent réalisés avec plusieurs processeurs connectés selon un hypercube : chaque processeur traite une partie des données et ainsi les données sont traitées par plusieurs processeurs à la fois, ce qui constitue un calcul parallèle.

Graphe de Hamming

Produit cartésien (graphe)

Le produit cartésien, ou somme cartésienne, est une opération sur deux graphes et résultant en un graphe . Parler de produit ou de somme pour cette opération n'est pas une contradiction, mais une explication basée sur deux aspects différents : la construction peut se voir comme un produit, tandis que de nombreuses propriétés sont basées sur la somme. Soient deux graphes et . Le produit cartésien est défini comme suit : Autrement dit, l'ensemble résultant des sommets est le produit cartésien .