Preflow Push Algorithm

A preflow push algoritmus megoldja a maximális áramlás megtalálásának problémáját a szállítási hálózatban . Az algoritmus nem a Ford-Fulkerson algoritmus speciális esete . Különleges fejlesztések nélkül megvalósítva az algoritmus időben fut . Néhány fejlesztés tovább gyorsítja az algoritmust: az „elejére emelés” csúcskiválasztási szabály - ig , a legmagasabb aktív csúcs kiválasztása -ig , a Senor és a Tarjan adatszerkezet használatával történő megvalósítás - ig . Először 1986 -ban publikálta Andrew W. Goldberg és Tarjan. [1] . $O(V^{2}E)$ $O(V^{3})$ $O(V^{2}{\sqrt {E)))$ $O(VE\log(V^{2}/E))$

Az algoritmus leírása

Definíciók és jelölések

Ebben a cikkben az u csúcs gyermekének nevezünk minden olyan v csúcsot, amelyben a maradék hálózat tartalmaz egy élt (u, v).

A hálózat csúcsainak és éleinek halmazait és -vel , számukat pedig V-vel és E- vel jelöljük. ${\mathbf {V}}$ $\mathbf {E}$

Az algoritmus a preflow függvényt használja, amely a következő tulajdonságokkal rendelkezik bármely csúcshoz és : $\ f:V\times V\rightarrow {\mathbb {R}}$ $\u$ $\v$

Sávszélesség korlátozás. Az adatfolyam nem haladhatja meg a sávszélességet: $\f(u,v)\leq c(u,v).$
Antiszimmetria. Az innen irányú áramlásnak ellentétesnek kell lennie a innen irányú áramlással : $\u$ $\v$ $\v$ $\u$ $\f(u,v)=-f(v,u).$
A túlzott áramlás nem negativitása: mindenre, kivéve a forrást és a nyelőt. $\ \sum _{w\in V}f(w,u)\geq 0$ $\u\in V$

Az első két tulajdonság megegyezik a folyaméval, a harmadik pedig az adatfolyam perzisztencia tulajdonságának gyengülése. Az ebben a tulajdonságban foglalt összeget többletáramlásnak (többletnek) nevezzük , és jelöli . E tulajdonság szerint a többletáramlás nem negatív az összes csúcsra, kivéve a forrást és a nyelőt. $\ \sum _{w\in V}f(w,u)$ ${\displaystyle e_{u))$

Túlcsordulásnak nevezünk egy csúcsot , ha az nem forrás és nem is nyelő, és az adott csúcs felé irányuló többletáramlás szigorúan pozitív. Könnyen belátható, hogy az előfolyam akkor és csak akkor áramlás, ha nincsenek túlcsordulási csúcsok.

Változók

Az algoritmus a következő adatokat tárolja:

előfolyó f
többletáramlás minden csúcsra $e_{u}\$
az egyes csúcsokhoz rendelt nem negatív egész szám, amelyet magasságnak nevezünk . Az u csúcs magasságát jelöli . $h_{u}\$

Inicializálás

Kezdetben az előfolyam egyenlő a forrásból kilépő összes él kapacitásával, és ellentétes a fordított csúcspárok esetében:

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

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

A fennmaradó csúcspárok esetében az előfolyamat egyenlő nullával.

A kezdeti magasság V az origónál, és 0 az összes többi csúcsnál.

Műveletek

Az algoritmus két műveletet használ: lökést (push) és emelést (újracímkézés).

Pushing

Az u csúcsból a v csúcsba tolni a következő feltételek mellett lehetséges:

top u tele van
a maradék hálózat tartalmazza az (u, v) élt (más szóval, v az u leszármazottja)
v alatta: $h_{u}>h_{v}\$

A tolás azt jelenti, hogy az áramlás egy mennyiséggel megnő $f(u,v)$

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

A többletáramlás ugyanennyivel növekszik . $e_{v}\$

A fordított áramlás és a többletáramlás ugyanannyival csökken. $f(v,u)\$ $e_{u}\$

A tolást telítésnek nevezzük, ha . Egy telítés után egyenlővé válik -vel , aminek következtében az (u, v) él kiesik a maradék hálózatból. Nem telítõ nyomással tehát zsúfolttá teszi az u csúcsot. $\delta f(u,v)=c(u,v)-f(u,v)\$ $f(u,v)\$ $c(u,v)\$ $\delta f(u,v)=e_{u}\$

Rise

Az u csúcs megemelése a következő feltételek mellett lehetséges:

top u tele van
alattad nincsenek leszármazottai

