Chemin
Nœuds explorés
Cycle hamiltonien
Chemin hamiltonien

Mode

    But

    En savoir plus sur les chemins et cycles hamiltoniens

    Explorateur de chemins hamiltoniens

    En 1857 William Rowan Hamilton inventa un casse-tête : parcourir les arêtes d'un dodécaèdre en passant par chacun de ses 20 coins exactement une fois et en terminant au point de départ. Une telle route s'appelle aujourd'hui un cycle hamiltonien. Elle est facile à vérifier et, en général, difficile à trouver. Tracez-en une vous-même sur le dodécaèdre de Hamilton, sur un échiquier ou sur un graphe que vous dessinez, ou regardez une recherche par retour sur trace en chercher une, comptez les impasses qu'elle rencontre et voyez à quel point quelques tests simples raccourcissent la recherche. Choisissez un graphe et un but : un cycle qui revient à son départ, ou un chemin. Tracer : cliquez sur un sommet pour commencer, puis sur un voisin à chaque fois ; des cercles en pointillés montrent où aller ensuite. Un clic sur le dernier sommet, Retour ou Annuler revient d'un pas, et Indice donne un pas suivant qui mène encore au but. Recherche : Lancer ou Pas déroule une recherche par retour sur trace, qui ajoute des sommets jusqu'à l'impasse puis revient en arrière ; les tirets rouges montrent les retours et les barres comptent les nœuds par longueur de chemin. Avant le départ, un clic sur un sommet choisit où elle commence. Les cases activent et désactivent l'élagage, Comparer lance la même recherche avec et sans, et Tout compter compte chaque cycle ou chemin d'un petit graphe. Modifier : cliquez pour ajouter un sommet, cliquez sur deux sommets pour les relier ou les séparer, faites glisser pour en déplacer un, et Supprimer retire le sommet sélectionné.

    Comment ça marche

    1. Choisissez un graphe, par exemple le dodécaèdre de Hamilton, le graphe de Petersen ou un parcours du cavalier, ou dessinez le vôtre dans Modifier, puis choisissez un cycle ou un chemin comme but.
    2. Dans Tracer, cliquez sur un sommet pour commencer, puis sur un voisin après l'autre. Retour et Annuler reviennent d'un pas, et Indice montre un pas suivant qui mène encore au but.
    3. Dans Recherche, appuyez sur Lancer ou Pas pour regarder le retour sur trace chercher une route, activez et désactivez l'élagage, et appuyez sur Comparer pour voir combien de nœuds chaque variante demande.

    Hamilton contre Euler

    Un chemin eulérien emprunte chaque arête une fois ; un chemin hamiltonien passe par chaque sommet une fois. Cela se ressemble mais se comporte très différemment. Savoir si un graphe connexe a un chemin eulérien se décide en comptant les sommets de degré impair, comme Euler l'a montré en 1736 : il en a un s'il y en a zéro ou deux. Pour les chemins hamiltoniens aucune règle de ce genre n'est connue. Décider si un graphe a un cycle hamiltonien est NP-complet, l'un des 21 problèmes de la liste de Richard Karp de 1972 ; une méthode rapide pour lui donnerait donc des méthodes rapides pour des milliers d'autres problèmes difficiles. Il existe en revanche des conditions qui tranchent pour certains graphes. Le théorème de Dirac de 1952 garantit un cycle hamiltonien quand chaque sommet est de degré au moins n/2, et celui d'Ore de 1960 quand deux sommets non reliés ont toujours des degrés de somme au moins n ; un sommet de degré 1, un point d'articulation ou deux classes de couleurs de tailles différentes en excluent un.

    Comment fonctionne la recherche

    Le retour sur trace construit le chemin un sommet à la fois et, quand il est bloqué, reprend le dernier pas et essaie le voisin suivant. Il trouve toujours un cycle hamiltonien s'il en existe un, mais le nombre de chemins partiels peut croître exponentiellement. Sur la grille 5 × 5, qui n'a pas de cycle hamiltonien, le retour sur trace simple explore 153 745 nœuds avant d'en être sûr. Deux tests arrêtent tôt les chemins sans espoir : un sommet non visité ayant moins de deux voisins libres ne peut plus entrer dans un cycle, et quand les sommets non visités se séparent en morceaux distincts, aucun chemin unique ne peut les couvrir. Avec les deux, la même preuve prend 1 761 nœuds. La règle de Warnsdorff de 1823, qui essaie d'abord le voisin ayant le moins de coups suivants, trouve un parcours du cavalier 8 × 8 depuis un coin en 64 coups sans une seule impasse.

    Questions fréquemment posées

    Quelle est la différence entre un chemin hamiltonien et un cycle hamiltonien ?

    Un chemin hamiltonien passe par chaque sommet d'un graphe exactement une fois. Un cycle hamiltonien fait de même puis revient par une arête de plus à son point de départ, il peut donc commencer à n'importe lequel de ses sommets. Tout graphe ayant un cycle hamiltonien a un chemin hamiltonien (enlevez une arête du cycle), mais l'inverse est faux : le graphe de Petersen a des chemins hamiltoniens et aucun cycle hamiltonien.

    Le dodécaèdre a-t-il un cycle hamiltonien ?

    Oui, 30, en comptant chaque cycle une fois quels que soient son départ et son sens. Hamilton en fit le jeu icosien en 1857, un plateau portant les 20 coins d'un dodécaèdre aplati marqués de consonnes, et vendit les droits pour 25 livres au fabricant de jouets londonien John Jaques and Son. Tout compter trouve les 30 cycles en environ 1 400 nœuds.

    Pourquoi une grille 5 × 5 n'a-t-elle pas de cycle hamiltonien ?

    Coloriez les 25 points comme un échiquier : 13 prennent une couleur et 12 l'autre, et chaque pas mène à l'autre couleur. Un cycle alterne les couleurs sur tout son tour, il lui en faut donc autant de l'une que de l'autre, ce que 13 et 12 ne donnent pas. Le même argument vaut pour toute grille ayant un nombre impair de points, pour un cavalier sur un échiquier 5 × 5 ou 7 × 7 (un cavalier change toujours de couleur de case) et pour le graphe de Herschel, dont les deux classes ont 6 et 5 sommets. Un chemin hamiltonien reste possible : il commence et finit sur la couleur la plus nombreuse.

    Comment la règle de Warnsdorff trouve-t-elle un parcours du cavalier ?

    H. C. von Warnsdorff proposa en 1823 de toujours déplacer le cavalier vers la case depuis laquelle il aura le moins de coups suivants. Les cases près des bords et des coins, faciles à isoler, sont ainsi visitées tôt, tant que le cavalier peut encore y entrer. La règle est empirique, non garantie, et les égalités doivent être départagées d'une manière ou d'une autre, mais sur un échiquier 8 × 8 elle achève le plus souvent un parcours sans revenir en arrière. Associée au retour sur trace, comme dans l'application, elle trouve des parcours ouverts à partir de 5 × 5 et des parcours fermés sur les échiquiers 6 × 6 et 8 × 8.

    Combien de cycles hamiltoniens a un graphe complet ?

    (n − 1)!/2 pour n ≥ 3. Fixez le sommet de départ ; les n − 1 autres peuvent suivre dans n'importe quel ordre, et chaque cycle est compté deux fois, une fois par sens. K₆ en a 5!/2 = 60 et K₁₀ en a 181 440. Ce sont les tournées parmi lesquelles un voyageur de commerce doit choisir, et c'est pourquoi les essayer toutes cesse si vite d'être possible.

    Prêt à l'essayer ?

    Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

    Aller à l'éditeur