chaine eulérienne

chaine eulérienne

Chaine simple qui passe par toutes les arêtes d’un graphe non orienté.

Propriété

Un graphe comporte une chaine eulérienne si le graphe est connexe et s’il comporte deux sommets d’ordre impair.

Exemple

Dans le graphe ci-dessous, il n’existe pas de chaine eulérienne parce qu’il y a plus de deux sommets d’ordre impair.

 

Le graphe ci-dessous possède une chaine eulérienne en suivant les sommets dans l’ordre suivant : B – A – E – D – C – B – E.


Noter que la chaine eulérienne ci-dessus débute à un sommet d’ordre impair (B) et se termine à l’autre sommet d’ordre impair (E).