Demi-hypercube (graphe)
# Demi-hypercube (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é |
| - | - | - | - | - |
| 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.