Az emelés azt jelenti, hogy az u összes leszármazottja közül kiválasztjuk a minimális magasságú v csúcsot, ami után az u csúcs magassága egyenlő lesz a -val . $h_{v}+1$

Algoritmus

Inicializálja az előáramlást, a redundáns áramlásokat és a magasságokat
Amíg a tolás vagy emelés lehetséges, végezzen el minden lehetséges műveletet.

Az algoritmus tulajdonságai

A maximális áramlás igazolása

Bizonyítsuk be, hogy ha az algoritmus valaha is véget ér, abban a pillanatban az előfolyam lesz a maximális áramlás. Útközben más lemmákat is bebizonyítunk, amelyek hasznosak a következőkben.

1. lemma . Bármely csúcs felemelése növeli a magasságát.
Bizonyíték . Felemelkedés előtt a teteje nem magasabb, mint a legalacsonyabb leszármazottai. Felkelés után magasabb nála. A gyermek magassága nem változott. Következésképpen az emelt felső magassága megnőtt.

2. lemma . Egyetlen csúcs magassága sem csökken.
Bizonyíték . A tolás nem változtatja meg a csúcsok magasságát. Az emelés növeli a felemelt csúcs magasságát, és nem változtatja meg a többi csúcs magasságát.

3. lemma . A forrás és a nyelő magassága mindig V, illetve 0 marad.
Bizonyíték . A forrás és a nyelő definíció szerint nem csordulhat túl, ezért soha nem emelkedhet fel. Sem a többi csúcs megemelése, sem a tolás nem befolyásolja a forrás vagy a nyelő magasságát. Ezért a magasságuk mindig ugyanaz marad, mint az inicializáláskor, ami bizonyítandó volt.

4. lemma . f mindig kielégíti az előáramlási tulajdonságokat.
Bizonyíték . Az elvégzett műveletek számának indukciójával igazoljuk. Bizonyítanunk kell, hogy inicializálás után f kielégíti az előfolyam tulajdonságait, és azt is, hogy ha f kielégíti az előfolyam tulajdonságait a push vagy lift művelet előtt, akkor azt követően is kielégíti azokat.

Inicializálás . Ezt az előáramlás tulajdonságainak triviális ellenőrzése bizonyítja.
Nyomkodás . Ezt az előáramlás tulajdonságainak triviális ellenőrzése is bizonyítja.
Emelkedj . A szálakat egyáltalán nem érinti.

5. lemma ( magasság tulajdonság ) . A maradékhálózat bármely élére (u, v) az egyenlőtlenség

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

Bizonyíték . Indukcióval igazoljuk a végrehajtott műveletek számát az előző lemmához hasonlóan.

Inicializálás . Inicializálás után a V forrás magassága, bármely más csúcspontja 0. Ezért az egyenlőtlenség csak akkor sérülhet meg, ha , . De a maradék hálózatban nincsenek ilyen élek. Valóban, ha a gráf tartalmaz egy élt (s, v), akkor , és az él maradék kapacitása nulla. Ha a gráf nem tartalmaz ilyen élt, akkor és , és ismét az él maradék kapacitása nulla. $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$
Nyomkodás . Nem befolyásolja a csúcsmagasságokat, de létrehozhat egy élt (v, u) a maradék hálózatban és/vagy kizárhat belőle egy élt (u, v).
- Hozzon létre egy élt (v, u) . A tolás csak akkor lehetséges, ha a következő következik . Ez azt jelenti, hogy az újonnan létrehozott él feltétele teljesül. $h_{v}<h_{u}\$ $h_{v}\leq h_{u}+1\$
- Élelvonás (u, v) . Törli a magasság tulajdonság egyik feltételét, ezért nem akadályozza meg a végrehajtását.
Emelkedj . Tekintsük az egyenlőtlenséget bármely csúcspárra. Felemelés előtt kész. Ha u egy olyan csúcs, amely nem emelhető, akkor az emelés nem változtatja meg a magasságot és nem csökken , ami azt jelenti, hogy az egyenlőtlenség az emelés után is fennáll. Ha u egy megmászható csúcs, akkor legyen w a leszármazottjai közül a legalacsonyabb. Majd emelés után , amit bizonyítani kellett. $h_{u}\leq h_{v}+1\$ $h_{u}\$ $h_{v}\$ $h_{u}=h_{w}+1\leq h_{v}+1\$

