Stöhr-Wagner-algoritmi

Stöhr-Wagner- algoritmi on rekursiivinen algoritmi vähiten leikatun ongelman ratkaisemiseksi ohjaamattomissa painotetuissa graafisissa nollasta poikkeavilla painoilla. Algoritmia ehdottivat Mechthild Stöhr ja Frank Wagner vuonna 1995. Tämän algoritmin pääideana on kutistaa graafia yhdistämällä voimakkaimmat kärjet, kunnes graafi sisältää vain kaksi yhdistettyä (liiton tulos) kärkeä [2] . Algoritmilla on jokaisessa vaiheessa pienin st -leikkaus kahdelle pisteelle s ja t . Algoritmi vähentää sitten s:n ja t :n välisen reunan löytääkseen reunan st , joka ei sisälläviilto. Pienin kaikista vaiheista löydetty leikkaus on kaavion pienin painotettu leikkaus.

Määritelmät

Leikkaus on graafin kärkien osio kahdeksi erilliseksi osajoukoksi. Pienin leikkaus on leikkaus, jonka koko tai paino ei ole suurempi kuin toisen leikkauksen koko tai paino. Painottamattomassa kaaviossa pienin leikkaus, jolla on vähiten reunoja. Painotetussa kaaviossa kaikkien leikkausreunojen painojen summa määrittää, onko leikkaus pienin. Käytännössä pienin leikkausongelma käsitellään aina maksimivirtausongelman kanssa, joka tutkii verkon maksimiläpäisykykyä, koska pienin leikkaus on graafin tai verkon pullonkaula.

Huippupisteissä st leikkaus on pisteet s ja t erottava leikkaus . Minimileikkaus on st - leikkaus, jonka paino on pienin . $s,t\in V$

Pienimmän leikkauksen Stöhr-Wagner-algoritmi

Antaa olla painotettu suuntaamaton graafi. Olkoon graafin G globaali minimileikkaus . Oletetaan, että . Jos täsmälleen yksi pisteistä s tai t kuuluu S :ään , on myös graafin G [3] :95 pienin st -leikkaus . $G=(V,E,w)$ $(S,T)$ $s,t\in V$ $(S,T)$

Tämä algoritmi alkaa etsimällä G : n minimileikkaus kahdelle kärjelle . Huippuparilla on kaksi eri tilannetta - onko graafin G globaali minimileikkaus tai ne kuuluvat samaan osaan graafin G globaalia minimileikkausta . Siksi globaali minimileikkaus voidaan löytää tarkastelemalla graafia , joka on graafi sen jälkeen, kun kärjet s ja t on yhdistetty . Jos yhdistämisen aikana s ja t on yhdistetty reunalla, reuna katoaa. Jos sekä s:llä että t :llä on reuna johonkin kärkeen v , niin uudesta kärjestä st pisteeseen v tulevan reunan paino on [3] . Algoritmi kuvataan seuraavasti [2] : $(S,T)$ $\left\{s,t\right\}\in V$ $\left\{s,t\right\}$ $(S,T)$ $G/\left\{s,t\right\}$ $w(s,v)+w(t,v)$

MinimumCutPhase ${\näyttötyyli (G,w,a)}$

{\displaystyle A\gets\left\{a\right\))

ja lisää eniten yhteydessä oleva huippupiste A :han

\ A\neq V

muista leikkausvaihe ja pienennä G yhdistämällä viimeksi lisätyt kaksi kärkeä

MinimumCut ${\näyttötyyli (G,w,a)}$

kun taas MinimumCutPhase , jos vaiheen leikkaus on kevyempi kuin nykyinen pienin leikkaus , muista katkaisuvaihe nykyisenä pienimpänä leikkauksena

|V|>1

{\näyttötyyli (G,w,a)}

