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[szerkesztés]

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ő[szerkesztés]

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[szerkesztés]

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[szerkeszté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[szerkesztés]

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.