Hypercube (graphe) - Définition

Propriétés

Fondamentales

Un cycle dans un hypercube Q₃ constitué de deux hypercubes Q₂. En rouge, un chemin dans le premier hypercube Q₂, 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 n symboles, chaque sommet est connecté à exactement n voisins : tout sommet a donc degré n, autrement dit le graphe est n-régulier.
• Nombre de sommets. Par la construction récursive, on voit que pour passer de Q_{n − 1} à Q_n, il faut faire une copie du graphe, autrement dit le nombre de sommets est doublé. Si V_n est le nombre de sommets du graphe Q_n, on obtient ainsi V_n = 2 * V_{n − 1}, et le premier cas est V₁ = 2 ; en déroulant la récurrence, on obtient V_n = 2 * V_{n − 1} = 2² * V_{n − 2} = ... = 2ⁿ, c'est-à-dire que le graphe a 2ⁿ sommets.
• Diamètre. Une des propriétés du produit cartésien est que le diamètre D(C) de est égal à D(A) + D(B). Comme Q_n est le produit cartésien de n graphes complets K₂, son diamètre est égal à n * D(K₂) = n * 1 = n.

Les sommets de l'hypercube Q₄ sont répartis en deux ensemble. 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 à Q₂, qui est isomorphe au cycle C₄ (i.e. le cycle de longueur 4). Le graphe Q₃ est formé par deux graphes Q₂ : si l'on souhaite un cycle de longueur supérieur à 4 dans Q₃, alors on choisit p arêtes dans un des deux graphes Q₂, p arêtes dans l'autre Q₂ 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 si 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 χ(Q_n) = 2. Pour voir qu'un graphe est biparti, il suffit de trouver un schéma afin de ranger chaque sommet dans un ensemble G₁ ou G₂, 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 G₁ peut être constitué des sommets dont l'étiquette a un nombre pair de 1, et G₂ 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 n > 3, 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 Q₄.
• Eulérien. Un graphe a un chemin eulérien si et seulement si tout sommet est de degré pair. Comme Q_n est n-régulier, il en résulte qu'il n'y a un chemin eulérien que pour n pair.
• Hamiltonien. Q₂ étant un cycle, il est aussi un circuit hamiltonien. Pour construire un circuit hamiltonien dans Q₃, 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 Q₃ et Q₄. 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 k de circuits hamiltoniens dans Q_n est donnée par : .

• Graphe de Hamming. Un graphe de Hamming H(d,q) est le graphe obtenu par produit cartésien de d graphes complets K_q. L'hypercube Q_d étant obtenu par produit cartésien de d copies de K₂, il découle de la définition que tout hypercube Q_d est isomorphe à H(d,2). Une définition alternative d'un graphe de Hamming montre le rapport direct avec celle utilisée pour introduire l'hypercube : H(d,q) est le graphe dont les sommets sont S^d, l'ensemble des mots de longueur d sur un alphabet S, où | S | = q. Deux sommets sont adjacents dans H(d,q) 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égulier et son vecteur d'intersection est {n,n − 1,n − 2,...,1,1,2,3,...,n}.
• Diagramme de Hasse. L'hypercube Q_n 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.
• Code de Gray. Les étiquettes ordonnées des sommets dans un cycle hamiltonien sur Q_n définissent le code de Gray sur n bits. De plus, ce code suit une construction similaire à celle de l'hypercube : les mots de n bits sont déterminés en copiant les mots de n − 1 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 Γ(Q_d) de l'hypercube Q_d est d'ordre 2^dd!. Il est isomorphe au produit en couronne des groupes symétriques S₂ et S_d : . Le produit en couronne de A et B étant défini comme le produit semi-direct où A^B est l'ensemble des fonctions de A dans B et où A agit sur A^B par décalage d'indice :

(g.λ)(s) = λ(g ^{− 1}s) pour et .

L'hypercube Q_d est un graphe arc-transitif : son groupe d'automorphisme Γ(Q_d) agit transitivement sur l'ensemble de ses arcs. Étant donné deux arêtes e₁ = u₁v₁ et e₂ = u₂v₂ de G, il existe deux automorphismes et tels que f_E(e₁) = e₂, g_E(e₁) = e₂, et f_V(u₁) = u₂, f_V(v₁) = v₂, g_V(u₁) = v₂, g_V(v₁) = u₂.

