Algorithme de Chu-Liu/Edmonds

En théorie des graphes, l'algorithme d'Edmonds ou algorithme de Chu-Liu/Edmonds est un algorithme fournissant une arborescence couvrante de poids minimal dans un graphe. Il s'agit de la version orientée d'un arbre couvrant de poids minimal. L'algorithme a été proposé indépendamment par Yoeng-Jin Chu et Tseng-Hong Liu (1965), puis par Jack Edmonds (1967).

Algorithme

Description

L'algorithme prend en entrée un graphe orienté $G=\langle V,E\rangle$ où $V$ est l'ensemble des sommets et $E$ est l'ensemble des arcs. Soit un sommet $r$ appelé la racine, et une valeur réelle de poids $w(e)$ pour chaque arc $e\in E$. L'algorithme renvoie une arborescence couvrante de poids minimal $A$ ancrée à la racine $r$, le poids d'une arborescence étant défini comme la somme des poids des arcs, $w(A)=\sum _{e\in A}w(e)$.

L'algorithme peut être exécuté de manière récursive. Soit $f(G,r,w)$ la fonction qui retourne une arborescence couvrante de poids minimal ancrée à la racine . On commence par supprimer tous les arcs de $E$ dont la destination est $r$. On remplace également tous les ensembles d'arcs parallèles (les arcs ayant la même origine et la même destination) par un seul arc avec un poids égal au poids minimal de l'ensemble associé.

Maintenant, pour chaque sommet $v$ autre que la racine, on prend l'arc de poids le plus faible dont la destination est $v$. On appelle l'origine de cet arc $\pi (v)$. Si l'ensemble d'arcs $P=\{(\pi (v),v)\mid v\in V\setminus r\}$ ne contient pas de cycles, alors $f(G,r,w)=P$.

Sinon, $P$ contient au moins un cycle. On choisit arbitrairement l'un de ces cycles. Soit $C$ ce cycle. Nous allons maintenant définir un nouveau graphe orienté et pondéré $G'=\langle S',E'\rangle$ dans lequel le cycle $C$ est "contracté" dans un seul sommet comme suit :

Les sommets de $V'$ sont les sommets de $V\setminus C$ plus un nouveau sommet dénoté $v_{C}$.

• Si $(u,v)$ est un arc de $E$ avec $u\notin C$ et $v\in C$ (un arc entrant dans le cycle), alors on inclut dans $E^{\prime }$ un nouvel arc $e=(u,v_{C})$, et on définit $w^{\prime }(e)=w(u,v)-w(\pi (v),v)$.
• Si $(u,v)$ est un arc de $E$ avec $u\in C$ et $v\notin C$ (un arc sortant du cycle), alors on inclut dans $E^{\prime }$ un nouvel arc $e=(v_{C},v)$, et on définit $w^{\prime }(e)=w(u,v)$.
• Si $(u,v)$ est un arc de $E$ avec $u\notin C$ et $v\notin C$ (un arc non-relié au cycle), alors on inclut dans $E^{\prime }$ un nouvel arc $e=(u,v)$, et on définit $w^{\prime }(e)=w(u,v)$.

Pour chaque arc de $E'$, on garde en mémoire l'arc de $E$ auquel il correspond.

Maintenant, on récupère une arborescence couvrante de poids minimal $A^{\prime }$ pour $G'$ en appelant $f(G',r,w')$. Comme $A^{\prime }$ est une arborescence couvrante, chacun de ses sommets a exactement un arc entrant. Soit $(u,v_{C})$ l'unique arc de $A'$ entrant dans $v_{C}$. Cet arc correspond à un arc $(u,v)\in E$ avec $v\in C$. On supprime $(\pi (v),v)$de $C$, pour briser le cycle. On garde tous les autres arcs de $C$. Pour chaque arc dans $A^{\prime }$, on garde son arc correspondant dans $E$. Maintenant, $f(G,r,w)$ est défini par les arcs que nous avons gardés, qui forment une arborescence couvrante de poids minimal.On note que $f(G,r,w)$ est défini à l'aide de $f(G',r,w')$, avec $G'$ ayant strictement moins de sommets que $G$. Trouver $f(G,r,w)$ pour un graphe contenant un seul sommet est trivial (il s'agit de $G$ lui-même), ainsi la terminaison de l'algorithme est garantie.

Complexité de l'algorithme

La complexité en temps de cet algorithme est $O(EV)$. Une implémentation plus rapide de l'algorithme a été élaborée par Robert Tarjan et a une complexité en temps $O(E\log V)$ pour un graphe creux et $O(V^{2})$ pour un graphe dense. C'est aussi rapide que l'algorithme de Prim pour un arbre couvrant de poids minimal non-orienté. En 1986, Gabow, Galil, Spencer, Compton, et Tarjan ont élaboré une implémentation plus rapide, avec une complexité en temps $O(E+V\log V)$.

Références

• Chu, Y. J. et Liu, T. H., « On the Shortest Arborescence of a Directed Graph », Science Sinica, vol. 14,‎ 1965, p. 1396–1400
• Edmonds, J., « Optimum Branchings », J. Res. Nat. Bur. Standards, vol. 71B,‎ 1967, p. 233-240 (DOI 10.6028/jres.071b.032)
• Tarjan, R. E., « Finding Optimum Branchings », Networks, vol. 7,‎ 1977, p. 25-35 (DOI 10.1002/net.3230070103)
• Camerini, P.M., Fratta, L. et Maffioli, F., « A note on finding optimum branchings », Networks, vol. 9,‎ 1979, p. 309–312 (DOI 10.1002/net.3230090403)
• Gibbons, Alan, « Algorithmic Graph Theory », Cambridge University press,‎ 1985 (ISBN 0-521-28881-9)
• Gabow, H. N., Galil, Z., Spencer, T. et Tarjan, R. E., « Efficient algorithms for finding minimum spanning trees in undirected and directed graphs », Combinatorica, vol. 6,‎ 1986, p. 109–122 (DOI 10.1007/bf02579168)

Liens externes

• Algorithme d'Edmonds ( edmonds-alg ) – Une implémentation open source de l'algorithme d'Edmonds écrite en C++ et sous Licence MIT. Cette source utilise l'implémentation de Tarjan pour les graphes denses.