Metraipolis › archive › dc_33fef66bddb2
Graphe hamiltonien — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Graphe_hamiltonien
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-15T15:40:00.832Z
- SHA-256 of the archived text
a34fe145c2d314fb3a5751def8e107499c548467ce1ce1088000005db4d32540- Stable URL of this page
https://metraipolis.com/documento/dc_33fef66bddb2
How to cite
Graphe hamiltonien — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Graphe_hamiltonien (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_33fef66bddb2 (Metraipolis archive dc_33fef66bddb2, sha256 a34fe145c2d314fb3a5751def8e107499c548467ce1ce1088000005db4d32540)
BibTeX
@misc{dc33fef66bddb2,
title = {Graphe hamiltonien — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Graphe_hamiltonien},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_33fef66bddb2; sha256 a34fe145c2d314fb3a5751def8e107499c548467ce1ce1088000005db4d32540},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Graphe_hamiltonien. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En mathématiques, dans le cadre de la théorie des graphes, un chemin hamiltonien d'un graphe orienté ou non orienté est un chemin qui passe par tous les sommets une fois et une seule. Un cycle hamiltonien est un chemin hamiltonien qui est un cycle. Un graphe hamiltonien est un graphe qui possède un cycle hamiltonien. Un graphe hamiltonien ne doit pas être confondu avec un graphe eulérien, où l'on passe par toutes les arêtes une fois et une seule : dans un cycle hamiltonien, on peut très bien négliger de passer par certaines arêtes. Un graphe peut être eulérien, hamiltonien, les deux à la fois, ou aucun des deux : le graphe papillon est un exemple de graphe eulérien mais pas hamiltonien. Un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens : ainsi, le graphe de Chvátal a 12 sommets, 24 arêtes et 370 cycles hamiltoniens distincts. On a démontré un certain nombre de conditions mathématiques, qui, si elles sont vérifiées, permettent d'assurer qu'un graphe est hamiltonien, ainsi que des conditions qui, si elles ne sont pas vérifiées, assurent qu'il ne l'est pas. On peut par ailleurs confier à des ordinateurs le soin de chercher des cycles hamiltoniens au moyen d'algorithmes que l'on a optimisés petit à petit. Dans les deux cas, le problème algorithmique du chemin hamiltonien est NP-complet, i.e. difficile à résoudre dans un temps raisonnable dans le cas général. Les graphes hamiltoniens sont un domaine de recherche actif à la fois en mathématiques et en informatique. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «théorie des graphes»). Fonte: Wikipedia in francese, voce «Graphe hamiltonien» — https://fr.wikipedia.org/wiki/Graphe_hamiltonien Wikidata Q18011235 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q18011235 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Graphe_hamiltonien?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 240125836, consultata il 2026-10-15T15:08:00.202Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: d007886ae79a243082a79e231741ca0a25834fdc8008443a40647edb41b8fd63