Algoritmi toimii useissa vaiheissa. MinimumCutPhase-vaiheessa graafin kärkien osajoukko A kasvaa mielivaltaisesta yksittäisestä kärjestä alkaen, kunnes A on yhtä suuri kuin V . Jokaisessa vaiheessa joukkoon A lisätään kärki, joka ei kuulu A :han, mutta joka liittyy läheisimmin A :han . Tämä menettely voidaan kirjoittaa muodossa [2] : lisää kärkipiste , jolloin , missä on kaikkien A:n ja y :n välisten reunojen painojen summa . Siten yhdessä vaiheessa määritellään pari pisteitä s ja t sekä pienin st - leikkaus C [4] . Yhden MinimumCutPhase-vaiheen jälkeen kaksi kärkeä yhdistetään uudeksi kärjeksi ja kahdesta pisteestä jäljellä oleviin kärkipisteisiin korvataan reuna, jossa on kahden edellisen reunan painojen summa. Solmuja yhdistävät reunat poistetaan. Jos G :stä on pienin leikkaus, joka erottaa s :n ja t :n , C on G :n pienin leikkaus . Jos ei, G :n pienimmässä leikkauksessa on oltava s ja t samalla puolella. Siksi algoritmi yhdistää ne yhdeksi solmuksi. Lisäksi MinimumCut kirjoittaa ja päivittää globaalin pienimmän leikkauksen jokaisen MinimumCutPhase-kutsun jälkeen. Vaiheiden jälkeen löydetään pienin leikkaus [4] . $z\notin A$ ${\displaystyle w(A,z)=\max\{w(A,y\mid y\notin A)\))$ $w(A,y)$ $n-1$

Esimerkki

Vaiheen 1 kuvaaja edustaa alkuperäistä graafia G , ja satunnaisesti valittu solmu 2 toimii tämän algoritmin aloitussolmuna. MinimumCutPhase-vaiheessa joukko A sisältää vain solmun 2, jonka raskain reuna on reuna (2,3), joten lisäämme solmun 3 A :han . Nyt joukko A sisältää solmut 2 ja 3 ja raskain reuna on (3,4), joten solmu 4 lisätään joukkoon A. Tämän toimenpiteen jälkeen solmu 5 ja 1 ovat viimeinen solmu, joka tulee solmuksi s . ja t tässä vaiheessa. Niiden yhdistämisen jälkeen (solmuun 15) saadaan uusi graafi vaiheelle 2. Tässä vaiheessa leikkauksen paino on 5, joka on reunojen (1,2) ja (1,5) painojen summa. ). Ensimmäinen MinimumCut-sykli on valmis.

Vaiheessa 2 alkaen solmusta 2 raskain reuna on (2,15), joten solmu 15 lisätään joukkoon A. Seuraavaksi painavin reuna on (2,3) tai (15,6), valitsemme (15,6), joten solmu 6 lisätään joukkoon. Nyt verrataan reunoja (2,3) ja (6,7) ja valitaan solmu 3 sisällytettäväksi joukkoon A . Kaksi viimeistä solmua ovat 7 ja 8. Siksi supistamme reunaa (7,8). Pienin leikkaus on 5, joten se pysyy minimaalisena.

Seuraavat vaiheet toistavat samoja graafin supistusoperaatioita, kunnes jäljellä on vain yksi reuna. Globaalilla pienimmällä leikkauksella on reuna (2,3) ja reuna (6,7), joka löytyy vaiheessa 5.

Todiste oikeellisuudesta

Algoritmin oikeellisuuden todistamiseksi on todistettava, että MinimumCutPhase antaa graafin todellisen minimileikkauksen , jossa s ja t ovat kaksi vaiheen viimeiseksi lisättyä kärkeä. Alla on lemma:

Lemma 1 : MinimumCutPhase palauttaa G : n vähimmäisleikkauksen .

Todistamme lemman induktiolla aktiivisten pisteiden joukossa. Olkoon mielivaltainen st - leikkaus ja olkoon CP vaiheleikkaus. Meidän on näytettävä se . Huomaa, että yksi MinimumCutPhase-ajo antaa permutaation kaikille graafin pisteille (jossa a on ensimmäinen kärkipiste ja s ja t ovat kaksi viimeistä tähän vaiheeseen lisättyä kärkeä). Sanomme, että kärki v on aktiivinen , jos MinimumCutPhase-proseduurilla saadun kärjen katkaisujärjestyksen kärjet ennen v :tä ovat kohdassa , tai päinvastoin. Määrittelemme A :han ennen v : tä lisättyjen pisteiden joukoksi , ja se on C :n leikkauksen generoiman joukon leikkaus . Kaikille aktiivisille pisteille v $C=(X,{\overline {X)))$ $W(C)\geqslant W(CP)$ $v\in X$ $\overline {X}$ ${\näyttötyyli A_{v))$ $CV$ $A_{v}\cup \{v\}$

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