6. lemma . Ha a maradék hálózat w csúcsa elérhető az u csúcsból, akkor . Bizonyíték . Tekintsük a legrövidebb utat u-tól w-ig. Nem tartalmaz ciklusokat, ezért a hossza legfeljebb . De a magasság tulajdonsága alapján ennek az útnak minden szélén a magasság legfeljebb 1-gyel csökken. Ezért a teljes pályán legfeljebb -kal csökken , amit bizonyítani kellett. $h_{u}-h_{w}<V\$
$V-1$ $V-1$

7. lemma . A maradék hálózatban a mosogató soha nem érhető el a forrásból.
Bizonyíték . Ne legyen így. Aztán az előző lemma szerint . De a 3. Lemma szerint . Ellentmondás. $h_{s}-h_{t}<V\$ $h_{s}-h_{t}=V-0=V\$

8. lemma . Ha az algoritmus valaha is véget ér, akkor az előfolyamat egy szál lesz.
Bizonyíték . Adott egy túlcsorduló csúcs, mindig tudunk tolni (ha a csúcs legalább egy gyereknél magasabb), vagy emelni (egyébként). Mivel az algoritmus csak akkor fejeződik be, ha nem lehetséges a művelet, ezért ebben a pillanatban nincsenek túlcsordulási csúcsok, ami a lemma érvényesülését jelenti.

Tétel . Ha az algoritmus valaha is leáll, akkor az előfolyamat lesz a maximális áramlás.
Bizonyíték . A 8. lemma szerint az előáramlás áramlássá válik. A 7. lemmára a maradék hálózatban a nyelő nem lesz elérhető a forrásból, vagyis nem lesz bővítési út. Ezért az áramlás maximális lesz. [2]

A tolási és emelési műveletek maximális száma

Ebben a részben nemcsak azt bizonyítjuk be, hogy az algoritmus véges időn belül elkészül, hanem felső korlátot is adunk a toló- és emelési műveletek maximális számára.

1. lemma . A mosogatóhoz vezető felesleges áramlás ( ) soha nem csökken. Bizonyíték . Az u-ból v-be tolás csak az u-nál csökkenti a többletáramlást, míg a tolás egyáltalán nem befolyásolja a többletáramlást. Ezért az egyetlen módja a csökkentésnek , ha a süllyesztőből egy másik csúcsba toljuk. De tolni csak túlcsorduló csúcsokból lehet, a süllyesztőt pedig értelemszerűen nem lehet túlcsordulni. Tehát lehetetlen csökkenteni. $e_{t}$
$e_{t}$ $e_{t}$

2. lemma . A mosogatóba ( ) irányuló többletáramlás mindig nem negatív. Bizonyíték . Közvetlenül az inicializálás után egyenlő a -val, ezért nem negatív. A jövőben nem csökken, ezért nem negatív marad. $e_{t}$
$c(s,t)$

3. lemma . A maradék hálózatban a forrás mindig elérhető bármely zsúfolt csúcsból.
Bizonyíték . Legyen az s forrás elérhetetlen valamelyik u csúcsból. Bizonyítsuk be, hogy nem vagy túlcsordulva. Legyen U, U' az u-ból elérhető és el nem érhető csúcsok halmaza a maradék hálózatban. Feltételezve ,. Tekintsünk egy tetszőleges csúcspárt , . A maradék hálózatban nincs (v,w) él, különben u-ból, majd ezen a w él mentén el lehetne érni v-t, ami ellentmond -nek . Másrészt, ha , akkor a maradék kapacitás pozitív, tehát kell lennie egy ilyen élnek. Szóval, honnan . Most összegezzük az U összes csúcsához tartozó többletáramlásokat: $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)

A jobb oldalon lévő két összeg közül az első egyenlő nullával, mert minden releváns csúcspárhoz (v,w) van két olyan f(v,w) és f(w,v) tag, amelyek összege nullával egyenlő. . A második nem pozitív, mivel minden kifejezése nem pozitív. Eszközök,

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

Másrészt az összeg minden tagja nem negatív: $\sum _{v\in U}e_{v}$

ha v nem forrás és nem nyelő, akkor az előfolyamatok harmadik tulajdonsága alapján $e_{v}\geq 0$
nincs forrás, mert $s\notin U$
$e_{t}\geq 0$ az előző lemma szerint

Mivel a nem negatív tagok összege nem pozitív, ebből az következik, hogy minden tagja egyenlő nullával. Konkrétan , azaz u nem túlcsorduló, amit bizonyítani kellett. $e_{u}=0\$

