Utilisateur:Yopai/Brouillon
- → N'hésitez pas à publier sur le brouillon un texte inachevé et à le modifier autant que vous le souhaitez.
- → Pour enregistrer vos modifications au brouillon, il est nécessaire de cliquer sur le bouton bleu : « Publier les modifications ». Il n'y a pas d'enregistrement automatique.
Si votre but est de publier un nouvel article, votre brouillon doit respecter les points suivants :
- Respectez le droit d'auteur en créant un texte spécialement pour Wikipédia en français (pas de copier-coller venu d'ailleurs).
- Indiquez les éléments démontrant la notoriété du sujet (aide).
- Liez chaque fait présenté à une source de qualité (quelles sources – comment les insérer).
- Utilisez un ton neutre, qui ne soit ni orienté ni publicitaire (aide).
- Veillez également à structurer votre article, de manière à ce qu'il soit conforme aux autres pages de l'encyclopédie (structurer – mettre en page).
- → Si ces points sont respectés, pour transformer votre brouillon en article, utilisez le bouton « publier le brouillon » en haut à droite. Votre brouillon sera alors transféré dans l'espace encyclopédique.
Graphe hamiltonien[modifier | modifier le code]
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).