Les chemins et cycles hamiltoniens expliqués
Dessinez cinq points en rond, reliez chacun à ses deux voisins, et vous pouvez faire le tour en passant une fois par chaque point et revenir chez vous : un cycle hamiltonien. Ajoutez quelques arêtes ou enlevez-en, et la question devient étonnamment difficile. Savoir si un graphe a un tel cycle est l'un des problèmes les plus connus auxquels aucun ordinateur ne sait encore répondre vite pour tout graphe.
Chaque sommet une fois
Un graphe est un ensemble de points, les sommets, reliés par des lignes, les arêtes. Un chemin hamiltonien suit des arêtes et passe par chaque sommet exactement une fois ; un cycle hamiltonien revient en plus à son point de départ, il a donc autant d'arêtes que de sommets. Un graphe ayant un cycle hamiltonien est dit hamiltonien. Vérifier une route proposée est facile : comptez les sommets et regardez chaque pas. En trouver une, ou prouver qu'il n'y en a aucune, est la partie difficile, car le nombre d'ordres dans lesquels les sommets pourraient être visités croît comme n!, déjà 2,4 × 10¹⁸ pour 20 sommets.
Le jeu icosien de Hamilton
William Rowan Hamilton, le mathématicien irlandais qui découvrit les quaternions, inventa le jeu icosien en 1857. Son plateau montrait un dodécaèdre aplati dans le plan, ses 20 coins marqués par des consonnes, et la tâche principale était de poser des chevilles numérotées de 1 à 20 sur les coins de sorte que les nombres consécutifs, ainsi que 20 et 1, soient reliés par des arêtes. Hamilton vendit les droits pour 25 livres au fabricant de jouets londonien John Jaques and Son, qui le sortit en 1859 ; il se vendit mal. Le casse-tête a 30 solutions, en comptant un cycle une fois quels que soient son départ et son sens. La question elle-même n'était pas nouvelle : Thomas Kirkman avait demandé quels polyèdres ont un cycle passant par tous leurs coins dans un article envoyé à la Royal Society en 1855, et en avait montré un qui n'en a aucun.
Parcours du cavalier
Un parcours du cavalier déplace un cavalier d'échecs de façon qu'il se pose exactement une fois sur chaque case : un chemin hamiltonien dans le graphe dont les sommets sont les cases et les arêtes les coups du cavalier. Un parcours fermé s'achève à un coup de cavalier de son départ, c'est-à-dire un cycle hamiltonien. Les joueurs d'échecs posaient de tels problèmes il y a plus de mille ans, et Euler les étudia dans un article de 1759. En 1823 H. C. von Warnsdorff proposa d'aller toujours vers la case ayant le moins de coups suivants ; cette règle simple achève le plus souvent un parcours d'un échiquier 8 × 8 sans revenir en arrière. Un cavalier change toujours de couleur de case, un parcours fermé demande donc autant de cases claires que de cases sombres, ce qui exclut les échiquiers ayant un nombre impair de cases. Allen Schwenk a montré en 1991 exactement quels échiquiers rectangulaires ont un parcours fermé ; parmi les carrés, tous ceux dont le côté est pair et vaut au moins 6. L'échiquier ordinaire a 13 267 364 410 532 parcours fermés, comptés par Brendan McKay en 1997.
Les graphes sans cycle hamiltonien
Les preuves les plus rapides qu'il n'y a pas de cycle sont des arguments de comptage. Si les sommets peuvent être coloriés avec deux couleurs de sorte que chaque arête relie des couleurs différentes, un cycle alterne et demande autant de sommets de chaque couleur ; une grille 5 × 5 en a 13 d'une et 12 de l'autre, elle n'a donc pas de cycle hamiltonien. Un point d'articulation, dont le retrait coupe le graphe, devrait être traversé deux fois, et un sommet de degré 1 ne peut pas l'être du tout. Certains graphes échappent à tous ces arguments. Le graphe de Petersen, publié par Julius Petersen en 1898, a 10 sommets de degré 3 et aucun cycle hamiltonien, et pourtant supprimer un sommet quelconque laisse un graphe qui en a un ; c'est le plus petit graphe hypohamiltonien. Le graphe de Herschel, nommé d'après Alexander Stewart Herschel, qui écrivit sur le jeu icosien en 1862, a 11 sommets et 18 arêtes et est le graphe d'un polyèdre à neuf faces quadrangulaires. Aucun polyèdre à moins de coins ne manque de cycle hamiltonien. En 1884 Peter Guthrie Tait conjectura que tout polyèdre ayant trois arêtes à chaque coin en possède un ; W. T. Tutte trouva en 1946 un contre-exemple à 46 sommets.
Les conditions qui en garantissent un
Si un graphe a beaucoup d'arêtes, un cycle hamiltonien est certain. Gabriel Dirac prouva en 1952 qu'un graphe à n ≥ 3 sommets dont chaque sommet est de degré au moins n/2 en a un, et Øystein Ore affaiblit la condition en 1960 : il suffit que deux sommets non reliés aient toujours des degrés de somme au moins n. Les deux conditions ne valent que dans un sens. Un simple anneau de 100 sommets est partout de degré 2, bien en dessous de 50, et c'est pourtant un cycle hamiltonien. Voilà le tableau général : il y a des conditions suffisantes et il y a des raisons d'échec, et entre les deux s'étend un vaste territoire de graphes que seule une recherche peut trancher.
Pourquoi aucun test rapide n'est connu
Décider si un graphe a un cycle hamiltonien est NP-complet ; c'était l'un des 21 problèmes de la liste de Richard Karp de 1972. Une méthode qui le résoudrait vite pour tout graphe résoudrait vite des milliers d'autres problèmes et trancherait la question P contre NP. Le contraste avec les chemins eulériens, qui empruntent chaque arête une fois, est frappant : Euler a montré en 1736 que compter les sommets de degré impair tranche cette question d'un coup. Les meilleures méthodes exactes pour les cycles hamiltoniens prennent encore un temps exponentiel. La programmation dynamique sur tous les sous-ensembles de sommets, trouvée par Richard Bellman et par Michael Held et Richard Karp en 1962, demande environ n² × 2ⁿ étapes, et la méthode randomisée d'Andreas Björklund de 2010 environ 1,657ⁿ. En pratique le retour sur trace avec un bon élagage traite des graphes de quelques dizaines de sommets, et le problème du voyageur de commerce, qui cherche le cycle hamiltonien le plus court, est la version pondérée de la même question.
Les codes de Gray et l'hypercube
Écrivez les nombres de 0 à 7 comme des codes de 3 bits et reliez deux codes quand ils diffèrent d'exactement un bit : le résultat est le graphe d'un cube. Un cycle hamiltonien qui le parcourt, par exemple 000, 001, 011, 010, 110, 111, 101, 100, liste les huit codes de sorte que chacun diffère du précédent d'un seul bit. Une telle liste est un code de Gray, nommé d'après Frank Gray des laboratoires Bell, qui le décrivit dans un brevet déposé en 1947. Tout hypercube en a un : écrivez les codes à un bit de moins, puis la même liste à l'envers, et placez un 0 devant la première moitié et un 1 devant la seconde. Les codeurs rotatifs utilisent des codes de Gray pour qu'une lecture prise entre deux positions ne soit jamais fausse de plus d'un pas. Le cube a 6 cycles hamiltoniens et l'hypercube de 4 bits en a 1 344.
À vous d'explorer
Ouvrez l'explorateur de chemins hamiltoniens pour essayer vous-même le casse-tête de Hamilton, avec des cercles en pointillés montrant où aller ensuite, ou passez à Recherche et regardez le retour sur trace travailler : le chemin grandit, des tirets rouges marquent les retours, et les barres comptent les nœuds par longueur de chemin. Activez et désactivez le test d'impasse, le test de connexité et l'ordre de Warnsdorff, comparez combien de nœuds chacun demande, comptez tous les cycles d'un petit graphe, ou dessinez votre propre graphe et voyez lesquels des tests rapides s'appliquent.
Questions fréquemment posées
Un graphe ayant un circuit eulérien est-il aussi hamiltonien, ou l'inverse ?
Ni l'un ni l'autre ne découle de l'autre. Le nœud papillon, deux triangles partageant un sommet, a un circuit eulérien parce que tous les degrés sont pairs, mais aucun cycle hamiltonien, puisque le sommet partagé devrait être traversé deux fois. Le graphe complet K₄ a des cycles hamiltoniens, mais ses quatre sommets sont de degré 3, il n'a donc pas de circuit eulérien.
Un ordinateur ne peut-il pas simplement essayer tous les ordres ?
Seulement pour de petits graphes. Il y a n! ordres de n sommets, environ 2,4 × 10¹⁸ pour 20. Le retour sur trace fait bien mieux, car il ne suit que des arêtes et abandonne un chemin partiel dès qu'il est bloqué : il trouve les 30 cycles du dodécaèdre à 20 sommets en environ 1 400 étapes. Mais pour certains graphes le nombre de chemins partiels croît tout de même exponentiellement, et aucune méthode n'est connue qui évite cela pour tout graphe.
Le problème du chemin hamiltonien est-il plus facile que celui du cycle ?
Non, les deux sont NP-complets. Chacun se ramène à l'autre : ajoutez un nouveau sommet relié à tous les anciens, et l'ancien graphe a un chemin hamiltonien exactement quand le nouveau a un cycle hamiltonien. Dans l'autre sens, un problème de cycle devient un problème de chemin en ajoutant une copie d'un sommet, avec les mêmes voisins, et un nouveau sommet terminal attaché au sommet et un autre à sa copie.
Pourquoi un parcours du cavalier sur un échiquier 5 × 5 doit-il commencer sur la couleur des coins ?
Des 25 cases, 13 ont la couleur des coins et 12 l'autre, et un cavalier change de couleur à chaque coup. Un parcours de 25 cases alterne les couleurs, il commence et finit donc sur la couleur qui a le plus de cases. L'application trouve les 1 728 parcours ouverts de l'échiquier 5 × 5, 864 si un parcours et son inverse comptent pour un, et tous commencent et finissent sur une case de la couleur des coins.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Ouvrir l'explorateur de chemins hamiltoniens