4. lemma . Bármely csúcs magassága mindig kisebb, mint 2 V.
Bizonyíték . Tekintsünk néhány u csúcsot. Egy csúcs magasságának megváltoztatásának egyetlen módja a csúcs felemelése. Ezért, ha az u csúcsot soha nem emeltük meg, akkor a magassága ugyanaz marad, mint az inicializálás után, azaz 0 vagy V, és a lemma bizonyítást nyer. Egyébként a magassága ugyanaz maradt, mint amilyenné az utolsó emelkedés eredményeként lett. Az utolsó emelkedés előtt u túlcsordult, ami azt jelenti, hogy a maradék hálózatban az s forrás elérhető volt onnan. Az emelkedés után az u-tól s-ig tartó út a maradék hálózatban megmarad, mert az emelkedés nem érinti a maradék hálózatot. Ezért az előző szakasz 6. lemmája alapján , ahonnan , amit bizonyítani kellett. $h_{u}-h_{s}<V$ $h_{u}<2V$

Tétel . Az algoritmus működésének teljes ideje alatt nem lehet több, mint . Bizonyíték . Egy csúcs felemelése legalább 1-gyel növeli a magasságát. Minden csúcs kezdeti magassága nem kisebb, mint 0, a végső magassága az előző lemma szerint legfeljebb 2V-1. A csúcsmagasság nem csökkenthető. Ez azt jelenti, hogy minden csúcs legfeljebb 2V-1 mászást bír ki. Összességében legfeljebb V-2 csúcsot emelhet fel (s és t kivételével). Ez magában foglalja a tétel érvényesítését. $(2V-1)(V-2)$

Tétel . Az algoritmus működésének teljes ideje alatt nem lehet több, mint . Bizonyíték . Tekintsünk két egymást követő telítő lökést u-ból v-be. Az első kizárja az (u, v) élt a maradék hálózatból, mire a második végrehajtódik, ez az él újra megjelenik. Tehát e két lökés között egy v-ről u-ra történő lökést hajtanak végre, ami az él visszaállításának egyetlen módja. Az első telítési lökés során, miközben v-ről u-ra nyomjuk, éppen ellenkezőleg, . Figyelembe véve, hogy a magasságok nem csökkenhetnek, azt kapjuk, hogy a magasság legalább 2-vel nőtt. Mivel ez minden két egymást követő telítési lökés között történik u-ból v-be, és egyetlen csúcs magassága sem nőhet 2V-1-nél nagyobb mértékben (0-ról). 2V-1-re), az u-ból v-be történő lökések száma nem haladja meg a V-t. Összesen 2E tolásra alkalmas csúcspár van (minden él és azok inverzei). Ennélfogva nem lehet több telítési nyomás, mint 2VE. $2VE$
$h_{u}>h_{v}$ $h_{u}<h_{v}$ $h_{v}$

Végül, hogy megtaláljuk a nem telítetlen lökések számának felső korlátját, az összes túlcsordult csúcs magasságának összegét használjuk potenciálfüggvényként. Jelöljük ezt az összeget Φ-vel. Az u-ból v-be történő nem telítő hatás nem változtatja meg a magasságokat, hanem u-t zsúfoltból zsúfolttá változtat, és v-t zsúfoltból zsúfolttá változtathatja; nem befolyásolja a többi csúcs állapotát. Ezért Φ legalább -kal csökken . A tolás csak akkor lehetséges, ha tehát a nem telítõ nyomás legalább 1-gyel csökkenti Φ-t. Kezdetben Φ=0, de Φ soha nem válhat negatívvá. Ez azt jelenti, hogy az algoritmus csak annyi nem telítõ lökést tud végrehajtani, amennyit a többi mûvelet Φ-vel növel. Az emelés legfeljebb 2V-1-gyel növeli a Φ-t, a Saturating Push pedig legfeljebb 2V-1-gyel növeli a Φ-t. Ezért az ilyen lökések teljes száma legfeljebb , vagy . $h_{u}-h_{v}$ $h_{u}>h_{v}$ $(2V-1)^{2}(V-2)+2VE(2V-1)$ $O(V^{2}(V+E))$

Mivel az izolált csúcsok (amelyek nem esnek az eredeti hálózat egyik szélére) semmilyen módon nem befolyásolják a push vagy lift műveleteket, ezért mentálisan kizárhatjuk őket, hogy megbecsüljük a műveletek számát, amelyek után . Ezért a nem telítő lökések száma . Ha ide hozzáadjuk a legfeljebb telítő lökéseket, akkor azt kapjuk, hogy az összes lökések száma is . $V\leq 2E$ $O(V^{2}E)$ $2VE$ $O(V^{2}E)$

Megvalósítás

Egy sor túlcsorduló csúcsot tárolunk, és minden csúcshoz - két utódot: nem kisebb magassággal és kisebb magassággal. Mindezeket a halmazokat egyszerűen elemek tömbjeként tároljuk (C++ - vektorok szempontjából).

