Graphe hamiltonien

Carte Peu commune · n° 160992

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...

Lire sur Wikipédia · Image Christoph Sommer, CC BY-SA 3.0