[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 graphe hamiltonien
[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.