Preflow Push Algorithm

Preflow push - algoritmi ratkaisee ongelman löytää maksimivirtaus kuljetusverkossa . Algoritmi ei ole Ford-Fulkerson-algoritmin erikoistapaus . Ilman erityisiä parannuksia toteutettu algoritmi toimii ajallaan . Jotkut parannukset nopeuttavat algoritmia entisestään: "nousu alkuun" huippupisteen valintasääntö - asti , korkeimman aktiivisen kärjen valinta - asti , toteutus Seanorin ja Tarjanin tietorakenteella - asti . Julkaisivat ensimmäisen kerran vuonna 1986 Andrew W. Goldbergin ja Tarjanin. [1] . $O(V^{2}E)$ $O(V^{3})$ $O(V^{2}{\sqrt {E)))$ $O(VE\log(V^{2}/E))$

Algoritmin kuvaus

Määritelmät ja merkinnät

Tässä artikkelissa kutsutaan kärjen u lapsiksi mitä tahansa kärkeä v siten, että jäännösverkko sisältää reunan (u, v).

Verkon kärkien ja reunojen joukkoja merkitään ja ja niiden numeroita V:llä ja E:llä. ${\mathbf {V}}$ $\mathbf {E}$

Algoritmi käyttää preflowa , funktiota , jolla on seuraavat ominaisuudet kaikille pisteille ja : $\ f:V\times V\rightarrow {\mathbb {R}}$ $\u$ $\v$

Kaistanleveyden rajoitus. Virta ei saa ylittää kaistanleveyttä: $\f(u,v)\leq c(u,v).$
Antisymmetria. Virran osoitteesta kohteeseen on oltava päinvastainen kuin virtauksen kohteesta kohteeseen : $\u$ $\v$ $\v$ $\u$ $\f(u,v)=-f(v,u).$
Ylimääräisen virtauksen ei-negatiivisuus: kaikille paitsi lähteelle ja nielulle. $\ \sum _{w\in V}f(w,u)\geq 0$ $\u\in V$

Kaksi ensimmäistä ominaisuutta ovat samat kuin virralla, kolmas on virran pysyvyysominaisuuden heikkeneminen. Tämän ominaisuuden sisältämää summaa kutsutaan ylimääräiseksi virtaukseksi (ylimäärä) ja sitä merkitään . Tämän ominaisuuden mukaan ylivirtaus ei ole negatiivinen kaikille pisteille paitsi lähteelle ja nielulle. $\ \sum _{w\in V}f(w,u)$ ${\displaystyle e_{u))$

Kutsumme kärkeä ylivuodoksi , jos se ei ole lähde eikä nielu, ja ylivirtaus kyseiseen kärkeen on ehdottomasti positiivinen. On helppo nähdä, että esivuoto on vuo silloin ja vain, jos ylivuotopisteitä ei ole.

Muuttujat

Algoritmi tallentaa seuraavat tiedot:

preflow f
ylimääräinen virtaus jokaiselle kärkipisteelle $e_{u}\$
jokaiselle kärkipisteelle määritetty ei-negatiivinen kokonaisluku, jota kutsutaan korkeudeksi . Huippupisteen u korkeutta merkitään . $h_{u}\$

Alustus

Aluksi esivirtaus on yhtä suuri kuin kaikkien lähteestä lähtevien reunojen kapasiteetti ja on päinvastainen kääntöpisteparien kohdalla:

f(s,u)=c(s,u)\

f(u,s)=-c(s,u)\

Jäljelle jääville kärkipareille esivirtaus on yhtä suuri kuin nolla.

Alkukorkeus on V origolle ja 0 kaikille muille pisteille.

Toiminnot

Algoritmi käyttää kahta operaatiota: työntämistä (työntö) ja nostamista (uudelleenmerkintä).

Työnnä

Työntäminen kärjestä u kärkeen v on mahdollista seuraavissa olosuhteissa:

alkuun olet täynnä
jäännösverkko sisältää reunan (u, v) (toisin sanoen v on u:n jälkeläinen)
v alapuolellasi: $h_{u}>h_{v}\$

Työntäminen tarkoittaa, että virtausta lisätään tietyllä määrällä $f(u,v)$

\delta f(u,v)=\min(e_{u},c(u,v)-f(u,v))\

Ylivirtaus kasvaa saman verran . $e_{v}\$

Vastavirtaus ja ylivirtaus vähenevät samalla määrällä. $f(v,u)\$ $e_{u}\$

Työntämistä kutsutaan kyllästymiseksi , jos . Kyllästyvän työnnön jälkeen tulee yhtä suureksi kuin , minkä seurauksena reuna (u, v) jää pois jäännösverkosta. Ei-kyllästävällä työntöllä se siis tekee kärjestä u ruuhkattoman. $\delta f(u,v)=c(u,v)-f(u,v)\$ $f(u,v)\$ $c(u,v)\$ $\delta f(u,v)=e_{u}\$

Nouse

Huippupisteen u nostaminen on mahdollista seuraavissa olosuhteissa:

alkuun olet täynnä
ei sinun jälkeläisiäsi alapuolellasi

Nosto tarkoittaa, että kaikista u:n jälkeläisistä valitaan minimikorkeudella oleva kärki v, jonka jälkeen kärjen u korkeudeksi tulee yhtä suuri kuin . $h_{v}+1$

Algoritmi

Alusta esivirtaus, redundantit virtaukset ja korkeudet
Kun työntäminen tai nostaminen on mahdollista, suorita mikä tahansa mahdollinen toimenpide.

Algoritmin ominaisuudet

Todiste maksimaalisesta virtauksesta

Osoittakaamme, että jos algoritmi joskus päättyy, sillä hetkellä preflow on maksimivirtaus. Matkan varrella todistamme muita lemmoja, jotka ovat hyödyllisiä seuraavassa.

Lemma 1 . Minkä tahansa kärjen nostaminen lisää sen korkeutta.
Todiste . Ennen nousua huippu ei ole korkeampi kuin alin jälkeläisistä. Noustuaan ylös hän on häntä pitempi. Lapsen pituus ei ole muuttunut. Tämän seurauksena nostettavan yläosan korkeus on kasvanut.

Lemma 2 . Minkään huippupisteen korkeus ei koskaan laske.
Todiste . Työntäminen ei muuta kärkien korkeutta. Nosto lisää nostettavan kärjen korkeutta eikä muuta muiden kärkien korkeutta.

Lemma 3 . Lähteen ja nielun korkeus pysyy aina yhtä suurena V ja 0, vastaavasti.
Todiste . Lähde ja nielu eivät määritelmän mukaan voi vuotaa yli, eivätkä siksi koskaan nouse. Muiden pisteiden nostaminen tai työntäminen ei vaikuta lähteen tai nielun korkeuteen. Siksi niiden korkeudet pysyvät aina samoina kuin alustushetkellä, mikä oli todistettava.

Lemma 4 . f täyttää aina esivirtausominaisuudet.
Todiste . Todistamme sen suoritettujen operaatioiden lukumäärän induktiolla. Meidän on todistettava, että alustuksen jälkeen f täyttää esivirran ominaisuudet, ja myös, että jos f täyttää esivirran ominaisuudet ennen työntö- tai nostotoimintoa, se täyttää ne sen jälkeen.

Alustus . Se todistetaan esivirtauksen ominaisuuksien triviaalisella tarkastuksella.
Työntää . Tämän todistaa myös esivirtauksen ominaisuuksien triviaali tarkistus.
Nouse . Ei vaikuta lankoihin ollenkaan.

Lemma 5 ( korkeusominaisuus ) . Jollekin jäännösverkon reunalle (u, v), epäyhtälö

h_{u}\leq h_{v}+1\

Todiste . Todistamme induktiolla suoritettujen operaatioiden lukumäärän samalla tavalla kuin edellisessä lemassa.

Alustus . Alustuksen jälkeen lähteen V, minkä tahansa muun kärjen korkeus on 0. Näin ollen epäyhtälö voidaan rikkoa vain, jos , . Mutta jäännösverkossa ei ole tällaisia reunoja. Todellakin, jos graafi sisältää reunan (s, v), niin , ja reunan jäännöskapasiteetti on nolla. Jos kuvaaja ei sisällä tällaista reunaa, niin ja , ja jälleen, reunan jäännöskapasiteetti on nolla. $h_{u}\leq h_{v}+1$ $u=s\$ $v\neq s\$ $f(s,v)=c(s,v)$ $f(s,v)=0$ $c(s,v)=0$
Työntää . Ei vaikuta kärkien korkeuksiin, mutta voi luoda reunan (v, u) jäännösverkkoon ja/tai jättää reunan (u, v) pois siitä.
- Luo reuna (v, u) . Työntäminen on mahdollista vain jos , mistä seuraa . Tämä tarkoittaa, että ehto täyttyy vasta luodulle reunalle. $h_{v}<h_{u}\$ $h_{v}\leq h_{u}+1\$
- Reunojen eliminointi (u, v) . Peruuttaa yhden korkeusominaisuuden ehdoista, joten se ei estä sen suorittamista.
Nouse . Harkitse minkä tahansa kärkiparin epäyhtälöä. Ennen nostoa se on tehty. Jos u on kärki, jota ei voida nostaa, niin nosto ei muuta korkeutta eikä laske , mikä tarkoittaa, että epäyhtälö pysyy noston jälkeenkin. Jos u on kiivettävä kärki, olkoon w sen jälkeläisistä alin. Sitten noston jälkeen , mikä oli todistettava. $h_{u}\leq h_{v}+1\$ $h_{u}\$ $h_{v}\$ $h_{u}=h_{w}+1\leq h_{v}+1\$

Lemma 6 . Jos jäännösverkon kärki w on saavutettavissa kärjestä u, niin . Todiste . Harkitse lyhintä polkua u:sta w:hen. Se ei sisällä jaksoja, joten sen pituus on enintään . Mutta korkeusominaisuudella tämän polun jokaisella reunalla korkeus pienenee enintään 1. Siksi koko polulla se pienenee enintään , mikä vaadittiin todistettavaksi. $h_{u}-h_{w}<V\$
$V-1$ $V-1$