L'hypercube Q_d est donc a fortiori symétrique. Le groupe Γ(Q_d) 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 (Q₃) est l'unique graphe cubique symétrique à 8 sommets. Le graphe tesseract (Q₄) est l'unique graphe symétrique régulier de degrés 4 à 16 sommets.

Graphe de Cayley

L'hypercube Q_d 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.

Matrice d'adjacence et spectre

La matrice d'adjacence A(Q₂) de l'hypercube Q₁ est définie ci-dessous. Par la définition récursive de l'hypercube, pour passer à la dimension supérieure Q₂, on duplique Q₁ et connecte les sommets d'origine à leur équivalent dans la copie.

On obtient ainsi la matrice d'adjacence A(Q₃) ci-dessous :

Au niveau de la matrice, l'opération passant de Q₁ à Q₂ se comprend comme suit : les entrées {A_{00 − 00},A_{00 − 01},A_{01 − 00},A_{01 − 01}} correspondent à la matrice d'origine, et se trouvent dupliquées en {A_{10 − 10},A_{10 − 11},A_{11 − 10},A_{11 − 11}}. 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 2ⁿ − 1 :

Pour comprendre l'évolution du spectre de la matrice en fonction de n, il faut revenir à la définition comme produit cartésien. Le spectre d'un produit cartésien est {α_i + β_j}, où {α_i} est le spectre de A et {β_j} le spectre de B ; autrement dit, le spectre est la somme de toutes les paires possibles. Sachant que le spectre de Q₁ = K₂ est { + 1, − 1}, on en déduit que le spectre de Q₂ est { + 2,0, − 2} : en effet, elles correspondent aux combinaisons 1 + 1 = 2, 1 − 1 = 0, − 1 − 1 = − 2. Si l'on passe au stade suivant, soit Q₃, on a d'un côté le spectre { + 2,0, − 2} de Q₂, et de l'autre { − 1, + 1} de K₂ : le résultat du produit cartésien est { + 3, + 1, − 1, − 3}.

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 0010 à 1011, on obtient . Dans le cas général, pour aller de (x₁,x₂,...,x_n) à (y₁,y₂,...,y_n) on obtient :

Notons deux choses. Premièrement, la longueur d'un chemin entre deux sommets est le nombre de symboles sur lesquels leurs étiquettes diffèrent : ainsi, si les étiquettes sont complètement différentes, le chemin sera de longueur n, ce qui est une autre explication quant au diamètre du graphe. Deuxièmement, le chemin choisi n'est pas unique : au lieu d'aller de 0010 en 1010, on aurait tout d'abord pu passer par 0011 avant d'aller en 1011. Le nombre de chemins différents pour aller entre deux sommets est un problème de combinatoire : considérons que les sommets diffèrent sur k symboles, combien de façons a-t-on de générer des chemins ? On a k choix pour le premier symbole à changer, puis k − 1 choix pour le second symbole à changer, jusqu'à un seul choix quand il n'y a plus qu'un symbole à changer ; ainsi, le nombre de chemins entre deux sommets différant sur k symboles est k!.

Hypercubes induits

Les chemins entre deux sommets ont d'autres propriétés intéressantes, particulièrement pour les sous-graphes qu'ils définissent. Ainsi, l'union des chemins entre deux sommets distants de k (i.e. différant de k symboles) donne l'hypercube Q_k. Ceci est illustré par l'exemple ci-dessous : dans le cas de deux sommets voisins u et v, il n'y a qu'un chemin et on obtient l'hypercube Q₁ ; dans le cas où ils sont à distance 2, il y a deux chemins entre eux qui définissent Q₂, et s'ils sont à distance 3 alors l'union des chemins représente l'ensemble de l'hypercube Q₃.

Le nombre α_d d'hypercubes Q_d compris dans Q_n est donné par la formule suivante :

