Les graphes hamiltoniens forment un autre problème de la théorie de graphes. Dans ce cas, le but est de savoir si un graphe admet un cycle qui contient tous les sommets d’un graphe. Les origines de ce problème ont lieu avec un important mathématicien appelé Sir William R. Hamilton, d’ici le nom, mais en réalité le premier à étudier le problème c’était un autre mathématicien appelé T.P. Kirkman. 

 

Néanmoins, l'attribution à Hamilton du nom du problème c’est parce qu’il avait inventé un jeu fondé sur les graphes hamiltoniennes. Le jeu s’appelait “le voyage autour du monde”, et consistait à trouver un chemin ou parcours à travers les arêtes d’un dodécaèdre passant une seule fois pour chaque sommet qui représentent les citées plus importantes du monde. Le parcours final avait le nom de “voyage autour du monde”. Cela c’est ce qu’on appelle cycle hamiltonienne. 

 

Pour l’instant on ne connaît encore aucun critère pour savoir si un graphe est hamiltonienne ou pas mais il y a quelques conditions nécessaires.

• Le graphe G= (V,E) est connexe

•  Tous ses sommets ont degré >1.

• Le graphe G n’est pas dirigé, donc il doit être non dirigé.

 

Il y a aussi une autre conditionne pour savoir si un graphe a un chemin, pas un cycle, hamiltonien laquelle dit que si la somme des durées de deux sommets qui ne sont pas adjacents est égal ou plus grand au nombre total de sommets moins 1, alors le graphe a un chemin hamiltonien. On va voir un exemple:

 

Si on prend ce graphe, on sait que le nombre total de sommets c’est #V=5. Donc si on applique la formule qu’on vient de décrire:

 

​

grA + grD ≥ #V - 1 → 3 + 2 ≥ 5-1

​

​

​

La condition s'accomplit pourtant on peut dire qu’il existe un chemin hamiltonien. En plus il est aussi un graphe connexe et tous ses sommets ont un degré supérieur à 1. On peut alors tracer un chemin hamiltonien  lequel sera celle-ci colouré  en jaune:

​

​

​

​

​

​

 

On pourra aussi trouver le cycle hamiltonien en unint aussi les sommets A et E: