Stöhr-Wagner algoritmus

A Stöhr-Wagner algoritmus egy rekurzív algoritmus a legkevesebb vágott probléma megoldására irányítatlan súlyozott gráfokban , amelyek nullától eltérő súllyal rendelkeznek. Az algoritmust Mechthild Stöhr és Frank Wagner javasolta 1995-ben. Ennek az algoritmusnak az a fő ötlete, hogy a gráfot a legintenzívebb csúcsok összevonásával addig zsugorítsa, amíg a gráf csak két kombinált (az egyesülés eredménye) csúcsot tartalmaz [2] . Az algoritmus minden fázisban rendelkezik egy minimális st vágással bármely két s és t csúcsra . Az algoritmus ezután kivonja az s és t közötti élt , hogy olyan vágást találjon, amely nem tartalmazza az st élt. Az összes fázisban található legkisebb vágás lesz a grafikon minimális súlyozott vágása.

Definíciók

A vágás a gráf csúcsainak két szétválasztott részhalmazra való felosztása. A legkisebb vágás olyan vágás, amelynek mérete vagy súlya nem nagyobb, mint egy másik vágás mérete vagy súlya. Súlyozatlan gráf esetén a legkisebb vágás a legkevesebb éllel. Súlyozott gráf esetén az összes vágott él súlyának összege határozza meg, hogy a vágás a legkisebb. A gyakorlatban a legkisebb vágási problémát mindig a maximális áramlási problémával tárgyaljuk , amely a maximális hálózati áteresztőképességet, mivel a legkisebb vágás a szűk keresztmetszet egy gráfban vagy hálózatban.

Az st csúcsok esetében a vágás az s és t csúcsokat elválasztó vágás . A minimális vágás a minimális súlyú st vágás . $s,t\in V$

A legkisebb vágás Stöhr-Wagner algoritmusa

Legyen egy súlyozott irányítatlan gráf. Legyen a G gráf globális minimális metszete . Tegyük fel, hogy . Ha az s vagy t csúcsok közül pontosan egy S -hez tartozik , akkor a G [3] :95 gráf minimális st metszete is . $G=(V,E,w)$ $(UTCA)$ $s,t\in V$ $(UTCA)$

Ez az algoritmus azzal kezdődik, hogy megkeresi G minimális st vágását két csúcsra . Egy csúcspár esetében két különböző helyzet létezik - a G gráf globális minimális metszete, vagy a G gráf globális minimális vágásának ugyanahhoz a részéhez tartoznak . Ezért a globális minimális vágást a gráf vizsgálatával találhatjuk meg , amely az s és t csúcsok egyesítése utáni gráf . Egyesítés során, ha s és t egy éllel vannak összekötve, az él eltűnik. Ha s -nek és t -nek is van éle valamelyik v csúcshoz , akkor az új st csúcsból v - be tartó él súlya [3] . Az algoritmus leírása a következő [2] : $(UTCA)$ $\left\{s,t\right\}\in V$ ${\displaystyle \left\{s,t\right\))$ $(UTCA)$ $G/\left\{s,t\right\}$ $w(s,v)+w(t,v)$

MinimumCutPhase ${\megjelenítési stílus (G,w,a)}$

A\gets\left\{a\right\}

míg a leginkább kapcsolódó csúcsot hozzáadjuk A -hoz

\ A\neq V

ne feledje a fázisvágást és csökkentsük G -t az utoljára hozzáadott két csúcs összevonásával

MinimumCut ${\megjelenítési stílus (G,w,a)}$

míg a MinimumCutPhase , ha a fázisvágás könnyebb, mint az aktuális legkisebb vágás, akkor a fázisvágást az aktuális legkisebb vágásként jegyezze meg

|V|>1

{\megjelenítési stílus (G,w,a)}