Lemma 7 . Jäännösverkossa nielu ei ole koskaan tavoitettavissa lähteestä.
Todiste . Älkää antako olla niin. Sitten edellisen lemman mukaan . Mutta Lemma 3, . Ristiriita. $h_{s}-h_{t}<V\$ $h_{s}-h_{t}=V-0=V\$

Lemma 8 . Jos algoritmi joskus päättyy, siinä vaiheessa preflow on säiettä.
Todiste . Ylivuotopisteessä voimme aina joko työntää (jos kärki on korkeammalla kuin vähintään yksi lapsi) tai nostaa (muuten). Koska algoritmi päättyy vain silloin, kun operaatiot eivät ole mahdollisia, tällä hetkellä ei ole ylivuotopisteitä, mikä tarkoittaa lemman vahvistamista.

Lause . Jos algoritmi joskus päättyy, siinä vaiheessa esivirtaus on maksimivirtaus.
Todiste . Lemmassa 8 esivirtauksesta tulee virtaus. Lemman 7 mukaan jäännösverkossa nielu ei ole tavoitettavissa lähteestä, toisin sanoen lisäyspolkua ei ole. Siksi virtaus on maksimaalinen. [2]

Työntö- ja nostotoimintojen enimmäismäärä

Tässä osiossa emme vain todista, että algoritmi valmistuu äärellisessä ajassa, vaan annamme myös ylärajan työntö- ja nostotoimintojen enimmäismäärälle.

Lemma 1 . Ylimääräinen virtaus nielulle ( ) ei koskaan vähene. Todiste . Työntäminen u:sta v:ään vähentää ylimääräistä virtausta vain kohdassa u, kun taas työntäminen ei vaikuta ylimääräisiin virtauksiin ollenkaan. Siksi ainoa tapa pienentää on työntää nielusta toiseen kärkeen. Mutta työntäminen on mahdollista vain ylivuotavista pisteistä, eikä nielua voi määritelmän mukaan ylivoittaa. Joten sitä on mahdotonta vähentää. $e_{t}$
$e_{t}$ $e_{t}$

Lemma 2 . Ylimääräinen virtaus pesualtaaseen ( ) on aina ei-negatiivinen. Todiste . Välittömästi alustuksen jälkeen se on yhtä suuri kuin , joten se ei ole negatiivinen. Tulevaisuudessa se ei laske, joten pysyy ei-negatiivisena. $e_{t}$
$c(s,t)$

Lemma 3 . Jäännösverkossa lähde on aina tavoitettavissa mistä tahansa ruuhkaisesta kärjestä.
Todiste . Olkoon lähde s saavuttamaton jostain kärjestä u. Osoittakaamme, että et ole täynnä. Olkoot U, U' jäännösverkon kärkijoukot, jotka ovat u:lta saavutettavissa ja joita ei voida saavuttaa. Oletuksena ,. Harkitse mitä tahansa kärkiparia , . Jäännösverkossa ei ole reunaa (v,w), muuten olisi mahdollista päästä v:stä u:sta ja sitten tätä reunaa w pitkin, mikä on ristiriidassa . Toisaalta, jos , niin jäännöskapasiteetti on positiivinen, joten tällaisen reunan täytyy olla. Siis mistä . Summataan nyt ylimääräiset virrat U:n kaikkiin pisteisiin: $s\notin U$ $v\in U$ $w\in U'$ $w\in U'$ $f(v,w)<0\$ $c(v,w)-f(v,w)\$ $f(v,w)\geq 0\$ $f(w,v)\leq 0\$

