Exercices

Imaginer un graphe dont les sommets représentent les nombres entiers positifs ayant exactement $n$ chiffres binaires (le nombre peut commencer par des zéros), et dans lequel il y a une arête entre deux sommets si et seulement si la représentation des nombres binaires des extrémités diffère en exactement une position.

Par exemple, si $n=2$, les sommets sont $00$, $01$, $10$, et $11$. Il y a dans ce cas quatre arêtes : entre les sommets $00$ et $01$, entre $00$ et $10$, entre $10$ et $11$ et entre $01$ et $11$.

On appelle un tel graphe un hypercube.

Exercice 5.1   Déterminer $\vert V(G)\vert$ (en fonction de $n$) si $G$ est un hypercube.

Exercice 5.2   Quel est le degré des sommets d'un hypercube (en fonction de $n$). Pourquoi ?