A teendő intézkedések meghatározása:
- ha a túlcsorduló csúcsok halmaza üres, állj le
- az utolsó elemét másolja u
- ha nincs alacsonyabb termetű gyermeked, hívj fel, hogy kelj fel
- ellenkező esetben az utolsó ilyen gyermeket másolja v-be, és hívja a push parancsot u-ról v-re
Lökés u-ról v
- módosítsa f(u, v), f(v, u), e(u), e(v) a régi értékek mentése után
- ha szükséges, zárjuk ki az u-t a túlcsorduló csúcsok halmazából
- adjunk hozzá v-t ehhez a halmazhoz, ha szükséges
- ha szükséges, zárja ki v-t az u leszármazottainak halmazából
- ha szükséges, adjunk hozzá u-t v nem kisebb magasságú gyermekeinek halmazához
Top emelkedő u
- nézd meg az összes leszármazott magasságát, és találd meg belőlük a minimumot
- változtassa meg az u csúcs magasságát
- átnézünk minden nem kisebb magasságú leszármazottat, és néhányat áthelyezünk az alacsonyabb magasságú leszármazottak körébe
- átnézzük az u csúcs összes szomszédját (az inicializálás során a szomszédok listáit kell készíteni), és ha szükséges, átvisszük az u-t a nem kisebb magasságú leszármazottak halmazába.

A szükséges művelet meghatározása és a tolás állandó időben történik (megjegyzendő, hogy a tolásnál a halmaz utolsó eleme mindig kizárt). Ezért a kívánt művelet és push minden meghatározása műveleteket igényel. $O(V^{2}E)\$

Az emelkedési idő meghatározásához megjegyezzük, hogy az u csúcsnak a nem kisebb magasságú leszármazottak halmazába való áttételéhez ki kell zárni az alacsonyabb magasságú leszármazottak halmazából. Mivel a leszármazottak halmazai vektorokként vannak tárolva, és egy vektor elemének törléséhez a hosszával arányos számú műveletre van szükség, az ilyen átvitel műveleteket igényelhet. Ez azt jelenti, hogy az összes szomszéd fordítása műveleteket igényel, ahol az u csúcs foka. Az emelés során végrehajtott többi művelet kevesebb műveletet igényel, ami azt jelenti, hogy az emelés műveleteket igényel. Egy csúcs kibírja az emelést, ezért minden emelése műveleteket igényel, az összes csúcs minden emelése pedig műveletet igényel . $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)\$

Ezért az algoritmus megvalósítása műveleteket igényel. $O(V^{2}E)\$

Algoritmus "emelés az elejére"

Az átcímkézés a frontra algoritmus a fent leírtaknál hatékonyabb megvalósítása a preflow push algoritmusnak. A működési idő . $O(V^{3})$

Érvényes élek

Az algoritmus a megengedett élek fogalmát használja . Egy élt (u, v) elfogadhatónak nevezünk, ha két feltétel teljesül:

$f(u,v)<c(u,v)\$ , vagy ezzel egyenértékű, az él (u, v) jelen van a maradék hálózatban.
$h_{u}=h_{v}+1\$

Vegye figyelembe, hogy a magasság tulajdonságot figyelembe véve ezek a feltételek egybeesnek a push művelet élekre való alkalmazhatóságának utolsó két feltételével. Következésképpen,

A tolás csak a megengedett élek mentén történik.

Ezen túlmenően az emelés megengedhetősége a magasság tulajdonságát figyelembe véve a következőképpen fogalmazható meg

Az emelés akkor és csak akkor megengedett, ha az emelendő csúcs túlcsordul, és nem jönnek ki belőle megengedett élek

Ezen túlmenően a megengedhető élek további két tulajdonsága igazolható.

Tulajdonság 1. A tolás nem hoz létre új érvényes éleket.
Bizonyíték. Tegyük fel, hogy valamilyen lökdösődés megengedhetővé tette az élt (u, v). Egy él (u, v) megengedettségét 4 paraméter határozza meg teljesen: az u és v csúcsok magassága, az él mentén való áramlás és a kapacitása. A csúcsok magasságát és élkapacitását semmilyen tolás nem befolyásolja. Ez azt jelenti, hogy befolyásolta az f(u, v) áramlást. Ez csak az (u, v) vagy (v, u) él mentén történhet. De az él mentén (u, v) való toláshoz az már a tolás előtt megengedhető, ami ellentmond a feltételezésnek. A (v, u) él mentén történő toláshoz különösen szükséges, hogy u v alatt legyen. Mivel a tolás nem befolyásolja a magasságot, u kisebb lesz, mint v, lökést követően, ami sérti a második elfogadhatósági feltételt.

