L’étiquette « Hamilton » réunit ce qui tourne autour d’un même geste : passer une fois par chaque sommet d’un réseau, puis revenir au point de départ.
Elle porte d’abord un feuilleton numéroté, qui se lit dans l’ordre. Il commence avant son héros, avec les ponts d’Euler en 1736, puis viennent le jeu icosien d’Hamilton, les critères de Dirac et d’Ore — qui garantissent qu’un parcours existe sans avoir à le construire —, et la question qui fait tout l’intérêt du sujet : pourquoi ce problème résiste-t-il quand celui d’Euler se résout en une ligne. Les épisodes paraissent au fil des mois.
Mais l’étiquette ne se limite pas à ce feuilleton : elle signale aussi les énigmes où un parcours hamiltonien se cache sous un déguisement. Un représentant de commerce relie quatorze villes de cinq lettres, chacune commençant par une lettre contenue dans la précédente ; seize agents secrets reçoivent des noms de code qui ne diffèrent que d’un chiffre entre voisins — c’est un code de Gray, donc une promenade sur les sommets d’un hypercube. Le plus difficile y est de reconnaître la structure : une fois le graphe dessiné, l’énoncé change de nature.
Côté exercices, le site prolonge le sujet avec Le car de ramassage, où le car doit s’arrêter à chaque carrefour une fois et une seule, et avec son pendant eulérien, la tournée du facteur, où c’est chaque rue qu’il faut emprunter.
Une échappée, enfin : la validation grimpante emprunte l’image d’un parcours qui visiterait chaque sommet une fois pour parler d’évaluation — et dit aussi où l’analogie s’arrête.
Trouver une tournée passant par toutes les villes est déjà difficile. Le problème du voyageur de commerce demande davantage : trouver la meilleure, ou s’en approcher avec une garantie.
Entre explosion combinatoire, backtracking et NP-complétude, cet épisode explore les limites de nos algorithmes.
Trouver un parcours est une chose.
Savoir avant de le chercher qu’un parcours doit exister en est une autre.
La suite « 1 2 1 1 appelle 1 2 2 1 » : cycles hamiltoniens et codes de Gray, ou comment énumérer sans jamais sauter d'étape.
Chemins eulériens et cycles hamiltoniens : pourquoi un critère local simple d'un côté, et un problème redoutable de l'autre.
Après les ponts d’Euler, Hamilton déplace le regard : il ne s’agit plus de parcourir toutes les arêtes, mais de visiter tous les sommets. Le jeu icosien, imaginé autour du dodécaèdre, marque l’entrée des graphes hamiltoniens dans l’histoire des mathématiques.
M. Noël est représentant de commerce, et voyage ainsi dans toute la France. A la fin du mois, il établit sa note de frais. Il repère donc sur une carte les quatorze villes qu’il a visitées. Il constate, avec amusement,…
Pourquoi un problème de ponts datant de 1736 régit-il encore nos algorithmes modernes ? Découvrez l'héritage d'Euler avant de plonger dans l'enfer des graphes hamiltoniens.