Chemins Euleriens et Algorithme de Fleury

La théorie des graphes est un domaine des mathématiques que j'ai la chance d'enseigner à l'IUT de Lannion . Ce domaine est de plus en plus en vogue actuellement, certainement par ce que c'est un très bon outil de modélisation qui peut s'adapter pour résoudre de nombreux problèmes concrets. Cette caractéristique se retrouve dès l'origine de la théorie des graphes avec la résolution du problème des sept ponts de Königsberg  posé par Euler en 1735. Ce problème fait apparaître une notion très importante de théorie des graphes, la notion de graphe Eulerien  :

Définition un graphe G est

• Eulerien   s'il existe un cycle/circuit passant exactement une fois par chaque arc/arête de G.
• semi-Eulerien s'il existe un chemin/chaîne passant exactement une fois par chaque arc/arête de G.

Voici un exemple G0 de graphe non-orienté possédant un chemin Semi-Eulerien :

G0 Graphe non-orienté abvec un chemin Semi-Eulerien C=(1,2,3,1,4,5,6,4)

On a un critère très simple pour décider si un graphe est Eulerien ou pas, critère  trouvé justement par Euler pour résoudre le problème des sept ponts de Königsberg, qui repose sur le degré des sommets.

Définition Dans un graphe G le degré de chaque sommet x est

• si G est non-orienté d(x)= nombre d'arêtes connectées à x (attention les boucles comptent double!)
• si G est orienté d(x)=d⁺(x)=d^-(x) ou d⁺(x) le nombre de 'arcs "sortant" de x et d^-(x)= nombre d'arcs "entrant" en x

en considérant que dans un chemin Eulerien à chaque passage par un sommet "consomme" 2 arcs/arêtes (un pour arriver un pour repartir) sauf éventuellement pour le point de départ et d'arrivé lorsque le chemin n'est pas un circuit. On obtient alors le théorème suivant :

Théorème d'Euler un graphe G est Eulerien si et seulement si

• dans le cas où G est un graphe non-orienté chaque sommet x de G doit avoir un degré d(x) pair
• dans le cas où G est un graphe orienté chaque sommet x de G doit avoir des degrés entrants et sortants égaux d⁺(x)=d^-(x)

si deux sommets de G ne vérifient pas le critère ci-dessus alors le graphe est semi-Eulerien et les deux points en question sont les extrémités d'un chemin semi-Eulerien .

dans notre exemple les calculs sont assez faciles :

x	1	2	3	4	5	6
d(x)	3	2	2	3	2	2

On déduit de ce théorème que pour rendre un graphe Eulerien il suffit de lui ajouter des arcs/arêtes et éventuellement des sommets si on ne veut pas avoir d'arêtes multiples entres sommets (plusieurs arcs/arêtes différentes entre deux sommets x et y).

Algorithme rendre_Eulerien(G) 
tant que G n'est pas (semi-)Eulerien
             chercher deux sommets x,y ne vérifiant pas le critère d'Euler
             si (x,y) n'est pas un arc/arête de G
                        alors ajouter cet arc/arête à G
                        sinon ajouter un sommet z à G et ajouter les arcs/arêtes (x,z) et (z,y) à G

Cependant le théorème d'Euler ne résout pas en lui même le problème de trouver un chemin (semi-)Eulerien d'un graphe donné. On peut facilement trouver des chemins Eulerien en cheminant au hasard dans le graphe mais pour cela il faut éviter de couper le graphe en plusieurs composantes connexes! Les arêtes qui risquent de produire une telle coupure sont appelées des ponts du graphe.

Définition un pont du graphe G est un arc/arête tel que enlever cet arc/arête de G augmente le nombre de composantes (fortement)-connexes  de G

sur le graphe G0 l'arête {1;4} est un pont, c'est pour cela qu'en partant du sommet 1, pour trouver un chemin Eulerien, on ne doit pas commencer par parcourir l'arête {1;4} sinon on isolerai dès le départ les sommets 2 et 3 ainsi que les arêtes adjacentes! C'est à partir de cette définition d'un pont que l'on peut exprimer simplement l'algorithme de recherche d'un chemin (semi-)Eulerien :

Algorithme de Fleury : pour trouver un chemin (semi-)Eulerien de G  il suffit de parcourir les arcs/arête en prenant prioritairement ceux qui ne sont pas des ponts de G.

en langage de description ça donne à peu près ça :

Algorithme  C=Fleury(G)
si G est un  graphe Eulerien
             alors partir de n'importe quel sommet x de G
             sinon partir de x un des deux sommets ne vérifiant pas le critère d'Euler

initialiser le chemin a C=(x)
tant que G possède au moins un arc/arête  
            pour chaque y successeur de  x dans G
                      si (x,y) n'est pas un pont alors sortir
              en sortie  (x,y) est donc un arc/arête de G
              qui n'est un pont que s'il n'y a pas d'autre choix
             ajouter y à la fin du chemin C
             détruire l'arc/arête (x,y) de G
              x=y

L'implémentation de l'algorithme en langage  scilab est assez similaire que le graphe soit orienté ou pas.Voici une deuxième   animations  montrant la construction d'un chemin (orienté cette fois)  via l'algorithme de Fleury pour le graphe orienté suivant :

Chemin Eulerien C=(1,8,5,1,7,3,8,7,6,2,5,3,2,3,6,4,7,4,2,1)  pour le graphe orienté G1

On peut vérifier que le graphe est bien Eulerien à partir des degrés des sommets :

x	1	2	3	4	5	6	7	8
d+(x)	2	3	3	2	2	2	3	2
d-(x)	2	3	3	2	2	2	3	2