Tulajdonság 2. A v csúcs felemelése után a v-ben szereplő összes él érvénytelen lesz.
Bizonyíték. Tekintsünk egy ilyen élt (u, v), és bizonyítsuk be, hogy felemelés után érvénytelen lesz.

Ha az emelkedés előtt az él jelen volt a maradék hálózatban, akkor a magasság tulajdonság alapján . Az emelés megnöveli a v csúcs magasságát, tehát utána , ami sérti a második elfogadhatósági tulajdonságot. $h_{u}\leq h_{v}+1$ $h_{u}<h_{v}+1$
Ha az emelés előtt hiányzott egy él a maradék hálózatban, akkor az emelés után is hiányzik benne, mert az emelés nem befolyásolja az áramlásokat. Ez azt jelenti, hogy az első elfogadhatósági feltétel sérül.

Tárolt értékek

Az előfolyamon és a magasságokon kívül az algoritmus a következőket tárolja:

Minden v csúcshoz a szomszédok listája . A lista minden w csúcsot tartalmaz úgy, hogy a hálózat tartalmaz egy élt (v,w) vagy egy élt (w,v). A sorrend önkényes. A szomszédok listái egyszer, az algoritmus elején épülnek fel, és nem változnak tovább. $N[v]$
Minden csúcs esetében v egy mutató a szomszédok listájának egyik elemére ( C++ kifejezéssel iterátor). Az elején mutat a lista első elemére. $current[v]$
Az összes csúcs L listája , kivéve a forrást és a nyelőt. Kezdetben véletlenszerű sorrendben tartalmazza a csúcsokat. A jövőben a csúcsok áthelyezhetők, de nem zárhatók ki vagy nem adhatók hozzá a listához.
Mutasson rá az L lista egyik elemére ( C++ kifejezéssel iterátor). Az elején mutat a lista első elemére.

Kisütés

Ebben a részben egy csúcskisülés nevű függvényt írunk le . A távolság csak a zsúfolt csúcsokra vonatkozik.

Leírás

Az u csúcs kisütése a következőképpen történik:

1. lépés. Amíg az u csúcs megtelt, kövesse a 2-4 lépéseket. 2. lépés: Ha az áram túllép a lista végén, emelje fel az u csúcsot, és térjen vissza a lista elejére. 3. lépés. Egyébként, ha megengedett az u-ból az aktuális[u]-ra tolni, tedd meg. 4. lépés. Ellenkező esetben mozgassa előre az aktuális 1 elemet. Tulajdonságok

1. lemma . A ciklus minden iterációja után, ha a függvény nem állt le, az u csúcs túlcsordul.
Bizonyíték . Az 1. lépésben végzett ellenőrzésből következik.

2. lemma . A ciklus minden iterációja után az él (u, current[u]) érvénytelen, nem létezik, vagy a függvény leáll. Itt az aktuális az iteráció kezdetére mutató mutató értéke .
Bizonyíték . Ha a 2. lépés feltétele teljesült, az él nem létezik. Ellenkező esetben, ha a 3. lépés feltétele nem teljesül, az él érvénytelen; mivel a push nem hoz létre új érvényes éleket, érvénytelen marad. Végül, ha a nyomást a 3. lépésben hajtották végre, az vagy telítő vagy nem telítő volt. Az első esetben az él (u, v) eltűnt a maradék hálózatból, ami azt jelenti, hogy az első elfogadhatósági feltétel sérül. A második esetben a csúcs nem túlcsordult, ami után a függvény az 1. lépésnél megállt.

3. lemma . Ha a 2. lépés feltétele teljesül, az u-ból kimenő él nem megengedett.
Bizonyíték . Tekintsünk minden ilyen élt (u, v). Ha a v csúcs nem szomszédos az u csúcstal, akkor nincs él a maradék hálózatban, így az első elfogadhatósági feltétel megsérül. Ellenkező esetben a csúcsot a 3. lépésben vettük figyelembe. Tekintsük az utolsó alkalmat, amikor ez történt. Közvetlenül ezután az előző lemma (u, v) éle érvénytelenné vált. Ezen túlmenően a funkcióban semmilyen műveletet nem lehetett végrehajtani, kivéve az u-ból kiinduló egyéb élek mentén történő nyomkodást. Az ilyen lökések az első elfogadhatósági tulajdonság alapján nem tehetik újra megengedhetővé az (u, v) élt.

