Hypercube (graphe) - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Galerie

Variantes

L'hypercube (En géométrie, un hypercube est un analogue n-dimensionnel d'un carré (n = 2) et d'un cube (n = 3). C'est une figure fermée, compacte, convexe constituée de groupes de segments parallèles opposés aligné dans chacune des dimensions de...) était très utilisé pour les architectures (Architectures est une série documentaire proposée par Frédéric Campain et Richard Copans, diffusé sur Arte depuis 1995.) de machines parallèles, et certaines de ses propriétés étaient jugées perfectibles dans ce cadre. Le principal problème est la croissance d'un hypercube, où le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de sommets doit doubler d'une dimension (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien son diamètre si c'est une pièce de...) à l'autre : dans une machine, plus de flexibilité est désirable afin de pouvoir ajouter quelques processeurs. Plusieurs aspects sont aussi liés à sa réalisation par des circuits électroniques. Premièrement, l'hypercube n'est pas planaire (Les planaires sont des vers plats libres nageurs ou rampants. Des espèces vivent en mer, d'autres en eau douce, jusque dans les sols très...) et aura donc des chevauchements dans le circuit : en réduire le nombre simplifie le circuit. Deuxièmement, l'hypercube est défini comme un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) non-orienté, mais « un réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des informations. Par analogie avec un filet (un réseau est un « petit rets », c'est-à-dire un petit filet), on appelle nœud...) basé sur une orientation (Au sens littéral, l'orientation désigne ou matérialise la direction de l'Orient (lever du soleil à l'équinoxe) et des points cardinaux (nord de la boussole) ;) \vec{G} de G utilise la moitié du nombre de broches et câbles par rapport à G » : il est donc intéressant de trouver une orientation conservant des performances similaires. Enfin, il peut être désirable de réduire les distances dans l'hypercube pour les performances en termes de communications.

L'hypercube comme bloc de base

HCN(2,2) formé de 22 = 4 hypercubes Q2, chacun constituant un cluster dont le numéro est encadré.

Un hierarchical cubic network HCNn,n est formé de 2n n-cubes, où chaque cube (En géométrie euclidienne, un cube est un prisme dont toutes les faces sont carrées. Les cubes figurent parmi les solides les plus...) est désigné comme un cluster. Chacun de ces clusters est utilisé comme un bloc de base, et chaque nœud d'un cluster a un lien supplémentaire le reliant à un autre cluster ; ces liens sont déterminés par l'algorithme suivante pour le graphe G = (V,E) composé de 2n n-cubes, où (I,J) désigne le sommet J du cluster I et \bar{i} est le complément bit à bit de i :

\begin{array}{crl} \rm \text{pour } i = 0..2^n-1 & \rm & \rm \\ & \text{pour } j = 0..2^n-1 & \\ & & \text{si } i \neq j, E(G) \leftarrow E(G) \uplus \{e_{ij},e_{ji}\} \\ & & \text{sinon}, E(G) \leftarrow E(G) \uplus \{e_{i \bar{i} }, e_{j \bar{j} }\} \end{array}

