Edmonds-algoritmus

A gráfelméletben az Edmonds-algoritmus vagy Chu–Liu/Edmonds-algoritmus egy olyan algoritmus, amely a minimális feszítőfa megtalálására szolgál (ezt néha optimális elágazásnak nevezik). A feszítőfa olyan irányított fa, amelyben van egy speciális, gyökérnek nevezett pont, amelyből minden pontba vezet irányított út. Ez a minimális feszítőfa probléma irányított analógja. Az algoritmust először Yoeng-Jin Chu és Tseng-Hong Liu (1965), majd Jack Edmonds (1967) javasolta.

Algoritmus

Az algoritmus bemenetként irányított gráfot kap $D=\langle V,E\rangle$ ahol $V$ a csúcsok halmaza és $E$ a irányított élek halmaza, megkülönböztetett csúcs $r\in V$ amelyet gyökérnek hívnak, és egy valós értékű súlyt (költséget) $w(e)$ minden élre $e\in E$. Visszaad egy feszítőfát $A$-t mely $r$ gyökerű, minimális súlyú (költségű), ahol a fenyő súlya (költsége) a fenyőt meghatározó élek súlyának összege $w(A)=\sum _{e\in A}{w(e)}$.

Az algoritmus rekurzív. Legyen $f(D,r,w)$ az a függvény, mely egy $r$ gyökerű, minimális súlyú (költségű) feszítőfát ad vissza. Először távolítsunk el minden élt $E$-ből ami $r$-be mutat. A párhuzamos éleket (ugyanazon irányú csúcspárok közötti élek ugyanabba az irányba) kicserélhetjük egyetlen élre is, amelynek súlya (költsége) megegyezik a párhuzamos élek súlyának minimumával.

Ezután a $v$ a gyökéren kívüli csúcsokhoz keressük meg a legkisebb súlyú (költségű) beérkező élt $v$ (több lehetőségnél bármelyiket). Legyen ennek a élnek a forrásának jele $\pi (v)$. Ha az élek halmaza $P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}$ nem tartalmaz kört, akkor $f(D,r,w)=P$.

Másképpen fogalmazva, $P$ legalább egy kört tartalmaz. Tetszőlegesen válasszunk egyet a körök közül és hívja meg $C$-re. Most meghatározunk egy új súlyozott irányított gráfot $D^{\prime }=\langle V^{\prime },E^{\prime }\rangle$ amelyben a kör $C$ "csúcsra" van kötve, a következők szerint:

A $V^{\prime }$-ben lévő csúcsok nem $C$-ben lévő csúcsai $V$-nek, és egy új csomópont jelölje $v_{C}$.

• Ha $(u,v)$ egy él a $E$-ben úgy hogy $u\notin C$ és $v\in C$ (a ciklusban lévő él), és $E^{\prime }$-ben új él $e=(u,v_{C})$, akkor $w^{\prime }(e)=w(u,v)-w(\pi (v),v)$.
• Ha $(u,v)$ egy él a $E$-ben úgy hogy $u\in C$ és $v\notin C$ (a cikluson kívül eső él), és $E^{\prime }$-ben új él $e=(v_{C},v)$, akkor $w^{\prime }(e)=w(u,v)$.
• Ha $(u,v)$ egy él a $E$-ben úgy hogy $u\notin C$ és $v\notin C$ (a cikluson kívül eső él), és $E^{\prime }$-ben új él $e=(u,v)$, akkor $w^{\prime }(e)=w(u,v)$.

$E^{\prime }$-ben minden élről tudjuk hogy melyik élnek felel meg $E$-ben.

Ezután keressük meg $D^{\prime }$-nek minimális feszítőfáját $A^{\prime }$-t sz $f(D^{\prime },r,w^{\prime })$ hívásával. Mivel $A^{\prime }$ egy feszítőfa, minden csúcsnak pontosan egy bejövő éle van. Legyen$(u,v_{C})$ legyen az egyedi bejövő él $v_{C}$ $A^{\prime }$-be. Ez az él egy élnek felel meg $(u,v)\in E$ é s$v\in C$. Távolítsuk el az élt $(\pi (v),v)$ $C$-től, megszakítva a kört. Jelöljük be az összes fennmaradó élt $C$-ben. $A^{\prime }$ minden éle megfelel egy $E$-beli élnek. Határozzuk meg $f(D,r,w)$ a megjelölt élek halmazát, amelyek minimális feszítőfát képeznek.

Vegyük figyelembe hogy $f(D,r,w)$ meghatározása az alábbiak szerint történik: $f(D^{\prime },r,w^{\prime })$, $D^{\prime }$ szigorúan kevesebb csúccsal rendelkezik, mint $D$. $f(D,r,w)$ értéke egy csúcsú gráfra triviális (éppen ez $D$ maga), tehát biztosan véget ér a rekurzív algoritmus.

Futási idő

Ennek az algoritmusnak a futási ideje: $O(EV)$. Az algoritmus gyorsabb változata Robert Tarjan implementációja $O(E\log V)$ futási idővel rendelkezik ritka gráfokra és $O(V^{2})$ sűrű gráfokra. Ez olyan gyors, mint Prim algoritmusa egy irányítatlan minimális feszítőfára. Gabow, Galil, Spencer, Compton és Tarjan 1986-ban kidolgoztak egy gyorsabb $O(E+V\log V)$ idejű algoritmust.

Irodalom

• Chu, Y. J. & Liu, T. H. (1965), "On the Shortest Arborescence of a Directed Graph", Science Sinica 14: 1396–1400
• Edmonds, J. (1967), "Optimum Branchings", Journal of Research of the National Bureau of Standards Section B 71B: 233–240
• Tarjan, R. E. (1977), "Finding Optimum Branchings", Networks 7: 25–35
• Camerini, P.M. & Fratta, L. (1979), "A note on finding optimum branchings", Networks 9: 309–312
• Gibbons, Alan (1985), Algorithmic Graph Theory Gibbons, Alan (1985), Algorithmic Graph Theory
• Gabow, H. N. & Galil, Z. (1986), "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs", Combinatorica 6: 109–122
• Frank András, Összefüggések a kombinatorikus optimalizálásban I. Optimalizálás gráfokon http://web.cs.elte.hu/~frank/cikkek/FrankJ57.PDF Archiválva 2021. április 22-i dátummal a Wayback Machine-ben (2020.05.18.)

Fordítás

Ez a szócikk részben vagy egészben az Edmonds' algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

• Edmonds algoritmus (edmonds-alg) - Edmonds algoritmusának megvalósítása, C ++ formában, és a MIT licenc alapján engedélyezett. Ez a forrás a Tarjan megvalósítását használja a sűrű gráfhoz.
• A NetworkS, a BSD alatt elosztott python könyvtár Edmonds algoritmusát valósítja meg.