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.

Az algoritmus bemenetként irányított gráfot kap ${\displaystyle D=\langle V,E\rangle }$ ahol ${\displaystyle V}$ a csúcsok halmaza és ${\displaystyle E}$ a irányított élek halmaza, megkülönböztetett csúcs ${\displaystyle r\in V}$ amelyet gyökérnek hívnak, és egy valós értékű súlyt (költséget) ${\displaystyle w(e)}$ minden élre ${\displaystyle e\in E}$. Visszaad egy feszítőfát ${\displaystyle A}$-t mely ${\displaystyle 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 ${\displaystyle w(A)=\sum _{e\in A}{w(e)}}$.

Az algoritmus rekurzív. Legyen ${\displaystyle f(D,r,w)}$ az a függvény, mely egy ${\displaystyle 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 ${\displaystyle E}$-ből ami ${\displaystyle 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 ${\displaystyle v}$ a gyökéren kívüli csúcsokhoz keressük meg a legkisebb súlyú (költségű) beérkező élt ${\displaystyle v}$ (több lehetőségnél bármelyiket). Legyen ennek a élnek a forrásának jele ${\displaystyle \pi (v)}$. Ha az élek halmaza ${\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}}$ nem tartalmaz kört, akkor ${\displaystyle f(D,r,w)=P}$.

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

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

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

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

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

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

Ennek az algoritmusnak a futási ideje: ${\displaystyle O(EV)}$. Az algoritmus gyorsabb változata Robert Tarjan implementációja ${\displaystyle O(E\log V)}$ futási idővel rendelkezik ritka gráfokra és ${\displaystyle 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 ${\displaystyle O(E+V\log V)}$ idejű algoritmust.

• 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.)

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.

• 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.