Demi-hypercube (graphe)

Modèle:Infobox Graphe Dans la théorie des graphes, une branche des mathématiques, le graphe demi-hypercube $\frac{1}{2}{Q}_n$ est obtenu à partir du graphe hypercube $Q_n$ en ne gardant qu'un sommet sur deux et en reliant les sommets qui étaient à une distance de deux. Il est appelé halved cube, halfcube ou demihypercube en anglais.

Construction

Deux sommets de $\frac{1}{2}{Q}_n$ sont adjacents dans $\frac{1}{2}{Q}_n$ si et seulement s'ils se trouvent exactement à une distance de deux dans $Q_n$. À partir d'un graphe hypercube donné, on peut obtenir deux graphes demi-hypercubes distincts mais isomorphes, suivant le sommet de départ que l'on a choisi.

$\frac{1}{2}{Q}_4$ peut être construit à partir du graphe tesseract $Q_4$ en enlevant des sommets.	$\frac{1}{2}{Q}_4$ peut aussi être construit à partir du graphe hexaédrique $Q_3$ en ajoutant des arêtes.

On peut aussi obtenir $\frac{1}{2}{Q}_n$ à partir de l'hypercube de dimension inférieure $Q_{n-1}$ en ajoutant des arêtes entre les sommets à distance deux.

Le graphe $\frac{1}{2}{Q}_n$ est le graphe des arêtes et des sommets d'un objet géométrique, le demi-hypercube de dimension $n$.

On peut aussi interpréter $\frac{1}{2}{Q}_n$ comme le graphe de la relation entre les nombres binaires de longueur $n$ comportant un nombre pair de 1 (comme 0, 3, 5, 6, 9, etc.) qui sont à une distance de Hamming égale à deux.

Exemples

$n$	graphe $\frac{1}{2}{Q}_n$	sommets	arêtes	degré	illustration
1	Graphe singleton $K_1$	1	0	0
2	Graphe chaîne $K_2$	2	1	1
3	Graphe tétraédrique $K_4$	4	6	3
4	Graphe de l'hexadécachore	8	24	6
5	Complémentaire du graphe de Clebsch dans le graphe tesseract	16	80	10

Propriétés

Comme c'est la moitié bipartie d'un graphe distance-régulier, le graphe demi-hypercube est lui-même distance-régulier.

Comme c'est la moitié bipartie d'un graphe hamiltonien, il est lui-même hamiltonien.

Article lié

• Moitié bipartie