Utilisateur:Yopai/Graphe hamiltonien
Histoire
[modifier | modifier le code]Prémisses
[modifier | modifier le code]
Au IXe siècle, le poète indien Rudrata mentionne le problème consistant à déterminer comment parcourir chaque case d'un échiquier une et seule fois en n'utilisant que les mouvements d'un cavalier[réf. nécessaire]. C'est ce qu'on appellera le problème du cavalier, et dont la solution est un chemin hamiltonien sur un échiquier en reliant les cases distantes d'un mouvement de cavalier. (Exemple de solution sur l'animation ci-contre)
À noter qu'il existe également des solutions qui sont des parcours fermés, autrement dit des cycles hamiltoniens.
Étude par William Hamilton
[modifier | modifier le code]
Les graphes hamiltoniens sont nommés d'après William Rowan Hamilton qui était astronome royal en Irlande, au milieu du XIXe siècle. Celui-ci a inventé un jeu qu'il a nommé icosian game, qui consiste à trouver un cycle hamiltonien dans le graphe des arêtes du dodécaèdre. Hamilton a résolu ce problème à l'aide d'un nouveau type de calculs qu'il a appelé le icosian calculus (en)[1],[2], et que l'on décrirait de nos jours par des calculs dans un certain groupe non commutatif. Cette solution ne se généralise malheureusement pas à un graphe arbitraire.
Bien que ces graphes soient nommés d'après Hamilton, les cycles hamiltoniens dans les polyèdres avaient déjà été étudiés un an plus tôt par Thomas Kirkman[3].
- (en) William Rowan Hamilton, « Account of the Icosian Calculus », Proceedings of the Royal Irish Academy, no 6,
- (en) William Rowan Hamilton, « Memorandum respecting a new system of roots of unity », Philosophical Magazine, no 12, .
- (en) N. L. Biggs, « T. P. Kirkman, mathematician », The Bulletin of the London Mathematical Society, vol. 13, no 2, , p. 104 (DOI 10.1112/blms/13.2.97, MR 608093, lire en ligne).