L'hypercube est aussi un graphe médian, et en particulier le seul graphe médian régulier. On peut donc appliquer la formule suivante des graphes médians :

Spanners

Certains types de sous-graphe sont particulièrement utiles en termes de communications. Par exemple, un spanner est un sous-graphe couvrant, c'est-à-dire qui contient tous les sommets, mais qui contient moins d'arêtes. Contenir moins d'arêtes peut augmenter les distances entre des sommets du graphe, et l'on distingue ainsi les spanners multiplicatifs, où la distance peut être multipliée par un facteur k, des spanners additifs où la distance peut être augmentée d'un montant k. Dans le cas d'un spanneur additif sur Q_n, des résultats concernent les degrés du spanneur :

1. si et , alors le plus petit degré maximal Δ(k,n) est .
2. si et n est grand, il existe un spanneur de degré moyen au plus .

Pour avoir un spanner 2-additif de Q₃ on sélectionne les arêtes satisfaisant une des trois conditions.

De nombreuses études sur les spanners, et des constructions pour des modèles généralisés de l'hypercube, sont dues à Arthur L. Liestman et Thomas C. Shermer. Ils ont en particulier proposé un spanner additif avec un montant 2 où les arêtes sont celles dont les extrémités sont données par les trois conditions suivantes :

1. 
2. 
3. u = (0,x₂,...,x_n),v = (1,x₂,...,x_n)

Ce processus est illustré dans l'image ci-contre où les arêtes satisfaisant une des conditions sont surlignées ; l'ensemble de ces arêtes constitue le spanner. Pour obtenir un chemin entre deux sommets, considérons que l'on démarre d'un sommet (0,x₂,...,x_n). On inverse d'abord ses coordonnées paires, car la condition (1) impose l'existence d'une arête sur tout sommet commençant par 0 avec une différence sur bit pair. On change ensuite la première coordonnée en 1 grâce à la condition (3), à partir de quoi on peut inverser toutes les coordonnées impaires par la condition (2). Si le sommet de destination est (1,y₂,...,y_n) alors on est arrivé car on commence par 1 et les coordonnées paires comme impaires ont pu être inversé ; si le sommet de destination est (0,y₂,...,y_n) on utilise une dernière inversion par la condition (3). Le cas où le sommet d'origine est (1,x₂,...,x_n) est traité de façon similaire : inverser les coordonnées impaires, passer la première coordonnée en 0, inverser les coordonnées paires, passer la première coordonnée en 1 si nécessaire. Dans l'image ci-contre, on voit le délai de 2 si on cherche un chemin de 001 à 000 : ce qui se ferait normalement directement en une étape doit se faire en trois étapes, en passant par 101 et 100.

Diffusions

Dans le problème de la diffusion (anglais broadcast), un nœud source souhaite diffuser une information à tous les autres nœuds. Dans le modèle classique, à chaque étape un nœud donné peut transmettre au plus une information, cette information utilisant une arête et étant transmise à la fin de l'étape. Dans ce modèle, la diffusion la plus performante est celle où, à chaque étape, chaque nœud en contacte un autre, c'est-à-dire que le nombre de nœuds contactés est doublé. Le nombre d'étapes minimal est donc log₂n ; un graphe pouvant finir une diffusion en log₂n étapes quelle que soit l'origine et en minimisant le nombre d'arêtes est un graphe de diffusion minimale (anglais minimal broadcast graph). Dans le cas où n = 2^k, le nœud source doit avoir au moins k voisins car il doit diffuser à chaque étape pour faire doubler le nombre de voisins ; la source n'étant pas fixée, on obtient que chaque nœud doit avoir au moins k voisins d'où arêtes ( vient du partage de chaque arête dans un graphe non-orienté), ce qui est précisément le cas d'un hypercube. Ainsi, l'hypercube est un graphe de diffusion minimale.

Parmi les problèmes proches se trouve le commérage (anglais gossip) où chaque nœud veut échanger une information avec tous les autres, autrement dit chaque nœud est la source d'une diffusion. Des cas particuliers s'intéressent aux variantes locales : par exemple, dans un commérage 'local', chaque nœud veut apprendre les messages de ses voisins.