[4/6] Pourquoi les graphes hamiltoniens sont-ils difficiles ?
Entre explosion combinatoire, backtracking et NP-complétude, cet épisode explore les limites de nos algorithmes.
Étiquette Hamilton
[3/6] Dirac et Ore : quand les degrés imposent un cycle hamiltonien
Trouver un parcours est une chose.
Savoir avant de le chercher qu’un parcours doit exister en est une autre.
[2/6] Euler contre Hamilton : du critère local au casse-tête global
Repères de la série. L’article d’ouverture consacré à l’héritage d’Euler a posé le rôle fondateur des ponts de Königsberg. L’ article 1/6 sur Hamilton et le jeu icosien a ensuite déplacé la question des arêtes vers les sommets. Ce deuxième article s’intéresse maintenant à une…
[1/6] Hamilton et le jeu icosien : naissance des graphes hamiltoniens
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.
Avant Hamilton : L’héritage d’Euler – 1736
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.