1. ingatlan . Tolásra és emelésre csak akkor kerül sor, ha ez megengedett.
Bizonyíték . Minden egyes lökések megengedettségét kifejezetten ellenőrzik. Az emelés megengedhetőségét garantálja, hogy a 2. lépésben az u csúcsot az 1. lemma túlcsordítja, valamint az is, hogy a 3. lemma által nem jön ki belőle megengedett él.

2. ingatlan . A függvény befejezése után az u csúcs nem túlcsordul.
Bizonyíték . A függvény csak az 1. lépésnél állhat meg. A leállítás csak akkor következik be, ha az u csúcs nem túlcsordul.

Az algoritmus leírása

A prestream és a magasságok mellett a "raise to the elejéig" algoritmus tárolja az L csúcsok listáját és egy mutatót az egyik elemére (C++ kifejezéssel egy iterátor ) .

Inicializálás:
- Inicializálja az áramlásokat és a magasságokat, mint az előfolyamat push algoritmusban.
- Ha a forráson és a süllyedőn kívül nincs más csúcs, állj meg; a feladat megoldva.
- Készítsen listákat az összes csúcs szomszédjairól, és állítsa be az iterátorokat a listák elejére.
- Írja L - be az összes csúcs listáját, kivéve a forrást és a nyelőt, tetszőleges sorrendben.
- a lista elejére mutat.
Amíg a lista valamelyik elejére mutat:
- Helyezze el az általa mutatott csúcsot .
- Ha a vertex magasságot változtatott a kisütés során, rendezze át azt és az iterátort a lista elejére (így továbbra is rá fog mutatni).
- Tolja előre az iterátort egy pozícióval előre.

Tulajdonságok

A digráf topológiai rendezése (V,E) néhány csúcsának listája, oly módon rendezve, hogy bármely él esetén u a v előtti listában szerepel. $(u,v)\in E$

1. lemma. A külső hurok minden iterációja után az L lista a megengedett élgráf (ATGGR) topológiai fajtája.
Bizonyíték. A külső hurok iterációinak számának indukciója.
Bázis. Inicializálás után a forrás magassága egyenlő V-vel, az összes többi csúcs 0. Ugyanakkor , mivel legalább 2 csúcs van - forrás és süllyesztő. Ezért bármely csúcspár esetében a második elfogadhatósági feltétel sérül, és egyáltalán nincsenek megengedhető élek. Ezért a csúcsok bármely listája TSGDR. Lépés. Nézzük a v. $V\geq 2$

Ha nem emelték fel, a csúcsok sorrendje nem változott. Mielőtt megnéztem volna, a lista a TSGDR volt. A vizsgálat során csak push műveletek történtek, amelyek nem hoznak létre új érvényes éleket. Így a lista továbbra is TSGDR maradt.
Ha felvették, akkor a lista elejére került. Bizonyítsuk be, hogy minden megengedett él megfelel a topológiai rendezési feltételnek.
- V-ből kimenő: minden esetben teljesítenie kell a topológiai rendezési feltételt, mivel v áll a lista élén.
- V-ben benne van: nincsenek. Valójában a magasság tulajdonság alapján, az utolsó emelés előtt, a maradék hálózat bármely szélére, . Az emelkedés tehát a már végrehajtott után nőtt , ami sérti a második elfogadhatósági tulajdonságot. Ezért bármely u csúcs esetén a közvetlenül az emelkedés utáni él vagy nem lépett be a maradék hálózatba, vagy megsértette a második elfogadhatósági tulajdonságot. Mindkét esetben érvénytelen volt. Azóta semmilyen műveletet nem végeztek, kivéve talán a lökést. Amint megmutattuk, a push-ok nem hoznak létre új érvényes éleket. $(u,v)$ $h_{u}\leq h_{v}+1$ $h_{v}$ $h_{u}<h_{v}+1$ $(u,v)$
- Nem incidens v: az iteráció során sem az elfogadhatóságuk, sem a v-n kívüli csúcsok egymáshoz viszonyított sorrendje nem változott. Ezért ezek az élek továbbra is kielégítik a topológiai rendezési feltételt.

