CM3-RO-cheminFaisant

Un graphe hamiltonien :

• Possède un chemin hamiltonien

• Possède un cycle ou un circuit qui passe par tous les sommets du graphe une et une seule fois

Un graphe eulérien

• Possède un circuit ou un cycle eulérien

• Possède un cycle ou un circuit qui passe par tous les sommets du graphe une et une seule fois

Un graphe non orienté où tous les sommets sont de degré pair est :

• Hamiltonien

• Eulérien

Si dans un graphe simple non orienté il existe un sommet dont le degré est < |V|/2 :

• Le graphe n'est pas hamiltonien

• Le graphe est hamiltonien

• Le critère n'est pas suffisant pour décider

Un chemin élémentaire

• Est un cycle

• Est un chemin hamiltonien

• Ne passe pas deux fois par le même sommet

Un graphe est hamiltonien si et seulement si

• Sa fermeture est hamiltonienne

• Chaque sommet est au moins de degré |V|/2

• Chaque sommet est de degré pair

Un graphe orienté est eulérien si :

• Le degré entrant de chaque sommet est égal à son degré sortant

• Le degré entrant et le degré sortant ont une valeur au moins égale à |V|/2

Le graphe "papillon" est :

• Eulerien

• Hamiltonien