|
|
L’algorithme d’Euler permet de trouver explicitement, lorsque cela est possible, une chaîne eulérienne dans un graphe.
Les conditions d’existence d’un parcours eulérien sont données par le théorème :
|
· Un graphe connexe admet une chaîne eulérienne si le nombre de sommets de degré impair est 0 ou 2. · Un graphe connexe admet un cycle eulérien si tous ses sommets sont de degré pair. |
Exemple de mise en œuvre sur le graphe ci-dessous : départ en D et arrivée en A
On s’assurera au préalable que ce graphe admet une chaîne eulérienne en calculant l’ordre de chaque sommet
|
|
Chaînes fermées |
Chaîne eulérienne |
|
Étape 1 |
|
D B C A |
|
Étape 2 |
A E K A |
D B C A E K A |
|
Étape 3 |
D F A D |
D F A D B C A E K A |
|
Étape 4 |
F G H E F |
D F G H E F A D B C A E K A |
|
Étape 5 |
G I L J I H J G |
D F G I L J I H J G H E F A D B C A E K A |
|
Étape 6 |
K J M K |
D F G I L J I H J G H E F A D B C A E K J M K A |
Cet algorithme ne conduit pas à une solution unique : le choix de la chaîne de départ et des chaînes fermées est arbitraire.