Algorithme de Fleury

2023-06-21

L'algorithme de Fleury est une méthode permettant de mettre en évidence le chemin Eulérien dans un graphe, utilisant chaque arête uniquement une fois.

Conditions

La première étape consiste à compter le nombre d'arêtes de chaque nœud. Pour fonctionner, est nécessaire de n'avoir que des nœuds à arêtes paires (Cycle Eulérien), ou uniquement deux nœuds avec un nombre impair d'arêtes – en quel cas l'un deux doit être utilisé comme point de départ, l'autre étant l'arrivée.

Directions

À chaque nœud, l'arête choisie ne doit pas être un pont – arête qui ne fait pas partie d'un cycle – tant qu'un de ses côté n'est pas totalement exploré. De même, chaque arête doit conduire à un nœud ayant encore des arêtes inexplorées.