^{PDFprof.com Search Engine}

Chapitre 6: Graphes eulériens et hamiltoniens

Comment savoir si un graphe est hamiltonien ?
Un cycle qui passe exactement une fois par chaque arête d'un graphe est dit « eulérien ».
Un cycle qui passe exactement une fois par chaque sommet d'un graphe est dit « hamiltonien ».
Comment savoir si un graphe est eulérien ?
Un graphe connexe admet un parcours eulérien si et seulement si ses sommets sont tous de degré pair sauf au plus deux.
Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
Comment trouver un cycle eulérien ?
Théorème d'Euler
G admet un cycle eulérien si et seulement si tous les sommets de G sont de degré pair.
G admet une chaîne eulérienne (non fermée) si et seulement si le nombre de sommets de degré impair dans G est 2.
Si tel est le cas, les extrémités de la chaîne eulérienne sont les deux sommets de degré impair.
Un chemin élémentaire est hamiltonien s'il passe par tous les points du graphe.
Un chemin hamiltonien passe donc une et une seule fois par tout point du graphe ; si le graphe possède n points, un chemin hamiltonien contient exactement n-1 arcs.

Comment savoir si un graphe est hamiltonien ?