Algorhytme de Fleury
On sait déjà ce que sont les graphes eulériens et comment les reconnaître. Maintenant on va étudier comme trouver ces chemins dans des graphes eulériens. Pour faire cela on utilisera l'Algorithme de Fleury apparu en 1883.Pour expliquer cet algorithme on va poser un exemple avec un graphe eulérien:
D’abord on vérifie que le graphe est eulérien:
-
tous ses sommets ont degré par puisque:
grA=4 grB=2 grC=4 grD=2 grE=2 grF=2
Comme cela s'accomplit, on peut déjà savoir que le graphe est eulérien et alors, il contient un chemin eulérien. Pour trouver ce chemin il faut suivre un ensemble de pas:
-
On trouve un circuit fermé dans le graphe. Un circuit fermé est celui qui commence et finit dans le même sommet et ne répète pas arêtes. Alors on peut voir que le circuit le plus visible c’est le suivant: C= [D,A,B,C,F,D].
2.On peut voir qu’il manquent encore des arêtes pour compléter le chemin, bien qu’il faut passer par toutes les arêtes du graphe. Donc, on prend un des sommets qui est dans le circuit fermé, mais qui soit adjacent aux arêtes qui manquent dans le chemin, et on construit des là un autre circuit. On peut choisir les sommets A ou C. Dès A on peut former le circuit: C=[A,C,E,A].On peut dire que ce circuit c’est un sous graphe du graphe original.
3.Ensuite ce qu’on doit faire c’est substituer dans le premier circuit dans le point ou on arrive au sommet A, on met le deuxième circuit. Donc le circuit final aura ce trajet: C=[D,A,E,C,A,B,C,F,D].
On peut prouver que c’est circuit est un chemin eulérien en faisant une preuve très simple: si on peut dessiner ce graphe sans tracer deux fois la même ligne, en sans lever le crayon du papier, c’est que c’est un circuit eulérien. Et en plus c’est un cycle eulérien aussi, puisqu’il est fermé car il commence et finit au même sommet.
Avec cet algorithme on peut tracer des routes qui passent par toutes les arêtes d’un graphe mais une seule fois pour chacune. Il peut être très utile dans le champ des transports, comme par exemple le cas d’un facteur ou aussi pour dessiner des routes de transport urbain.
