Hypercube (graphe)
De Wikipedia, l'encyclopédie encyclopedia
Vous lisez un « bon article » labellisé en 2009.
Pour les articles homonymes, voir Hypercube (homonymie).
Cette page se comprend mieux après la lecture de Théorie des graphes.
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.
Hypercube | |
Q4 | |
Notation | Qn ou Hn |
---|---|
Nombre de sommets | 2n |
Nombre d'arêtes | 2n-1n |
Distribution des degrés | n-régulier |
Diamètre | n |
Maille | 4 |
Coefficient de clustering | 0 |
Automorphismes | 2nn! |
Nombre chromatique | 2 |
Propriétés | Hamiltonien Distance-unité Graphe de Cayley Symétrique Distance-régulier |
Utilisation | Machines parallèles |
modifier |