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. 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. 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ésien 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.
