title: Demi-hypercube (graphe)
text: # 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.
  
  