Az algoritmus több fázisban működik. A MinimumCutPhase fázisban a gráfcsúcsok A részhalmaza egy tetszőleges egyedi csúcstól kezdve növekszik, amíg A egyenlő nem lesz V -vel . Minden lépésben hozzáadunk egy olyan csúcsot, amely nem tartozik A - hoz, de a legszorosabb kapcsolatban áll A - val . Ezt az eljárást formálisan a következőképpen írhatjuk fel: [2] : adjunk hozzá egy csúcsot úgy, hogy , ahol az A és y közötti élek súlyának összege . Így egyetlen fázisban definiálunk egy s és t csúcspárt, valamint egy minimális st vágást C [4] . Egy MinimumCutPhase fázis után a két csúcsot egy új csúcsba egyesítjük, és a két csúcstól a többi csúcsig tartó éleket az előző két él súlyának összegével helyettesítjük. A csomópontokat összekötő élek eltávolításra kerülnek. Ha G -nek van egy legkisebb metszete, amely elválasztja s -t és t -t , akkor C a G legkisebb metszete . Ha nem, akkor a G legkisebb metszésének s -nek és t - nek kell lennie ugyanazon az oldalon. Ezért az algoritmus egy csomópontba egyesíti őket. Ezenkívül a MinimumCut minden MinimumCutPhase hívás után írja és frissíti a globális legkisebb vágást. A fázisok után a legkisebb vágást találjuk [4] . $z\notin A$ ${\displaystyle w(A,z)=\max\{w(A,y\mid y\notin A)\))$ $w(A,y)$ $n-1$

Példa

Az 1. lépésben szereplő gráf az eredeti G gráfot reprezentálja , és a véletlenszerűen kiválasztott 2. csomópont szolgál kiindulópontként ehhez az algoritmushoz. A MinimumCutPhase fázisban az A halmaz csak a 2. csomópontot tartalmazza, melynek legnehezebb éle a (2,3) él, ezért a 3. csomópontot hozzáadjuk A -hoz . Most az A halmaz tartalmazza a 2-es és 3-as csomópontokat, a legnehezebb él pedig (3,4), így a 4-es csomópont hozzáadódik az A halmazhoz . Ezt az eljárást követően az 5-ös és 1-es csomópont lesz az utolsó belépő csomópont, amely az s csúcsok lesznek. és t ebben a fázisban. Egyesítésük után (a 15. csomóponthoz) egy új gráfot kapunk a 2. lépéshez. Ebben a fázisban a vágás súlya 5, ami az (1,2) és (1,5) élek súlyának összege. ). Az első MinimumCut ciklus befejeződött.

A 2. lépésben a 2. csomóponttól kezdve a legnehezebb él (2,15), így a 15. csomópont hozzáadódik az A halmazhoz . A következő legnehezebb él a (2,3) vagy (15,6), mi választjuk (15,6), így a 6. csomópont hozzáadódik a halmazhoz. Most összehasonlítjuk a (2,3) és (6,7) éleket, és kiválasztjuk a 3. csomópontot az A halmazba . Az utolsó két csomópont a 7 és a 8 lesz. Ezért összehúzzuk az élt (7,8). A legkisebb vágás 5, tehát minimális marad.

A következő lépések ugyanazokat a gráfösszehúzási műveleteket ismétlik, amíg csak egy él marad. A globális legkisebb vágásnak van egy éle (2,3) és egy éle (6,7), amelyet az 5. lépésben találunk.

A helyesség igazolása

Az algoritmus helyességének bizonyításához bizonyítanunk kell, hogy a MinimumCutPhase megadja a gráf tényleges minimális st metszetét , ahol s és t a fázis utolsóként hozzáadott két csúcsa. Alább a lemma:

1. lemma : A MinimumCutPhase a G minimális st vágását adja vissza .

A lemmát indukcióval igazoljuk az aktív csúcsok halmazán. Legyen tetszőleges st vágás, és legyen CP a fázisvágás. Ezt meg kell mutatnunk . Jegyezzük meg, hogy a MinimumCutPhase egy lefutása a gráf összes csúcsának permutációját adja (ahol a az első csúcs, az s és t pedig az ebben a fázisban hozzáadott utolsó két csúcs). Azt mondjuk, hogy egy v csúcs akkor aktív , ha a v előtti csúcsok a MinimumCutPhase eljárással kapott csúcsvágási sorrendben -ben vannak , vagy fordítva. Úgy definiáljuk , mint a v előtti A - hoz hozzáadott csúcsok halmazát , és ez lesz a C vágása által generált halmaz metszete . Minden aktív csúcsra v $C=(X,{\overline {X)))$ $W(C)\geqslant W(CP)$ $v\in X$ $\overline {X}$ ${\displaystyle A_{v))$ $Önéletrajz$ $A_{v}\cup \{v\}$