Les auteurs montrèrent que, à tailles égales, ce graphe a un diamètre (Dans un cercle ou une sphère, le diamètre est un segment de droite passant par le centre et limité par les points du cercle ou de la sphère. Le diamètre est aussi la longueur de ce segment. Pour indiquer qu'une valeur...) d'un quart plus faible que celui de l'hypercube, et la moitié du nombre de liens. Cependant, dans certaines situations la diffusion (Dans le langage courant, le terme diffusion fait référence à une notion de « distribution », de « mise à disposition » (diffusion d'un produit, d'une information), voire de...) est plus lente (La Lente est une rivière de la Toscane.) que sur un hypercube, et avoir un graphe moins dense revient à être plus exposé lorsque des pannes surviennent sur les liens.

Cubes de Fibonacci (Leonardo Fibonacci (Pise, v. 1170 - v. 1250) est un mathématicien italien. Fibonacci (de son nom moderne), connu à l'époque sous le nom de Leonardo Pisano (Léonard de Pise), mais aussi...)

Une autre variante ayant été depuis particulièrement étudiée est le Cube de Fibonacci. Les conditions fondamentales du cube de Fibonacci de dimension n, noté FCn, sont les mêmes que celles de l'hypercube : chaque sommet porte une étiquette de longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou en forme de lacet,...) n sur un alphabet A = {0,1}, et deux sommets sont adjacents si leurs étiquettes ne différent que d'un symbole. Cependant, on rajoute une contrainte : une étiquette valide ne peut avoir deux 1 consécutif. Ainsi, ci-dessous, on voit que les cubes de Fibonacci FC1,FC2,FC3,FC4 peuvent se retrouver comme sous-graphes des hypercubes Q1,Q2,Q3,Q4 en éliminant les étiquettes contenant deux 1 consécutifs.

Les cubes de Fibonacci FC1,FC2,FC3,FC4 comme sous-graphes des hypercubes Q1,Q2,Q3,Q4.

La construction par récurrence peut-être définie par une grammaire formelle en énonçant les étiquettes valides pour les sommets, puis en considérant le graphe FCn comme le sous-graphe de l'hypercube Qn induit (L'induit est un organe généralement électromagnétique utilisé en électrotechnique chargé de recevoir l'induction de l'inducteur et de la transformer en électricité (générateur) ou en force...) par les sommets valides V(FCn) :

\begin{cases} V_0 = \epsilon \\ V_1 = \{0,1\} \\ V_i = \{0 \alpha | \alpha \in V_{i-1}\} \cup \{10 \alpha | \alpha \in V_{i-2}\}, \forall i > 2 \end{cases}

Hypercubes recâblés

Dans le cas où réduire la distance soit le principal objectif, il est courant d'utiliser des procédures de recâblage comme on le voit encore dans le cas de l'effet petit monde (Le mot monde peut désigner :). De nombreuses procédures ont été proposées, et les plus significatives sont résumées dans le tableau (Tableau peut avoir plusieurs sens suivant le contexte employé :) ci-dessous avec leurs performances sur la distance maximale (i.e. le diamètre) et moyenne (La moyenne est une mesure statistique caractérisant les éléments d'un ensemble de quantités : elle exprime la grandeur qu'auraient chacun des membres de l'ensemble s'ils...) ainsi que le nombre de recâblages nécessaire. Le nom de chacune des procédures est conservé à partir des articles d'origines, où twisted signifie recâblé, et suivi de l'année (Une année est une unité de temps exprimant la durée entre deux occurrences d'un évènement lié à la révolution de la Terre autour du Soleil.) à laquelle la procédure fut publiée.

Listes de variantes de l'hypercube par recâblage. Le temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) de routage (En informatique, le terme routage désigne le mécanisme par lequel les données d'un équipement expéditeur sont acheminées jusqu'à leur destinataire en examinant les informations situées...) est toujours en O(n).
Nom Diamètre Distance moyenne Nombre d'arêtes recâblées
Hypercube n \frac{n}{2} 0
Twisted cube (1987) \frac{n+1}{2} \approx \frac{3n}{8} (n − 1)2n − 4
Twisted hypercube (1991) n − 1 \approx \frac{n}{2} - \frac{1}{8} 2n − 1
Twisted N-cube (1991) n − 1 \approx \frac{n}{2} 2
Generalized twisted cube (1993) \frac{2n}{3} \approx \frac{11n}{24} n2^{\lfloor n/3 \rfloor}
0-Möbius Cube (1995) \frac{n+2}{2} \approx \frac{n}{3} (n − 2)2n − 1

Graphe libre d'échelle par contraction

L'hypercube Q2 a été contracté dans Q4 et deux coordonnées remplacées par « _ ».

Dans les années 2000, de nombreux modèles furent proposés pour prendre en compte des caractéristiques communes à de nombreux réseaux. Deux des principales caractéristiques sont l'effet petit monde et l'effet libre d'échelle. Il est possible de modifier un hypercube afin d'obtenir l'effet libre d'échelle, tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) en continuant à bénéficier de sa propriété de routage local. Pour cela, des sommets sont contractés à la condition qu'ils ne diffèrent que sur une coordonnée qui sera remplacé par un joker « _ ». Après une séquence de contractions, c'est-à-dire plusieurs contractions successives, il est toujours possible de trouver un chemin d'un sommet A à un sommet B en utilisant leurs coordonnés et en remplaçant les jokers « _ » par les coordonnées de B.

La condition de ne différer que sur une coordonnée tout en opérant une séquence de contractions conduit à ce qu'un sous-hypercube soit contracté, et le degré (Le mot degré a plusieurs significations, il est notamment employé dans les domaines suivants :) du sommet s résultant de la contraction d'un hypercube Qp dans Qn, 1 < p < n est :

d_{q_p}(s) = 2^{p}(n-p)

En résumé, l'effet libre d'échelle est obtenu par contraction de sous-hypercubes de grande taille et les algorithmes de navigation (La navigation est la science et l'ensemble des techniques qui permettent de :) n'ont pas besoin (Les besoins se situent au niveau de l'interaction entre l'individu et l'environnement. Il est souvent fait un classement des besoins humains en trois grandes catégories : les besoins primaires, les besoins secondaires et les besoins...) d'être modifiés.

Page générée en 0.675 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique