Dans la théorie des graphes, une branche des mathématiques, le graphe demi-hypercube est obtenu à partir du graphe hypercube 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 A hypercube related graph sur MathOverflow.
Construction Deux sommets de sont adjacents dans si et seulement s'ils se trouvent exactement à une distance de deux dans . À 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.
300px 180px peut être construit àpartir du graphe tesseract en enlevant des sommets. peut aussi être construit àpartir du graphe hexaédrique en ajoutant des arêtes.
On peut aussi obtenir à partir de l'hypercube de dimension inférieure en ajoutant des arêtes entre les sommets à distance deux.
Le graphe est le graphe des arêtes et des sommets d'un objet géométrique, le demi-hypercube de dimension .
On peut aussi interpréter comme le graphe de la relation entre les nombres binaires de longueur comportant un nombre pair de 1 (comme 0, 3, 5, 6, 9, etc.C'est la , surnommée par les anglophones evil numbers sequence (suite des « nombres méchants »)) qui sont à une distance de Hamming égale à deux..
Exemples graphe sommets arêtes degré illustration 1 Graphe singleton 1 0 0 80px 2 Graphe chaîne 2 1 1 80px 3 Graphe tétraédrique 4 6 3 80px 4 Graphe de l'hexadécachore 8 24 6 80px 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.
Notes et références
Lien externe
Article lié Moitié bipartie
Catégorie:Famille de graphes