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=⟨V,E⟩$ 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 }=⟨V^{\prime },E^{\prime }⟩$ 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

• Sablon:Citation
• Sablon:Citation
• Sablon:Citation
• Sablon:Citation
• Sablon:Citation Sablon:Citation
• Sablon:Citation
• 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 Sablon:Wayback (2020.05.18.)

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.