2. lemma. A külső ciklus minden egyes iterációja után a beolvasott csúcs és a listában attól balra lévő összes csúcs nem kerül túlrepülésre.
Bizonyíték. A külső hurok iterációinak számának indukciója.
Bázis. Az első iteráció után a beolvasott csúcsot nem csordítja túl a térköz tulajdonság, és nincsenek csúcsok tőle balra.
Lépés. Nézzük a v. Őt magát nem árasztja el az elbocsátás tulajdonsága. Ha felemeljük, és ezért a lista elejére kerül, akkor balra nincsenek csúcsok, és a tétel bizonyítást nyer. Egyébként ennél az iterációnál csak push műveleteket hajtottak végre a v csúcsból azokhoz a csúcsokhoz, amelyekhez a megengedett élek v-ből vezetnek. Mivel a push művelet nem hoz létre új érvényes éleket, ezek az élek mindegyike érvényes volt az iteráció kezdete előtt. Ezért az előző lemma szerint az összes csúcs, amelyre a lökést végrehajtották, a listában a v jobb oldalán volt. Ezért a listában a v-től balra lévő csúcsok nem lehetnek túlcsordultak ennél az iterációnál. De az indukciós hipotézis szerint korábban sem voltak túlzsúfoltak. A tétel bizonyítást nyert.

3. lemma. Az algoritmus befejezése után egyetlen csúcs sem csordul túl.
Bizonyíték. Az algoritmus befejezéséhez meg kell nézni az L lista utolsó csúcsát. Az előző lemma szerint ezután az L lista egyik csúcsa sem csordult ki. De az L lista a forrás és a nyelő kivételével minden csúcsot tartalmaz, és a forrást és a nyelőt definíció szerint nem lehet túlcsordulni.

Ingatlan. A lift-to-front (PHA) algoritmus a preflow push (PFP) algoritmus egy speciális esete.
Bizonyíték. A magasságok és az előáramlás inicializálása az ALP-ben ugyanaz, mint az APS-ben. A magasság és az áramlás előtti változások az ALP-ben csak kisülés indításával fordulnak elő, amely viszont csak törvényes tolási és emelési műveleteket hajt végre. Végül, az APN végén nincs túlcsordulás, így a push vagy lift műveletek nem lehetségesek.

Nyitva tartás

Becsüljük meg a különböző műveletek végrehajtásának számát és teljes futási idejét.

Kisülések

Minden emelés nélküli kisütésnél egy pozíciót jobbra tol. Az L lista V-2 csúcsokat tartalmaz, ezért V-2-nél több kisütés egymás után emelés nélkül lehetetlen. Az emelkedések száma tehát a kisülések száma . $O(V^{2})$ $O(V^{3})$

Maga a kisülési hívás és a kapcsolódó költségek (az iterátor előrelépése, visszahurkolása) állandó időt vesz igénybe. Ezért az összes ilyen művelet teljes ideje . $O(V^{3})$

Hegymászás

Tekintsünk egy tetszőleges u csúcsot. Legyen a mértéke. A teteje legfeljebb 2V-1-szer emelhető fel, és az egyes emelkedőkre fordított idő . Ezért az összes csúcs felemelésére fordított idő , vagy . ${\displaystyle d_{u))$ $O(d_{u})$ $O\left((2V-1)\sum _{u}d_{u}\right)$ $O(VE)$

Pushing

A telítő lökések, amint azt korábban bebizonyítottuk, nem több, mint O(VE).

A nem telítő nyomás zsúfolttá teszi a tetejét, ami után a kisülés leáll. Ezért nincs több nem telítést okozó push, mint a kisütési hívás, azaz . $O(V^{3})$

Egy nyomás futási ideje állandó. Ez azt jelenti, hogy a lökések teljes futási ideje . $O(V^{3})$

Az iterátor eltolja az aktuálisat

Tekintsünk egy tetszőleges u csúcsot. Legyen a mértéke. Az áram[u] minden eltolódása a csúcs emelkedését okozza. Az összes emelés legfeljebb 2V-1. Ezért az iterátoreltolások száma minden csúcsra , vagy . ${\displaystyle d_{u))$ ${\displaystyle d_{u))$ $O\left((2V-1)\sum _{u}d_{u}\right)$ $O(VE)$

Az egyes műszakok ideje állandó.

Teljes idő

Az előző szakaszokat összegezve azt kapjuk, hogy az algoritmus futási ideje , vagy . $O(V^{3}+VE)$ $O(V^{3})$

Jegyzetek

↑ A maximális áramlási probléma új megközelítése. - 1986. - S. 136-146. — (Annual ACM Symposium on Theory of Computing, Proceedings of the XVIII éves ACM szimpózium on Theory of Computing). — ISBN 0-89791-193-8 .
↑ Annak bizonyítására, hogy az utolsó állítás az utolsó előttiből következik, lásd a " Közlekedési hálózat " cikket.

Irodalom

Thomas Kormen et al. Algoritmusok: konstrukció és elemzés = BEVEZETÉS AZ ALGORITMUSOKBA. - 2. kiadás - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 . , 26. fejezet