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. L'hypercube est couramment introduit pour illustrer des algorithmes parallèles, et de nombreuses variantes ont été proposées, soit pour des cas pratiques liés à la construction de machines parallèles, soit comme objets théoriques.
Construction L'hypercube consiste en deux sommets d'étiquettes et ; les étiquettes de ces sommets étant différentes par un seul symbole, ils sont donc reliés. Pour passer à la dimension supérieure, on fabrique une copie du graphe : à la partie d'origine, on rajoute le symbole , et sur la partie copiée le symbole ; chaque sommet de la partie d'origine est ensuite relié à son équivalent dans la copie. Ainsi, consiste en quatre sommets étiquetés , , et . L'illustration ci-dessous montre en rouge les arêtes connectant les sommets d'origine à leurs équivalents dans la copie, et l'exemple se poursuit jusqu'à et . Cette méthode de construction est récursive, puisque pour construire on se fonde sur .
Fichier:Hypercube-dim1.PNG → Fichier:Hypercube-dim2.PNG → Fichier:Hypercube-dim3.PNG → Fichier:Hypercube-dim4.PNG
On peut aussi définir comme le produit cartésienJ-C. Bermond, P. Fraigniaud, A. Germa, M-C. Heydemann, E. Lazard, P. Michallon, A. Raspaud, D. Sotteau, M. Syska et D. Trystram - Communications dans les réseaux de processeurs, Masson, 1994, . Paru sous le pseudonyme Jean de Rumeur. de graphes complets , soit :
Enfin, on peut construire le graphe directement en appliquant sa définition. On dispose sommets, et chacun a une étiquette unique dans l'espace vectoriel. , c'est-à-dire une étiquette de la forme . Deux sommets sont reliés par une arête s'ils diffèrent exactement sur un symbole de leurs étiquettes, soit formellement pour le graphe :
Le graphe hypercube est le graphe hexaédrique et est le graphe tesseract.
Propriétés Fondamentales vignette|Un cycle dans un hypercube constitué de deux hypercubes . En rouge, un chemin dans le premier hypercube , en bleu les arêtes le reliant à sa copie et en vert le chemin dans la copie. Le cycle est de longueur 2 + 2 + 2 = 6, qui est pair. Degré. Deux sommets sont connectés s'ils diffèrent exactement sur un symbole de leurs étiquettes. Comme l'étiquette a symboles, chaque sommet est connecté à exactement voisins : tout sommet a donc degré , autrement dit le graphe est -régulier. Nombre de sommets. Par la construction récursive, on voit que pour passer de à , il faut faire une copie du graphe, autrement dit le nombre de sommets est doublé. Si est le nombre de sommets du graphe , on obtient ainsi , et le premier cas est ; en déroulant la récurrence, on obtient , c'est-à-dire que le graphe a sommets. Diamètre. 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 à . vignette|Les sommets de l'hypercube sont répartis en deux ensembles. Ceux en vert ont un nombre impair de 1 et ceux en rouge un nombre pair. Le voisin d'un sommet est nécessairement de couleur différente, donc le graphe est biparti. Cycles. Par construction, le plus petit cycle correspond à , qui est isomorphe au cycle (i.e. le cycle de longueur 4). Le graphe est formé par deux graphes : si l'on souhaite un cycle de longueur supérieur à 4 dans , alors on choisit arêtes dans un des deux graphes , arêtes dans l'autre et 2 arêtes supplémentaires pour naviguer entre les deux graphes, ce qui porte le total d'arêtes à ; ce mécanisme est illustré dans la figure ci-contre avec un cycle de longueur 6, et permet de prouver que les cycles dans un hypercube sont toujours de longueur paire. Nombre chromatique. Un graphe est biparti si et seulement s'il ne contient pas de cycle impair, et il découle donc de la propriété précédente que l'hypercube est biparti. Un graphe biparti est celui pouvant être colorié avec deux couleurs, et ainsi le nombre chromatique de l'hypercube est . Pour voir qu'un graphe est biparti, il suffit de trouver un schéma afin de ranger chaque sommet dans un ensemble ou , de façon telle que tout sommet d'un ensemble ait comme voisins uniquement des sommets de l'autre ensemble. Dans le cas de l'hypercube, l'ensemble peut être constitué des sommets dont l'étiquette a un nombre pair de 1, et est l'ensemble de sommets dont l'étiquette a un nombre impair de 1. Un sommet étant connecté à tous ceux dont l'étiquette diffère exactement d'un symbole, il en découle que le nombre de 1 des voisins d'un sommet est soit supérieur soit inférieur : ainsi, un sommet pair sera connecté à des sommets impairs, et vice-versa. Planaire. L'hypercube est planaire (c'est-à-dire pouvant se dessiner sur un plan sans croiser deux arêtes) uniquement pour . Pour , plusieurs arêtes vont se croiser mais déterminer le nombre minimum d'arêtes qui vont se croiser est un problème NP-complet ; on sait par exemple qu'il y en a 8 pour . Eulérien. Un graphe a un chemin eulérien si et seulement si tout sommet est de degré pair. Comme est -régulier, il en résulte qu'il n'y a un chemin eulérien que pour pair. Hamiltonien. étant un cycle, il est aussi un circuit hamiltonien. Pour construire un circuit hamiltonien dans , on sait qu'il y a un circuit hamiltonien dans le graphe d'origine et dans sa copie : supprimons une arête dans chacun de ces circuits et raccordons les sommets ainsi libérés pour créer un circuit hamiltonien dans l'ensemble. Ce processus est illustré ci-dessous pour et . Le nombre exact de cycles hamiltoniens est donné ci-dessous pour les premiers hypercubes ; au-delà, l'estimation la plus précise quant au nombre de circuits hamiltoniens dans est donnée. par : . 200px 280px + Nombre de cycles hamiltoniens dans l'hypercube n Sans compter les cycles isomorphes En comptant tous les cycles2113164913445275 065906 545 760 Graphe de Hamming. Un graphe de Hamming est le graphe obtenu par produit cartésien de graphes complets . L'hypercube étant obtenu par produit cartésien de copies de , il découle de la définition que tout hypercube est isomorphe à . Une définition alternative d'un graphe de Hamming montre le rapport direct avec celle utilisée pour introduire l'hypercube : 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. Distance-régulier. Un hypercube est un graphe distance-régulierRafaï Mourad Madani - Généralisations d'hypercubes et de (0,2)-graphes, Thèse de doctorat, Université Joseph Fournier - Grenoble 1, 1992, sous la direction de Jean-Marie Laborde. et son vecteur d'intersection est . Diagramme de Hasse. L'hypercube est isomorphe au diagramme de Hasse d'une algèbre de Boole à n éléments. Reconnaissance. Étant donné une liste d'adjacence, on peut savoir en temps et espace linéaire si le graphe qu'elle représente est un hypercube Wilfriend Imrich et Sandi Klavzar - Product Graphs: Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, 2000, .. Code de Gray Miltos D. Grammatikakis, D. Frank Hsu et Miro Kraetzl - Parallel system interconnections and communications, CRC Press, chapitre 4 : « Hypercube Networks », 2001, .. Les étiquettes ordonnées des sommets dans un cycle hamiltonien sur définissent le code de Gray sur bits. De plus, ce code suit une construction similaire à celle de l'hypercube : les mots de bits sont déterminés en copiant les mots de puis en rajoutant 0 devant l'original, 1 devant la copie, et en inversant les mots de la copie. Distance-unité. L'hypercube est un graphe distance-unité : il peut s'obtenir à partir d'une collection de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1.
Aspects algébriques Groupe d'automorphisme Le groupe d'automorphisme de l'hypercube est d'ordre . Il est isomorphe au produit en couronne des groupes symétriques et : .. Le produit en couronne de A par B étant défini comme le produit semi-direct où est l'ensemble des fonctions de B dans A et où B agit sur par décalage d'indice : pour et .
L'hypercube est un graphe arc-transitif : son groupe d'automorphisme agit transitivement sur l'ensemble de ses arcs. Étant donné deux arêtes e1 = u1v1 et e2 = u2v2 de G, il existe deux automorphismes et tels que , , et , , , .
L'hypercube est donc a fortiori symétrique. Le groupe agit donc également 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 hypercube jouent exactement le même rôle d'un point de vue d'isomorphisme de graphe.
Le graphe hexaédrique () est l'unique graphe cubique symétrique à 8 sommets.. Le graphe tesseract () est l'unique graphe symétrique régulier de degrés 4 à 16 sommets.
Graphe de Cayley L'hypercube est un graphe de Cayley Cay(G, S) avec :
Cela découle d'une propriété plus générale statuant que tous les graphes de Hamming sont des graphes de Cayley Cai Heng Li - Cayley graph in Encyclopaedia of Mathematics, Springer, . on-line.
Matrice d'adjacence et spectre La matrice d'adjacence de l'hypercube est définie ci-dessous. Par la définition récursive de l'hypercube, pour passer à la dimension supérieure , on duplique et connecte les sommets d'origine à leur équivalent dans la copie. 0 1001110 On obtient ainsi la matrice d'adjacence ci-dessous : 00 01 10 11000110011001101001110110 Au niveau de la matrice, l'opération passant de à se comprend comme suit : les entrées correspondent à la matrice d'origine, et se trouvent dupliquées en . Dans les autres entrées, on connecte chaque sommet à sa copie. Ainsi, la forme générale de la matrice est donnée de la façon suivante., où représente la matrice identité de dimension :
Pour comprendre l'évolution du spectre de la matrice en fonction de , il faut revenir à la définition comme produit cartésien. Le spectre d'un produit cartésien est , où est le spectre de et le spectre de ; autrement dit, le spectre est la somme de toutes les paires possibles Dragos M. Cvetkovic et Michael Doob et Horst Sachs - Spectra of Graphs, Heidelberg, Leipzig, 1994, .. Sachant que le spectre de est , on en déduit que le spectre de est : en effet, elles correspondent aux combinaisons , , . Si l'on passe au stade suivant, soit , on a d'un côté le spectre de , et de l'autre de : le résultat du produit cartésien est .
On en déduit par récurrence la formule suivante pour le polynôme caractéristique de la matrice d'adjacence (et donc du graphe): . Ce polynôme caractéristique n'admet que des racines entières. Le graphe d'un hypercube est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.
Chemins et sous-graphes Navigation Pour aller d'un sommet à un autre, on utilise à nouveau le fait que deux sommets sont connectés s'ils diffèrent exactement sur un symbole de leurs étiquettes. Ainsi, un chemin est trouvé en faisant correspondre une à une les coordonnées du sommet de destination avec celui d'origine. Par exemple, pour aller de à , on obtient . Dans le cas général, pour aller de à on obtient :