Graphique de Hanoï - Hanoi graph

Le graphique de Hanoï ${\displaystyle H_{3}^{7}}$

En théorie des graphes et en mathématiques récréatives , les graphes de Hanoï sont des graphes non orientés dont les sommets représentent les états possibles du puzzle de la Tour de Hanoï , et dont les arêtes représentent les mouvements admissibles entre des paires d'états.

Construction

Le graphique de Hanoï (disques noirs) dérivé des valeurs impaires dans le triangle de Pascal${\style d'affichage H_{3}^{5}}$

Le puzzle se compose d'un ensemble de disques de différentes tailles, placés par ordre croissant de taille sur un ensemble fixe de tours. Le graphique de Hanoï pour un puzzle avec des disques sur des tours est noté . Chaque état du puzzle est déterminé par le choix d'une tour pour chaque disque, le graphe a donc des sommets. ${\style d'affichage n}$${\style d'affichage k}$${\displaystyle H_{k}^{n}}$${\displaystyle k^{n}}$

Dans les déplacements du puzzle, le plus petit disque d'une tour est déplacé soit vers une tour inoccupée, soit vers une tour dont le plus petit disque est plus grand. S'il y a des tours inoccupées, le nombre de mouvements autorisés est ${\displaystyle u}$

${\displaystyle {\binom {k}{2}}-{\binom {u}{2}},}$

qui va d'un maximum de (quand est zéro ou un et est égal à zéro) à (lorsque tous les disques sont sur une tour et est ). Par conséquent, les degrés des sommets dans le graphe de Hanoï vont d'un maximum de à un minimum de . Le nombre total d'arêtes est ${\displaystyle {\tbinom {k}{2}}}$${\displaystyle u}$${\displaystyle {\tbinom {u}{2}}}$${\style d'affichage k-1}$${\displaystyle u}$${\style d'affichage k-1}$${\displaystyle {\tbinom {k}{2}}}$${\style d'affichage k-1}$

${\displaystyle {\frac {1}{2}}{\binom {k}{2}}{\bigl (}k^{n}-(k-2)^{n}{\bigr )}.}$

Pour (pas de disques) il n'y a qu'un seul état du puzzle et un seul sommet du graphe. Pour , le graphe de Hanoï peut être décomposé en copies du plus petit graphe de Hanoï , une pour chaque emplacement du plus grand disque. Ces copies ne sont connectées les unes aux autres que dans les états où le plus gros disque est libre de se déplacer : c'est le seul disque de sa tour, et une autre tour est inoccupée. ${\style d'affichage k=0}$${\style d'affichage k>0}$${\displaystyle H_{k}^{n}}$${\style d'affichage k}$${\displaystyle H_{k}^{n-1}}$

Les propriétés générales

${\style d'affichage H_{3}^{3}}$ avec 12 arêtes supprimées pour donner un cycle hamiltonien

Chaque graphe de Hanoï contient un cycle hamiltonien .

Le graphe de Hanoï est un graphe complet sur les sommets. Parce qu'ils contiennent des graphiques complets, tous les grands graphiques de Hanoi nécessitent au moins des couleurs dans n'importe quelle coloration de graphique . Ils peuvent être colorés avec des couleurs exactes en additionnant les indices des tours contenant chaque disque, et en utilisant la somme modulo comme couleur. ${\displaystyle H_{k}^{1}}$${\style d'affichage k}$${\displaystyle H_{k}^{n}}$${\style d'affichage k}$${\style d'affichage k}$${\style d'affichage k}$

Trois tours

Un cas particulier des graphes de Hanoi qui a été bien étudié depuis les travaux de Scorer, Grundy & Smith (1944) est le cas des graphes de Hanoi à trois tours, . Ces graphes ont 3 ⁿ sommets ( OEIS :  A000244 ) et${\displaystyle H_{3}^{n}}$ 3( ³ⁿ −1)/2 bords ( OEIS :  A029858 ). Ce sont des graphes de penny (les graphes de contact des disques unitaires qui ne se chevauchent pas dans le plan), avec un arrangement de disques qui ressemble au triangle de Sierpinski . Une façon de construire cet arrangement est de disposer les nombres du triangle de Pascal sur les points d'un réseau hexagonal , avec un espacement unitaire, et de placer un disque unité sur chaque point dont le nombre est impair. Le diamètre de ces graphiques et la longueur de la solution de la forme standard du puzzle de la tour de Hanoï (dans lequel les disques commencent tous sur une tour et doivent tous se déplacer vers une autre tour) est de . ${\displaystyle 2^{n}-1}$

Plus de trois tours

Pour , la structure des graphes de Hanoi n'est pas aussi bien comprise, et le diamètre de ces graphes est inconnu. Quand et ou quand et , ces graphiques ne sont pas planaires. ${\displaystyle k>3}$${\style d'affichage k>4}$${\style d'affichage n>0}$${\style d'affichage k=4}$${\style d'affichage n>2}$

Les références