\sum _{v\in U}e_{v}=\sum _{v\in U}\sum _{w\in V}f(w,v)=\sum _{v\in U }\sum _{w\in U}f(w,v)+\sum _{v\in U}\sum _{w\in U'}f(w,v)

Ensimmäinen oikealla puolella olevista kahdesta summasta on nolla, koska kullekin relevantille pisteparille (v,w) sillä on kaksi termiä f(v,w) ja f(w,v), joiden summa on nolla . Toinen on ei-positiivinen, koska kaikki sen ehdot ovat ei-positiivisia. tarkoittaa,

\sum _{v\in U}e_{v}\leq 0

Toisaalta jokainen summan termi ei ole negatiivinen: $\sum _{v\in U}e_{v}$

jos v ei ole lähde eikä nielu, niin esivirtausten kolmannella ominaisuudella $e_{v}\geq 0$
lähdettä ei ole, koska $s\notin U$
$e_{t}\geq 0$ edellisen lemman mukaan

Koska ei-negatiivisten termien summa on ei-positiivinen, tästä seuraa, että kaikki sen termit ovat yhtä suuria kuin nolla. Erityisesti , eli u ei ole ylikuormittava, mikä oli todistettava. $e_{u}=0\$

Lemma 4 . Minkä tahansa kärjen korkeus on aina alle 2V.
Todiste . Harkitse jotain kärkeä u. Ainoa tapa muuttaa kärjen korkeutta on nostaa sitä. Siksi, jos kärkeä u ei ole koskaan nostettu, sen korkeus pysyy samana kuin se oli alustuksen jälkeen, eli 0 tai V, ja lemma todistetaan. Muuten sen korkeus pysyi samana kuin se oli edellisen nousun seurauksena. Ennen viimeistä nousua u oli ylivuoto, mikä tarkoittaa, että jäännösverkossa lähde s oli tavoitettavissa siitä. Nousun jälkeen polku u:sta s:iin jäännösverkostossa säilyy, koska nousu ei vaikuta jäännösverkkoon. Tästä syystä edellisen osan Lemmalla 6 , mistä , joka oli todistettava. $h_{u}-h_{s}<V$ $h_{u}<2V$

Lause . Algoritmin koko toiminta-ajalla ei voi olla enempää kuin . Todiste . Huippupisteen nostaminen lisää sen korkeutta vähintään 1. Jokaisen kärjen alkukorkeus on vähintään 0, viimeinen edellisen lemman mukaan enintään 2V-1. Huippupisteen korkeutta ei voi pienentää. Tämä tarkoittaa, että kukin huippu voi kestää enintään 2V-1 nousua. Yhteensä voit nostaa korkeintaan V-2 kärkeä (kaikki paitsi s ja t). Tämä edellyttää lauseen vahvistamista. $(2V-1)(V-2)$

Lause . Algoritmin koko toiminta-ajalla ei voi olla enempää kuin . Todiste . Tarkastellaan kahta peräkkäistä kyllästystyöntöä u:sta v:ään. Ensimmäinen niistä jättää reunan (u, v) pois jäännösverkosta; kun toinen suoritetaan, tämä reuna tulee uudelleen esiin. Joten näiden kahden työntövälin välillä suoritetaan työntö v:stä u:hun, mikä on ainoa tapa palauttaa reuna. Ensimmäisen kyllästyvän painalluksen aikana , kun painat v:stä u:han, päinvastoin . Ottaen huomioon, että korkeudet eivät voi laskea, saadaan, että korkeus on kasvanut vähintään 2. Koska tämä tapahtuu jokaisen kahden peräkkäisen kyllästyvän työnnön välillä u:sta v:hen, eikä minkään kärjen korkeus voi kasvaa enempää kuin 2V-1 (0:sta 2V-1), työntöjen määrä u:sta v:iin ei ylitä V:tä. Työntöyn sopivia kärkipareja on yhteensä 2E (kaikki reunat ja niiden käänteiskohdat). Siksi kyllästyviä työntöjä ei voi olla enemmän kuin 2VE. $2VE$
${\displaystyle h_{u}>h_{v))$ ${\displaystyle h_{u}<h_{v))$ ${\displaystyle h_{v))$

Lopuksi, löytääksemme ylärajan ei-tyydyttyvien työntöjen lukumäärälle, käytämme kaikkien ylivuoteltujen kärkien korkeuksien summaa potentiaalifunktiona. Merkitään tämä summa Φ:llä. Ei-tyydyttävä työntö u:sta v:hen ei muuta korkeuksia, mutta muuttaa u:n täpötäytteisestä ruuhkattomaksi ja voi kääntää v:n ahtaasta ruuhkaiseksi; se ei vaikuta muiden kärkien tilaan. Siksi Φ pienenee vähintään . Työntäminen on mahdollista vain , jos siksi tyydyttymätön työntäminen vähentää Φ:tä vähintään yhdellä. Aluksi Φ=0, mutta Φ ei voi koskaan muuttua negatiiviseksi. Tämä tarkoittaa, että algoritmi voi suorittaa vain niin monta ei-tyydyttävää työntöä kuin muut toiminnot lisäävät Φ. Nosto lisää Φ:tä enintään 2V-1 ja Saturating Push lisää Φ:tä enintään 2V-1. Näin ollen tällaisten työntöjen kokonaismäärä on enintään , tai . ${\displaystyle h_{u}-h_{v))$ ${\displaystyle h_{u}>h_{v))$ $(2V-1)^{2}(V-2)+2VE(2V-1)$ $O(V^{2}(V+E))$

Koska eristetyt kärjet (jotka eivät ole sattumanvaraisia alkuperäisen verkon mihinkään reunaan) eivät vaikuta työntö- tai nostooperaatioihin millään tavalla, voimme jättää ne henkisesti pois arvioidaksemme operaatioiden lukumäärän, jonka jälkeen . Siksi ei-kyllästystyöntöjen määrä on . Kun tähän lisätään korkeintaan kyllästyviä työntöjä, saadaan, että työntöjen kokonaismäärä on myös . $V\leq 2E$ $O(V^{2}E)$ $2VE$ $O(V^{2}E)$

Toteutus

Säilytämme joukon ylivuotavia kärkipisteitä, ja jokaiselle kärjelle - kaksi sarjaa jälkeläisiä: vähintään korkeudella ja pienemmällä korkeudella. Tallennamme kaikki nämä joukot yksinkertaisesti elementtien taulukoina (C++ -vektorien suhteen).

Toimenpiteiden määrittäminen:
- jos ylivuotavien kärkien joukko on tyhjä, lopeta
- kopioi sen viimeinen elementti u
- jos sinulla ei ole matalampia lapsia, soita nousemaan
- muussa tapauksessa kopioi viimeinen lapsi v:hen ja kutsu push u:sta v:hen
Työntäminen u:sta v:hen
- muuttaa f(u, v), f(v, u), e(u), e(v), kun olet tallentanut vanhat arvonsa
- tarvittaessa sulje pois u ylivuotavien kärkien joukosta
- lisää v tähän joukkoon tarvittaessa
- tarvittaessa sulje v pois u:n jälkeläisten joukosta
- tarvittaessa lisää u v:n lapsijoukkoon, jonka pituus ei ole pienempi
Top nousu u
- katso kaikkien jälkeläisten korkeuksia ja löydä niistä pienin
- muuta kärjen u korkeutta
- katsomme läpi kaikki yhtä pitkät jälkeläiset ja siirrämme osan niistä matalamman korkuisten jälkeläisten joukkoon
- käymme läpi kaikki kärjen u naapurit (naapuriluettelot on laadittava alustuksen aikana) ja tarvittaessa siirretään u vähintään korkeudelle jälkeläisten joukkoon.

Tarvittavan toimenpiteen määrittäminen ja työntäminen suoritetaan vakioajassa (huomaa, että työnnössä joukon viimeinen elementti on aina poissuljettu). Siksi kaikki halutun toiminnon ja työntömääritykset vaativat operaatioita. $O(V^{2}E)\$

Nousuajan selvittämiseksi huomaamme, että kärjen u siirtäminen jälkeläisten joukkoon, jonka korkeus ei ole pienempi, vaatii sen poissulkemista alhaisemman korkeuden omaavien jälkeläisten joukosta. Koska jälkeläisten joukot tallennetaan vektoreina ja vektorin elementin poistaminen vaatii useita sen pituuteen verrannollisia operaatioita, tällainen siirto voi vaatia operaatioita. Tämä tarkoittaa, että käännösten suorittaminen kaikille naapureille vaatii operaatioita, joissa on kärjen u aste. Loput noston aikana suoritettavat toiminnot vaativat vähemmän operaatioita, mikä tarkoittaa, että hissi vaatii toimenpiteitä. Yksi kärki kestää nostoa, joten sen kaikki nostot vaativat operaatioita ja kaikkien kärkien kaikki nostot vaativat operaatioita. $O(V)\$ $O(d_{u}V)\$ $d_{u}\$ $O(d_{u}V)\$ $2V-1\$ $O(d_{u}V^{2})\$ $O(\sum _{u}d_{u}V^{2})=O(V^{2}E)\$

Näin ollen algoritmin toteutus vaatii operaatioita. $O(V^{2}E)\$

Algoritmi "nostaa alkuun"

Label to front -algoritmi on tehokkaampi toteutus preflow push -algoritmista kuin edellä on kuvattu. Toiminta-aika on . $O(V^{3})$

Kelvolliset reunat

Algoritmi käyttää sallittujen reunojen käsitettä . Reunaa (u, v) kutsutaan hyväksyttäväksi , jos kaksi ehtoa täyttyy:

$f(u,v)<c(u,v)\$ , tai vastaavasti, reuna (u, v) on jäännösverkossa.
$h_{u}=h_{v}+1\$

Huomaa, että ottaen huomioon korkeusominaisuuden, nämä ehdot ovat yhtäpitäviä kahden viimeisen työntöoperaation reunoihin sovellettavuuden ehdon kanssa. Näin ollen

Työntäminen tapahtuu vain sallittuja reunoja pitkin.

Lisäksi noston hyväksyttävyys, ottaen huomioon korkeuden ominaisuus, voidaan muotoilla seuraavasti:

Nostaminen on sallittua vain, jos nostettava kärki on ylivuoto eikä siitä tule sallittuja reunoja

Lisäksi voidaan todistaa kaksi muuta sallittujen reunojen ominaisuutta.

Ominaisuus 1. Työntäminen ei luo uusia kelvollisia reunoja.
Todiste. Oletetaan, että jokin työntäminen teki reunan (u, v) hyväksyttäväksi. Reunan (u, v) hyväksyttävyys määräytyy täysin neljällä parametrilla: kärkien u ja v korkeudella, kulmalla reunaa pitkin ja sen kapasiteetilla. Työntäminen ei vaikuta kärjen korkeuksiin ja reunakapasiteeteihin. Tämä tarkoittaa, että se vaikutti virtaukseen f(u, v). Tämä voidaan tehdä vain työntämällä reunaa (u, v) tai (v, u) pitkin. Mutta reunaa (u, v) pitkin työntäminen edellyttää, että se on sallittu jo ennen työntämistä, mikä on ristiriidassa oletuksen kanssa. Reunaa (v, u) pitkin työntäminen edellyttää erityisesti, että u on v:n alapuolella. Koska työntäminen ei vaikuta korkeuksiin, u on työntämisen jälkeen pienempi kuin v, mikä rikkoo toista hyväksymisehtoa.

Ominaisuus 2. Kun kärki v on nostettu, kaikki v:n sisältämät reunat ovat virheellisiä.
Todiste. Tarkastellaan mitä tahansa tällaista reunaa (u, v) ja todistetaan, että noston jälkeen se on virheellinen.

Jos reuna oli ennen nousua jäännösverkostossa, niin korkeusominaisuuden perusteella . Nosto lisää kärjen v korkeutta, siis sen jälkeen , mikä rikkoo toista hyväksyttävyysominaisuutta. $h_{u}\leq h_{v}+1$ $h_{u}<h_{v}+1$
Jos jäännösverkostosta puuttui reuna ennen hissiä, se puuttuu siitä myös nostamisen jälkeen, koska nosto ei vaikuta virtauksiin. Tämä tarkoittaa, että ensimmäistä hyväksymisehtoa rikotaan.

Tallennetut arvot

Esivirtauksen ja korkeuksien lisäksi algoritmi tallentaa seuraavat tiedot:

Jokaiselle pisteelle v on lista sen naapureista . Lista sisältää jokaisen kärjen w siten, että verkko sisältää reunan (v,w) tai reunan (w,v). Järjestys on mielivaltainen. Naapuriluettelot rakennetaan kerran algoritmin alussa, eivätkä ne muutu enempää. $N[v]$
Jokaisessa kärjessä v on osoitin johonkin naapuriluettelon elementtiin ( C++- termeissä iteraattori). Osoita alussa luettelon ensimmäistä elementtiä. $current[v]$
Listaa L kaikista kärkipisteistä paitsi lähde ja nielu. Aluksi sisältää huippuja satunnaisessa järjestyksessä. Jatkossa pisteitä voidaan siirtää, mutta niitä ei voi jättää pois tai lisätä luetteloon.
Osoita sitä johonkin listan L elementtiin ( C++- termeillä iteraattori). Osoita alussa luettelon ensimmäistä elementtiä.

Purkaus

Tässä osiossa kuvataan funktio nimeltä vertex-purkaus . Välit koskevat vain ruuhkaisia huippuja.

Kuvaus

Huippupisteen u purku suoritetaan seuraavasti:

Vaihe 1. Kun kärkipiste u on täynnä, noudata vaiheita 2-4. Vaihe 2. Jos virta on ylittänyt listan lopun, nosta kärki u ja palauta virta listan alkuun. Vaihe 3. Muussa tapauksessa, jos työntäminen u:sta nykyiseen[u] on sallittu, tee se. Vaihe 4. Muussa tapauksessa siirrä nykyinen 1 elementti eteenpäin. Ominaisuudet

Lemma 1 . Jokaisen silmukan iteraation jälkeen, jos funktio ei ole pysähtynyt, kärki u vuotaa yli.
Todiste . Seuraa vaiheessa 1 tehdystä tarkistuksesta.

Lemma 2 . Jokaisen silmukan iteraation jälkeen reuna (u, current[u]) on virheellinen, sitä ei ole olemassa tai funktio pysähtyy. Tässä nykyinen on iteraation alkuun johtavan osoittimen arvo .
Todiste . Jos vaiheen 2 ehto täyttyy, reunaa ei ole olemassa. Muuten, jos vaiheen 3 ehto ei täyttynyt, reuna oli virheellinen; koska push ei luo uusia kelvollisia reunoja, se pysyy virheellisenä. Lopuksi, jos työntö suoritettiin vaiheessa 3, se oli joko kyllästävä tai ei-kyllästävä. Ensimmäisessä tapauksessa reuna (u, v) on kadonnut jäännösverkosta, mikä tarkoittaa, että sen ensimmäinen hyväksymisehto on rikottu. Toisessa tapauksessa kärjestä ei tullut ylivuotoa, minkä jälkeen funktio pysähtyi vaiheessa 1.

Lemma 3 . Kun vaiheen 2 ehto täyttyy, u:sta lähtevää reunaa ei sallita.
Todiste . Harkitse mitä tahansa tällaista reunaa (u, v). Jos kärki v ei ole kärjen u vieressä, jäännösverkossa ei ole reunaa, joten ensimmäinen hyväksyttävyysehto on rikottu. Muuten kärkipiste otettiin huomioon vaiheessa 3. Mieti, milloin tämä tapahtui viimeksi. Välittömästi tämän jälkeen edellisen lemman reuna (u, v) muuttui virheelliseksi. Lisäksi funktiossa ei voitu suorittaa muita toimintoja, paitsi työntäminen pitkin u:sta lähteviä muita reunoja. Sellaiset työnnät eivät voi ensimmäisellä hyväksyttävyysominaisuudella tehdä reunasta (u, v) uudelleen hyväksyttäväksi.

Kiinteistö 1 . Työntäminen ja nostaminen suoritetaan vain silloin, kun ne ovat sallittuja.
Todiste . Jokaisen työntöjen hyväksyttävyys tarkistetaan erikseen. Noston hyväksyttävyys taataan sillä, että vaiheessa 2 kärki u ylittyy Lemmalla 1, ja myös sillä, että Lemma 3 ei lähde siitä yhtään sallittua reunaa.

Kiinteistö 2 . Kun funktio päättyy, kärki u ei ole ylivuoto.
Todiste . Funktio voi pysähtyä vain vaiheessa 1. Pysäytys tapahtuu vain, jos kärki u ei ole ylivuoto.

Algoritmin kuvaus

Prestreamin ja korkeuksien lisäksi "korotus alkuun" -algoritmi tallentaa listan pisteistä L ja osoittimen johonkin sen elementistä (C++-termeissä iteraattori) sen .

Alustus:
- Alusta virtaukset ja korkeudet kuten esivirtausalgoritmissa.
- Jos ei ole muita pisteitä kuin lähde ja nielu, lopeta; tehtävä on ratkaistu.
- Luo luettelot kaikkien kärkien naapureista ja aseta iteraattorit luetteloiden alkuun.
- Kirjoita L -kirjaimeen lista kaikista kärkeistä, paitsi lähde ja nielu, mielivaltaisessa järjestyksessä.
- se osoittaa luettelon alkuun.
Kunhan se osoittaa johonkin listan kärkeen:
- Siirrä sen osoittama kärkipiste .
- Jos kärki on vaihtanut korkeutta purkamisen aikana, järjestä se ja iteraattori uudelleen listan alkuun (joten se osoittaa edelleen siihen).
- Siirrä iteraattoria yhden aseman eteenpäin .

Ominaisuudet

Digraafin topologinen lajittelu (V,E) on lista joistakin sen kärjeistä, lajiteltuna siten, että minkä tahansa reunan kohdalla u on listassa ennen v:tä. $(u,v)\in E$

Lemma 1. Jokaisen ulomman silmukan iteraation jälkeen lista L on topologinen tyyppi hyväksyttävästä reunagraafista (ATGGR).
Todiste. Induktio ulomman silmukan iteraatioiden lukumäärälle.
Pohja. Alustuksen jälkeen lähteen korkeus on yhtä suuri kuin V, kaikki muut kärjet ovat 0. Samalla , koska pisteitä on vähintään 2 - lähde ja nielu. Siksi minkä tahansa kärkiparin toinen hyväksyttävyysehto rikotaan, eikä hyväksyttäviä reunoja ole ollenkaan. Siksi mikä tahansa kärkiluettelo on TSGDR. Vaihe. Katsotaanpa v. $V\geq 2$

Jos sitä ei nostettu, pisteiden järjestys ei muuttunut. Ennen katsomista lista oli TSGDR. Skannauksen aikana suoritettiin vain push-toimintoja, jotka eivät luo uusia kelvollisia reunoja. Näin ollen luettelo säilyi TSGDR:nä.
Jos se nostettiin, se siirrettiin luettelon kärkeen. Osoittakaamme, että kaikki hyväksyttävät reunat täyttävät topologisen lajitteluehdon.
- V:stä lähtevän on joka tapauksessa täytettävä topologinen lajitteluehto, koska v on listan kärjessä.
- Mukana v: ei niitä ole. Itse asiassa korkeusominaisuuden perusteella ennen viimeistä nostoa jäännösverkoston mille tahansa reunalle . Nousu kasvoi siis sen jälkeen, kun se oli jo suoritettu , mikä rikkoo toista hyväksyttävyysominaisuutta. Siten minkä tahansa kärjen u kohdalla välittömästi nousun jälkeinen reuna joko ei mennyt jäännösverkkoon tai rikkoi toista hyväksyttävyysominaisuutta. Molemmissa tapauksissa se oli pätemätön. Sen jälkeen ei ole tehty muita operaatioita, paitsi ehkä työntämistä. Kuten olemme osoittaneet, työnnät eivät luo uusia kelvollisia reunoja. $(u,v)$ $h_{u}\leq h_{v}+1$ ${\displaystyle h_{v))$ $h_{u}<h_{v}+1$ $(u,v)$
- Ei-insidentti v: iteraation aikana niiden hyväksyttävyys tai muiden kuin v:n kärkien suhteellinen järjestys ei muuttunut. Siksi kaikki nämä reunat täyttävät edelleen topologisen lajitteluehdon.

Lemma 2. Ulkosilmukan jokaisen iteraation jälkeen skannattua kärkeä ja kaikkia sen vasemmalla puolella olevia pisteitä ei ylilennä listassa.
Todiste. Induktio ulomman silmukan iteraatioiden lukumäärälle.
Pohja. Ensimmäisen iteraation jälkeen skannattu kärkipiste ei ole ylivuotettu väliominaisuuden vaikutuksesta, eikä sen vasemmalla puolella ole kärkipisteitä.
Vaihe. Katsotaanpa v. Hän itse ei ole ylenpalttinen vastuuvapauden ominaisuudesta. Jos se nostetaan ja siksi siirretään listan alkuun, sen vasemmalla puolella ei ole kärkeä ja lause on todistettu. Muuten tässä iteraatiossa suoritettiin vain työntöoperaatioita kärjestä v niihin kärkiin, joihin sallitut reunat johtavat v:stä. Koska push-toiminto ei luo uusia kelvollisia reunoja, kaikki nämä reunat olivat voimassa ennen iteraation alkua. Siksi edellisen lemman mukaan kaikki kärjet, joihin työnnettiin, olivat listan v:n oikealla puolella. Siksi listan v:n vasemmalla puolella olevat kärjet eivät voineet tulla ylivuodoiksi tässä iteraatiossa. Mutta induktiohypoteesin mukaan he eivät olleet liian täynnä myöskään aiemmin. Lause on todistettu.

Lemma 3. Algoritmin valmistumisen jälkeen mikään kärki ei vuoda yli.
Todiste. Algoritmin suorittamiseksi on tarkasteltava listan L viimeistä kärkeä. Edellisen lemman mukaan sen jälkeen mikään listan L kärki ei ole ylivuoto. Mutta lista L sisältää kaikki kärjet paitsi lähteen ja nielun, ja lähdettä ja nielua ei voi määritelmän mukaan ylittää.

Omaisuus. Lift-to-front (PHA) -algoritmi on erikoistapaus preflow push (PFP) -algoritmista.
Todiste. Korkeuksien ja esivirtauksen alustus ALP:ssä on sama kuin APS:ssä. Korkeuden ja esivirtauksen muutokset ALP:ssä tapahtuvat vain laukaisemalla purkaus, joka puolestaan suorittaa vain laillisia työntö- ja nostotoimintoja. Lopuksi, APN:n lopussa mikään kärki ei vuoda yli, joten työntö- tai nostotoiminnot eivät ole mahdollisia.

Aukioloajat

Arvioidaan kuinka monta kertaa eri toiminnot suoritetaan, ja niiden kokonaiskesto.

Purkaukset

Jokaisella purkauksella ilman nostamista se siirtyy yhden asennon oikealle. Lista L sisältää V-2 kärkeä, joten enemmän kuin V-2 purkaus peräkkäin ilman nostoa on mahdotonta. Nousujen määrä , siis purkausten määrä . $O(V^{2})$ $O(V^{3})$

Itse purkukutsu ja siihen liittyvät kustannukset (iteraattorin eteneminen, takaisinkytkentä) vievät jatkuvasti aikaa. Siksi kaikkien tällaisten toimien kokonaisaika on . $O(V^{3})$

Kiipeily

Tarkastellaan mielivaltaista kärkeä u. Olkoon sen aste. Huippua voidaan nostaa korkeintaan 2V-1 kertaa, ja jokaiseen nousuun kuluu aika . Siksi kaikkien kärkien nostamiseen käytetty aika on , tai . ${\displaystyle d_{u))$ $O(d_{u})$ $O\left((2V-1)\sum _{u}d_{u}\right)$ $O(VE)$

Työnnä

Kyllästyneet työnnät, kuten olemme aiemmin todenneet, eivät ole enempää kuin O(VE).

Ei-kyllästävä työntö tekee kannen ruuhkautumattomaksi, minkä jälkeen purkautuminen pysähtyy. Siksi ei ole sen enempää ei-kyllästäviä työntöjä kuin purkauskutsuja, eli . $O(V^{3})$

Yhden painalluksen käyntiaika on vakio. Tämä tarkoittaa, että työntöjen kokonaisajoaika on . $O(V^{3})$

Iteraattori siirtää nykyistä

Tarkastellaan mielivaltaista kärkeä u. Olkoon sen aste. Jokainen virran[u] siirto saa kärjen nousemaan. Kokonaisnostot enintään 2V-1. Siksi iteraattorisiirtymien määrä kaikille kärkipisteille on , tai . ${\displaystyle d_{u))$ ${\displaystyle d_{u))$ $O\left((2V-1)\sum _{u}d_{u}\right)$ $O(VE)$

Jokaisen vuoron aika on vakio.

Kokonaisaika

Yhteenvetona edellisistä osista saadaan, että algoritmin ajoaika on , tai . $O(V^{3}+VE)$ $O(V^{3})$

Muistiinpanot

↑ Uusi lähestymistapa maksimivirtausongelmaan. - 1986. - S. 136-146. — (Vuotuinen ACM Symposium on Theory of Computing, Proceedings of the XVIII ACM symposium on Theory of Computing). — ISBN 0-89791-193-8 .
↑ Todiste siitä, että viimeinen lause seuraa toiseksi viimeistä, katso artikkeli " Liikenneverkko ".

Kirjallisuus

Thomas Kormen ym. Algoritmit: rakentaminen ja analyysi = ALGORITMEIN JOHDANTO. - 2. painos - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 . , luku 26