[PDF] chaine eulérienne

Qu'est-ce que la chaine eulérienne ?

Chaine simple qui passe par toutes les arêtes d’un graphe non orienté. Un graphe comporte une chaine eulérienne si le graphe est connexe et s’il comporte deux sommets d’ ordre impair. 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.

Comment parcourir une chaine eulérienne ?

Une chaine eulérienne est une chaine qui parcourt toutes les arêtes d’un graphe connexe une et une seule fois. On peut demander s’il est possible de parcourir tel trajet en n’empruntant jamais deux fois la même route : On voit que c’est possible en partant de Trois-Rivières ou Drummondville, mais pas en partant de Québec ou Montréal.

Pourquoi n’y a-t-il pas de chaine eulérienne ?

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.

Comment savoir si un graphe a une chaine eulérienne ?

Pour qu’un graphe comporte une chaine eulérienne, il faut qu’il possède 0 ou deux 2 sommets de degré impair. Dans le cas de 2 sommets de degré impair, ils seront situés au début et à la fin de la chaine. Lorsque la chaine eulérienne est fermée, on l’appellera cycle eulérien.