Antaa olla ensimmäinen aktiivinen kärkipiste. Määritelmän mukaan nämä kaksi määrää ja ovat samanarvoisia. ovat yksinkertaisesti kaikki kärjet, jotka on lisätty A: hen asti , ja näiden pisteiden väliset reunat, jotka leikkaavat leikkauskohdan C . Siksi, kuten yllä on esitetty, aktiivisille pisteille u ja v ( v lisätään A :han ennen u ), $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)

induktiolla

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

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

, koska se vaikuttaa mutta ei (ja muilla reunoilla on ei-negatiiviset painot)

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

w(C_{u})

w(C_{v})

Sitten, koska t on aina aktiivinen kärki, koska viimeinen vaiheleikkaus erottaa s : n t :stä , määritelmän mukaan mille tahansa aktiiviselle kärkipisteelle t

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

Siten vaiheleikkaus ei ylitä painoa C.

Aika monimutkaisuus

MinimumCut- algoritmin aikamonimutkaisuus on yhtä suuri kuin MinimumCutPhase - proseduurin kokonaisajoaika , jota kutsutaan graafille, jossa on laskeva määrä pisteitä ja kulmia. $|V|-1$

Yksi MinimumCutPhase- menettelyn ajo ei vaadi enempää aikaa. $O(|E|+|V|\log |V|)$

Siksi kokonaisajan tulee olla kahden vaiheen tulo, joka on [2] . $O(|V||E|+|V|^{2}\log |V|)$

Lisäparannuksia varten pitäisi olla helppo valita seuraava joukoon A lisättävä kärki , eli vahvimmin yhdistetty kärki. Kun vaihe suoritetaan, kaikki pisteet, jotka eivät ole A :ssa, sijoitetaan prioriteettijonoon avainkentän perusteella. Huippupisteen V avain on sen nykyiseen joukkoon A yhdistävien reunojen painojen summa , eli . Kun vertex v lisätään joukkoon A , meidän tulee päivittää jono. Piikki v tulee poistaa jonosta ja kaikkien niiden kärkien w avaimia, jotka eivät liity v : hen, tulee lisätä reunan vw painolla , jos sellainen on. Koska tämä tehdään täsmälleen kerran mille tahansa reunalle, meidän tarvitsee vain ExtractMax- ja IncreaseKey-operaatiot. Fibonacci -keon avulla voimme suorittaa ExtractMax-operaation jaksotettuna aikana ja IncreaseKey-operaation jaksotettuna aikana [5] . Joten aika, joka meidän on suoritettava tämä avainvaihe, joka hallitsee loput, on [2] . $w(A,v)$ $|V|$ $|E|$ $O(\log |V|)$ $O(1)$ $O(|E|+|V|\log |V|)$

Muistiinpanot

↑ Boost Graph Library: Stoer–Wagner Min-Cut - 1.46.1 . www.boost.org . Käyttöpäivä: 7. joulukuuta 2015. Arkistoitu alkuperäisestä 19. syyskuuta 2015. (määrätön)
↑ 1 2 3 4 5 Yksinkertainen minimileikkausalgoritmi . Haettu 15. huhtikuuta 2019. Arkistoitu alkuperäisestä 8. joulukuuta 2017. (määrätön)
↑ 1 2 "Luentomuistiinpanot algoritmien analysointiin": Globaalit minimileikkaukset . Haettu 15. huhtikuuta 2019. Arkistoitu alkuperäisestä 5. lokakuuta 2019. (määrätön)
↑ 1 2 Stoerin ja Wagnerin minimileikkausalgoritmi . Haettu 15. huhtikuuta 2019. Arkistoitu alkuperäisestä 3. maaliskuuta 2019. (määrätön)
↑ Pohjimmiltaan kuoletettu aika tarkoittaa "keskimääräistä toimintaan käytettyä aikaa, jos teet paljon toimintaa".