w(A_{v},v)\leq w(C_{v})

Legyen az első aktív csúcs. Értelemszerűen ez a két mennyiség és egyenértékű. Egyszerűen csak az A -hoz hozzáadott összes csúcsot értjük , és az ezen csúcsok közötti éleket, amelyek metszik a C vágást . Ezért, amint fentebb látható, az u és v aktív csúcsok esetén ( v hozzáadva A -hoz u előtt ), $v_{0}$ $w(A_{v_{0)),v_{0})$ $w(C_{v_{0)))$ $A_{v_{0))$ $v_{0}$ $v_{0}$

w(A_{u},u)=w(A_{v},u)+w(A_{u}-A_{v},u)

w(A_{u},u)\leq w(C_{v})+w(A_{u}-A_{v},u)

indukcióval

w(A_{v},u)\leq w(A_{v},v)\leq w(C_{v})

w(A_{u},u)\leq w(C_{u})

, mert hozzájárul, de nem (és a többi élnek nem negatív súlya van)

w(A_{u}-A_{v},u)

w(C_{u})

w(C_{v})

Ekkor, mivel t mindig az aktív csúcs, mivel az utolsó fázisvágás elválasztja s - t t -től , definíció szerint bármely t aktív csúcsra

w(A_{t},t)\leq w(C_{t})=w(C)

Így a fázisvágás nem haladja meg a C súlyt .

Időbonyolultság

A MinimumCut algoritmus időbonyolultsága megegyezik a MinimumCutPhase eljárás teljes futási idejével , amelyet egy csökkenő számú csúcs- és élszámú gráfon hívunk meg. $|V|-1$

A MinimumCutPhase eljárás egyetlen futtatása nem igényel több időt. $O(|E|+|V|\log |V|)$

Ezért a teljes időnek két fázis szorzatának kell lennie, ami [2] . $O(|V||E|+|V|^{2}\log |V|)$

A további fejlesztés érdekében könnyűnek kell lennie kiválasztani a következő csúcsot az A halmazhoz , vagyis a legerősebben kapcsolódó csúcsot. Amikor a fázis végrehajtódik, minden olyan csúcs, amely nincs A -ban, a kulcsmező alapján prioritási sorba kerül. A V csúcs kulcsa az A jelenlegi halmazzal összekötő élek súlyainak összege , azaz . Amikor a v csúcsot hozzáadjuk az A halmazhoz , frissítenünk kell a sort. A v csúcsot el kell távolítani a sorból, és a v-hez tartozó összes w csúcs kulcsát meg kell növelni a vw él súlyával , ha van ilyen. Mivel ez minden élnél pontosan egyszer történik meg, csak az ExtractMax és IncreaseKey műveleteket kell tennünk. A Fibonacci kupac segítségével az ExtractMax műveletet amortizált időben , az IncreaseKey műveletet pedig amortizált időben tudjuk végrehajtani [5] . Tehát az idő, amire szükségünk van, hogy befejezzük ezt a kulcsfontosságú fázislépést, amely uralja a többit: [2] . $w(A,v)$ $|V|$ $|E|$ $O(\log |V|)$ $O(1)$ $O(|E|+|V|\log |V|)$

Jegyzetek

↑ Boost Graph Library: Stoer–Wagner Min-Cut - 1.46.1 . www.boost.org . Hozzáférés dátuma: 2015. december 7. Az eredetiből archiválva : 2015. szeptember 19. (határozatlan)
↑ 1 2 3 4 5 Egy egyszerű minimális vágási algoritmus . Letöltve: 2019. április 15. Az eredetiből archiválva : 2017. december 8.. (határozatlan)
↑ 1 2 "Lecture notes for Analysis of Algoritms": Globális minimális csökkentés . Letöltve: 2019. április 15. Az eredetiből archiválva : 2019. október 5.. (határozatlan)
↑ 1 2 Stoer és Wagner minimális vágási algoritmusa . Letöltve: 2019. április 15. Az eredetiből archiválva : 2019. március 3. (határozatlan)
↑ Az amortizált idő lényegében azt jelenti, hogy "az a tevékenységgel töltött átlagos idő, ha sok tevékenységet végez".