Demi-hypercube (graphe)

Demi-hypercube
Le graphe demi-hypercube ${\frac {1}{2}}Q_{3}$ est le graphe tétraédrique
Notation	${\frac {1}{2}}Q_{n}$
Nombre de sommets	$2^{n-1}$
Nombre d'arêtes	$n(n-1)2^{n-3}$
Distribution des degrés	${\frac {n(n-1)}{2}}$-régulier
Automorphismes	$n!2^{n-1}$
Propriétés	Distance-régulier Hamiltonien Symétrique

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.

Lien externe

(en) Eric W. Weisstein, « Halved Cube Graph », sur MathWorld

Article lié

• Moitié bipartie