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 ahol
a csúcsok halmaza és
a irányított élek halmaza, megkülönböztetett csúcs
amelyet gyökérnek hívnak, és egy valós értékű súlyt (költséget)
minden élre
. Visszaad egy feszítőfát
-t mely
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
.
Az algoritmus rekurzív. Legyen az a függvény, mely egy
gyökerű, minimális súlyú (költségű) feszítőfát ad vissza. Először távolítsunk el minden élt
-ből ami
-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 a gyökéren kívüli csúcsokhoz keressük meg a legkisebb súlyú (költségű) beérkező élt
(több lehetőségnél bármelyiket). Legyen ennek a élnek a forrásának jele
. Ha az élek halmaza
nem tartalmaz kört, akkor
.
Másképpen fogalmazva, legalább egy kört tartalmaz. Tetszőlegesen válasszunk egyet a körök közül és hívja meg
-re. Most meghatározunk egy új súlyozott irányított gráfot
amelyben a kör
"csúcsra" van kötve, a következők szerint:
A -ben lévő csúcsok nem
-ben lévő csúcsai
-nek, és egy új csomópont jelölje
.
- Ha
egy él a
-ben úgy hogy
és
(a ciklusban lévő él), és
-ben új él
, akkor
.
- Ha
egy él a
-ben úgy hogy
és
(a cikluson kívül eső él), és
-ben új él
, akkor
.
- Ha
egy él a
-ben úgy hogy
és
(a cikluson kívül eső él), és
-ben új él
, akkor
.
-ben minden élről tudjuk hogy melyik élnek felel meg
-ben.
Ezután keressük meg -nek minimális feszítőfáját
-t sz
hívásával. Mivel
egy feszítőfa, minden csúcsnak pontosan egy bejövő éle van. Legyen
legyen az egyedi bejövő él
-be. Ez az él egy élnek felel meg
é s
. Távolítsuk el az élt
-től, megszakítva a kört. Jelöljük be az összes fennmaradó élt
-ben.
minden éle megfelel egy
-beli élnek. Határozzuk meg
a megjelölt élek halmazát, amelyek minimális feszítőfát képeznek.
Vegyük figyelembe hogy meghatározása az alábbiak szerint történik:
,
szigorúan kevesebb csúccsal rendelkezik, mint
.
értéke egy csúcsú gráfra triviális (éppen ez
maga), tehát biztosan véget ér a rekurzív algoritmus.
Futási idő
Ennek az algoritmusnak a futási ideje: . Az algoritmus gyorsabb változata Robert Tarjan implementációja
futási idővel rendelkezik ritka gráfokra és
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
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.