Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Hypercube (graphe)
Résumé
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.
Source officielle
À 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.