Preflow Push Algorithm

Algoritmus preflow push řeší problém nalezení maximálního toku v transportní síti . Algoritmus není speciálním případem Ford-Fulkersonova algoritmu . Implementován bez speciálních vylepšení, algoritmus běží v čase . Některá vylepšení dále urychlují algoritmus: pravidlo výběru vrcholů „na začátek“ - až , výběr nejvyššího aktivního vrcholu - až , implementace pomocí datové struktury Seanor a Tarjan - až . Poprvé publikovali v roce 1986 Andrew W. Goldberg a Tarjan. [1] . $O(V^{2}E)$ $O(V^{3})$ $O(V^{2}{\sqrt {E)))$ $O(VE\log(V^{2}/E))$

Popis algoritmu

Definice a zápis

V tomto článku nazýváme potomkem vrcholu u libovolný vrchol v takový, že zbytková síť obsahuje hranu (u, v).

Množiny vrcholů a hran sítě značíme a a jejich čísla V a E. ${\mathbf {V}}$ $\mathbf {E}$

Algoritmus používá preflow , funkci s následujícími vlastnostmi pro libovolné vrcholy a : $\ f:V\times V\arrowarrow {\mathbb {R}}$ $\u$ $\proti$

Omezení šířky pásma. Stream nesmí překročit šířku pásma: $\f(u,v)\leq c(u,v).$
Antisymetrie. Tok od do musí být opakem toku od do : $\u$ $\proti$ $\proti$ $\u$ $\f(u,v)=-f(v,u).$
Nezápornost nadměrného toku: pro všechny kromě zdroje a jímky. $\ \sum _{w\in V}f(w,u)\geq 0$ $\u\in V$

První dvě vlastnosti jsou stejné jako u streamu, třetí je oslabení vlastnosti perzistence proudu. Součet obsažený v této vlastnosti se nazývá nadměrný tok (přebytek) a označuje se . Podle této vlastnosti je přebytečný tok nezáporný pro všechny vrcholy kromě zdroje a jímky. $\ \sum _{w\in V}f(w,u)$ ${\displaystyle e_{u))$

Vrchol nazýváme přetečením , pokud není ani zdrojem, ani propadem a přebytečný tok k tomuto vrcholu je přísně kladný. Je snadné vidět, že předtok je tok právě tehdy, když neexistují žádné vrcholy přetečení.

Proměnné

Algoritmus ukládá následující data:

předtok f
nadměrný průtok pro každý vrchol $e_{u}\$
nezáporné celé číslo přiřazené každému vrcholu, nazývané výška . Výška vrcholu u je označena . $h_{u}\$

Inicializace

Zpočátku se předtok rovná kapacitě všech hran opouštějících zdroj a je opačný pro obrácené páry vrcholů:

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

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

Pro zbývající dvojice vrcholů je předtok roven nule.

Počáteční výška je V pro počátek a 0 pro všechny ostatní vrcholy.

Operace

Algoritmus používá dvě operace: tlačení (tlačení) a zvedání (přepisování).

Tlačení

Přesunutí z vrcholu u do vrcholu v je možné za následujících podmínek:

nahoře u je plný
zbytková síť obsahuje hranu (u, v) (jinými slovy, v je potomkem u)
v pod u: $h_{u}>h_{v}\$

Tlačení znamená, že se průtok zvýší o určité množství $f(u,v)$

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

Přebytečný průtok se zvýší o stejnou hodnotu . $e_{v}\$

Zpětný průtok a přebytečný průtok se sníží o stejnou hodnotu. $f(v,u)\$ $e_{u}\$

Tlačení se nazývá saturace if . Po saturačním tlaku se , rovná , v důsledku čehož je hrana (u, v) vyloučena ze zbytkové sítě. Nenasyceným tlakem tedy učiní vrchol u nepřeplněný. $\delta f(u,v)=c(u,v)-f(u,v)\$ $f(u,v)\$ $c(u,v)\$ $\delta f(u,v)=e_{u}\$

Vzestup

Zvednutí vrcholu u je možné za následujících podmínek:

nahoře u je plný
žádní potomci u pod u

Zvednutí znamená, že ze všech potomků u se vybere vrchol v s minimální výškou, poté se výška vrcholu u stane rovna . $h_{v}+1$

Algoritmus

Inicializovat preflow, redundantní toky a výšky
Je-li možné tlačení nebo zvedání, proveďte jakoukoli možnou operaci.

Vlastnosti algoritmu

Důkaz maximálního průtoku

Dokažme, že pokud algoritmus někdy skončí, v tu chvíli bude preflow maximální průtok. Po cestě dokazujeme další lemmata, která jsou užitečná pro to, co následuje.

Lemma 1 . Zvednutím libovolného vrcholu se zvětší jeho výška.
Důkaz . Před vzestupem není vrchol výše než nejnižší z jeho potomků. Po vstávání je vyšší než on. Výška dítěte se nezměnila. V důsledku toho se výška zvednutého vršku zvýšila.

Lemma 2 . Výška žádného vrcholu se nikdy nezmenšuje.
Důkaz . Zatlačení nemění výšku vrcholů. Zvýšením se zvýší výška zvednutého vrcholu a nezmění se výška ostatních vrcholů.

Lemma 3 . Výška zdroje a jímky zůstává vždy rovna V a 0.
Důkaz . Zdroj a jímka podle definice nemohou přetékat, a proto nikdy nestoupají. Ani zvedání jiných vrcholů ani tlačení neovlivňuje výšku zdroje nebo jímky. Jejich výšky tedy zůstávají vždy stejné jako v době inicializace, což mělo být prokázáno.

Lemma 4 . f vždy splňuje vlastnosti předfuku.
Důkaz . Dokazujeme to indukcí na počtu provedených operací. Musíme dokázat, že po inicializaci f splňuje vlastnosti předfuku a také, že pokud f splňuje vlastnosti předfuku před operací tlačení nebo zdvihání, bude je splňovat i po něm.

Inicializace . Dokazuje to triviální kontrola vlastností předfuku.
Tlačení . To dokazuje i triviální kontrola vlastností předfuku.
Vstát . Vůbec to neovlivňuje vlákna.

Lemma 5 ( vlastnost výšky ) . Pro libovolnou hranu zbytkové sítě (u, v) je nerovnost

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

Důkaz . Dokazujeme indukcí na počtu provedených operací podobně jako v předchozím lemmatu.

Inicializace . Po inicializaci je výška zdroje V, libovolného jiného vrcholu 0. Nerovnici lze tedy narušit pouze tehdy , když , . Ale ve zbytkové síti žádné takové hrany nejsou. Pokud graf skutečně obsahuje hranu (s, v), pak , a zbytková kapacita hrany je nulová. Pokud graf takovou hranu neobsahuje, pak a , a znovu, zbytková kapacita hrany je nulová. $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$
Tlačení . Neovlivňuje výšky vrcholů, ale může vytvořit hranu (v, u) ve zbytkové síti a/nebo z ní hranu (u, v) vyloučit.
- Vytvořte hranu (v, u) . Zatlačení je možné pouze v případě , odkud následuje . To znamená, že podmínka je splněna pro nově vytvořenou hranu. $h_{v}<h_{u}\$ $h_{v}\leq h_{u}+1\$
- Eliminace hran (u, v) . Zruší jednu z podmínek vlastnosti height, proto nezabrání jejímu provedení.
Vstát . Zvažte nerovnost pro libovolný pár vrcholů. Před zvednutím je hotovo. Pokud u je vrchol, který nelze zvednout, pak zdvih nemění výšku a neklesá , což znamená, že nerovnost bude i po zvednutí pokračovat. Je-li u lezitelný vrchol, pak nechť w je nejnižší z jeho potomků. Poté po zvednutí , které bylo nutné prokázat. $h_{u}\leq h_{v}+1\$ $h_{u}\$ $h_{v}\$ $h_{u}=h_{w}+1\leq h_{v}+1\$

Lemma 6 . Pokud je vrchol w ve zbytkové síti dosažitelný z vrcholu u, pak . Důkaz . Zvažte nejkratší cestu z u do w. Neobsahuje cykly, proto je jeho délka maximálně . Ale pomocí vlastnosti výšky se na každé hraně této cesty výška zmenší o ne více než 1. Na celé cestě se tedy sníží o ne více než o , což bylo nutné dokázat. $h_{u}-h_{w}<V\$
$V-1$ $V-1$

Lemma 7 . Ve zbytkové síti není jímka nikdy dosažitelná ze zdroje.
Důkaz . Ať to tak není. Pak podle předchozího lemmatu . Ale Lemma 3, . Rozpor. $h_{s}-h_{t}<V\$ $h_{s}-h_{t}=V-0=V\$

Lemma 8 . Pokud se algoritmus někdy ukončí, v tomto okamžiku bude předběžné zpracování vlákno.
Důkaz . Vzhledem k přetékajícímu vrcholu můžeme vždy buď tlačit (pokud je vrchol výše než alespoň jedno dítě), nebo zvednout (jinak). Vzhledem k tomu, že algoritmus končí pouze tehdy, nejsou-li možné žádné operace, v tuto chvíli neexistují žádné přetékající vrcholy, což implikuje uplatnění lemmatu.

Věta . Pokud se algoritmus někdy ukončí, v tomto okamžiku bude preflow maximální průtok.
Důkaz . Podle lemmatu 8 se předtok stává tokem. Podle lemmatu 7 ve zbytkové síti nebude jímka dosažitelná ze zdroje, jinými slovy, nebude existovat žádná rozšiřující cesta. Proto bude průtok maximální. [2]

Maximální počet operací tlačení a zvedání

V této části nejen prokážeme, že algoritmus bude dokončen v konečném čase, ale také uvedeme horní mez pro maximální počet operací zatlačení a zvednutí.

Lemma 1 . Přebytečný průtok do jímky ( ) nikdy neklesá. Důkaz . Tlačení z u do v snižuje přebytečný průtok pouze u u, zatímco tlačení neovlivňuje přebytečné průtoky vůbec. Jediný způsob, jak snížit , je tedy tlačit z umyvadla do jiného vrcholu. Ale tlačení je možné pouze z přetékajících vrcholů a dřez nemůže být z definice přetečen. Takže to není možné snížit. $e_{t}$
$e_{t}$ $e_{t}$

Lemma 2 . Přebytečný průtok do dřezu ( ) je vždy nezáporný. Důkaz . Ihned po inicializaci se rovná , je tedy nezáporná. V budoucnu se nesnižuje, proto zůstává nezáporná. $e_{t}$
$c(s,t)$

Lemma 3 . Ve zbytkové síti je zdroj vždy dosažitelný z jakéhokoli přeplněného vrcholu.
Důkaz . Nechť je zdroj s nedosažitelný z nějakého vrcholu u. Dokažme, že u nepřetéká. Nechť U, U' jsou množiny vrcholů dosažitelných a nedosažitelných z u ve zbytkové síti. Podle předpokladu, . Uvažujme libovolný pár vrcholů , . Ve zbytkové síti není hrana (v,w), jinak by bylo možné dosáhnout v z u a poté podél této hrany w, což je v rozporu . Na druhou stranu, pokud , pak je zbytková kapacita kladná, takže tam musí být taková hrana. Takže odkud . Nyní shrňme přebytečné toky do všech vrcholů U: $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}=\součet _{v\in U}\součet _{w\in V}f(w,v)=\součet _{v\in U }\součet _{w\v U}f(š,v)+\součet _{v\v U}\součet _{w\v U'}f(š,v)

První ze dvou součtů na pravé straně je roven nule, protože pro každou relevantní dvojici vrcholů (v,w) má dva členy f(v,w) a f(w,v), jejichž součet je roven nule. . Druhý je nekladný, protože všechny jeho termíny jsou nekladné. Prostředek,

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

Na druhou stranu, každý člen v součtu je nezáporný: $\sum _{v\in U}e_{v}$

pokud v není ani zdroj, ani sink, pak třetí vlastností preflows $e_{v}\geq 0$
není tam žádný zdroj, protože $s\notin U$
$e_{t}\geq 0$ podle předchozího lemmatu

Protože součet nezáporných členů je kladný, všechny jeho členy jsou rovny nule. Zejména, , to znamená, že u není přetékající, což bylo třeba dokázat. $e_{u}=0\$

Lemma 4 . Výška libovolného vrcholu je vždy menší než 2V.
Důkaz . Zvažte nějaký vrchol u. Jediný způsob, jak změnit výšku vrcholu, je zvednout tento vrchol. Pokud tedy vrchol u nebyl nikdy zvýšen, jeho výška zůstává stejná, jako byla po inicializaci, tedy 0 nebo V, a lemma je dokázáno. Jinak jeho výška zůstala stejná, jakou se stala v důsledku posledního stoupání. Před posledním výstupem se u přelévalo, což znamená, že ve zbytkové síti byl z něj zdroj s dosažitelný. Po výstupu je cesta z u do s ve zbytkové síti zachována, protože výstup neovlivňuje zbytkovou síť. Proto podle lemmatu 6 z předchozí části, , odkud , které mělo být prokázáno. $h_{u}-h_{s}<V$ $h_{u}<2V$

Věta . Po celou dobu činnosti algoritmu nemůže být více než . Důkaz . Zvednutí vrcholu zvětší jeho výšku alespoň o 1. Počáteční výška každého vrcholu není menší než 0, konečná podle předchozího lemmatu není větší než 2V-1. Výšku vrcholu nelze snížit. To znamená, že každý vrchol nevydrží více než 2V-1 stoupání. Celkově můžete zvednout nejvýše V-2 vrcholy (všechny kromě s a t). To implikuje tvrzení teorému. $(2V-1)(V-2)$

Věta . Po celou dobu činnosti algoritmu nemůže být více než . Důkaz . Zvažte dvě po sobě jdoucí saturační tahy z u do v. První z nich vyřadí hranu (u, v) ze zbytkové sítě, v době, kdy je provedena druhá, se tato hrana znovu objeví. Mezi těmito dvěma tlaky se tedy provede tlak z v do u, což je jediný způsob, jak obnovit hranu. Při prvním nasycení zatlačte , při tlačení z v do u naopak . Uvážíme-li, že se výšky nemohou snižovat, dostaneme, že se výška zvýšila alespoň o 2. Protože k tomu dochází mezi každými dvěma po sobě jdoucími saturačními tlačítky od u do v a výška žádného vrcholu se nemůže zvýšit o více než 2V-1 (od 0 do 2V-1), počet zatlačení z u do v nepřesáhne V. Celkem jsou k protlačení vhodné 2E páry vrcholů (všechny hrany a jejich inverze). Tudíž nemůže být více saturačních tlaků než 2VE. $2VE$
${\displaystyle h_{u}>h_{v))$ ${\displaystyle h_{u}<h_{v))$ ${\displaystyle h_{v))$

Nakonec, abychom našli horní hranici počtu nesaturujících tahů, použijeme součet výšek všech přetečených vrcholů jako potenciální funkci. Označme tento součet Φ. Nenasycený tlak z u na v nemění výšky, ale mění u z přeplněného na nepřeplněné a může změnit v z nepřeplněného na přeplněné; nemá vliv na stav ostatních vrcholů. Proto se Φ sníží nejméně o . Potlačení je možné pouze tehdy, pokud , nesaturační stlačení sníží Φ alespoň o 1. Zpočátku Φ=0, ale Φ nikdy nemůže být záporné. To znamená, že algoritmus může provést pouze tolik nesaturujících stisků, kolik ostatní operace zvýší Φ. Raise zvýší Φ o ne více než 2V-1 a Saturating Push zvýší Φ maximálně o 2V-1. Celkový počet takových stisků je tedy maximálně , nebo . $h_{u}-h_{v}$ ${\displaystyle h_{u}>h_{v))$ $(2V-1)^{2}(V-2)+2VE(2V-1)$ $O(V^{2}(V+E))$

Vzhledem k tomu, že izolované vrcholy (které nejsou incidentní s žádnou hranou původní sítě) žádným způsobem neovlivňují operace push nebo lift, můžeme je mentálně vyloučit, abychom odhadli počet operací, po kterých . Počet nesaturujících stisků je tedy . Když sem sečteme maximálně saturující stisky, dostaneme, že celkový počet tahů je také . $V\leq 2E$ $O(V^{2}E)$ $2VE$ $O(V^{2}E)$

Implementace

Ukládáme sadu přetékajících vrcholů a pro každý vrchol - dvě sady potomků: s nemenší výškou a s menší výškou. Všechny tyto množiny ukládáme jednoduše jako pole (z hlediska C++ - vektory) prvků.

Určení, jaké kroky podniknout:
- pokud je množina přetékajících vrcholů prázdná, zastavte se
- zkopírujte jeho poslední prvek do u
- pokud nemáš děti nižšího vzrůstu, zavolej tě, abys vstal
- jinak zkopírujte posledního takového potomka do v a zavolejte push z u do v
Tlačení z u do v
- změnit f(u, v), f(v, u), e(u), e(v), po uložení jejich starých hodnot
- v případě potřeby vylučte u z množiny přetékajících vrcholů
- v případě potřeby přidejte do této sady
- v případě potřeby vylučte v z množiny potomků u
- v případě potřeby přidejte u k množině potomků v s nemenší výškou
Horní vzestup u
- podívejte se na výšky všech potomků a najděte jich minimum
- změnit výšku vrcholu u
- prohlédneme si všechny potomky s nemenší výškou a některé z nich přeneseme do množiny potomků s nižší výškou
- prohlédneme si všechny sousedy vrcholu u (seznamy sousedů je nutné připravit při inicializaci) a v případě potřeby přeneseme u do množiny potomků s nemenší výškou.

Určení požadované akce a zatlačení se provádí v konstantním čase (všimněte si, že při zatlačení je vždy vyloučen poslední prvek sady). Proto všechny definice požadované akce a push vyžadují operace. $O(V^{2}E)\$

Pro zjištění doby náběhu si všimneme, že přenos vrcholu u do množiny potomků s nemenší výškou vyžaduje jeho vyloučení z množiny potomků s nižší výškou. Protože sady potomků jsou uloženy jako vektory a odstranění prvku vektoru vyžaduje počet operací úměrných jeho délce, může takový přenos vyžadovat operace. To znamená, že provedení překladů pro všechny sousedy vyžaduje operace, kde je stupeň vrcholu u. Ostatní činnosti prováděné během výtahu vyžadují méně operací, což znamená, že výtah vyžaduje operace. Jeden vrchol může vydržet zvedání, proto všechna jeho zvedání vyžadují operace a všechna zvedání všech vrcholů vyžadují operace. $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)\$

Implementace algoritmu tedy vyžaduje operace. $O(V^{2}E)\$

Algoritmus "navýšení na začátek"

Algoritmus přeznačení na přední je účinnější implementací předflow push algoritmu, než je popsáno výše. Provozní doba je . $O(V^{3})$

Platné hrany

Algoritmus používá koncept přípustných hran . Hrana (u, v) se nazývá přípustná , pokud jsou splněny dvě podmínky:

$f(u,v)<c(u,v)\$ , nebo ekvivalentně, hrana (u, v) je přítomna ve zbytkové síti.
$h_{u}=h_{v}+1\$

Všimněte si, že při zohlednění vlastnosti výšky se tyto podmínky shodují s posledními dvěma podmínkami použitelnosti operace tlačení na hrany. Tudíž,

Tlačení se provádí pouze podél přípustných okrajů.

Kromě toho lze přípustnost zvedání s přihlédnutím k vlastnosti výšky formulovat následovně

Zvedání je přípustné tehdy a pouze tehdy, když zvedaný vrchol přetéká a nevycházejí z něj žádné přípustné hrany

Kromě toho lze prokázat další dvě vlastnosti přípustných hran.

Vlastnost 1. Pushování nevytváří nové platné hrany.
Důkaz. Předpokládejme, že nějaké zatlačení způsobilo, že hrana (u, v) je přípustná. Přípustnost hrany (u, v) je zcela určena 4 parametry: výškami vrcholů u a v, prouděním podél hrany a její kapacitou. Výšky vrcholů a kapacity hran nejsou ovlivněny žádným tlačením. To znamená, že to ovlivnilo tok f(u, v). To lze provést pouze zatlačením podél okraje (u, v) nebo (v, u). Ale tlačení podél okraje (u, v) vyžaduje, aby bylo přípustné již před tlačením, což je v rozporu s předpokladem. Tlačení podél okraje (v, u) vyžaduje zejména, aby u bylo pod v. Protože zatlačení neovlivňuje výšky, u bude po zatlačení nižší než v, což porušuje druhou podmínku přípustnosti.

Vlastnost 2. Po zvednutí vrcholu v budou všechny hrany obsažené ve v neplatné.
Důkaz. Uvažujme každou takovou hranu (u, v) a dokažme, že po zvednutí bude neplatná.

Pokud před výstupem byla hrana přítomna ve zbytkové síti, pak pomocí vlastnosti height . Vztlak zvyšuje výšku vrcholu v, tedy po něm , což porušuje druhou vlastnost přípustnosti. $h_{u}\leq h_{v}+1$ $h_{u}<h_{v}+1$
Pokud hrana chyběla ve zbytkové síti před výtahem, bude v něm chybět i po výtahu, protože výtah neovlivňuje průtoky. To znamená, že bude porušena první podmínka přípustnosti.

Uložené hodnoty

Kromě preflow a výšek ukládá algoritmus následující:

Pro každý vrchol v je seznam jeho sousedů . Seznam obsahuje každý vrchol w takový, že síť obsahuje hranu (v,w) nebo hranu (w,v). Pořadí je libovolné. Seznamy sousedů jsou sestaveny jednou na začátku algoritmu a dále se nemění. $N[v]$
Pro každý vrchol je v ukazatel na jeden z prvků seznamu sousedů (v C++ iterátor). Na začátku ukazuje na první prvek seznamu. $current[v]$
Seznam L všech vrcholů kromě zdroje a jímky. Zpočátku obsahuje vrcholy v náhodném pořadí. V budoucnu lze vertexy přesouvat, ale ne vyloučit nebo přidat do seznamu.
Ukažte jej na jeden z prvků seznamu L (v C++ iterátor ). Na začátku ukazuje na první prvek seznamu.

Výboj

V této části popíšeme funkci nazvanou vrcholový výboj . Mezery platí pouze pro přeplněné vrcholy.

Popis

Vybití vrcholu u se provádí následovně:

Krok 1. Zatímco je vrchol u plný, postupujte podle kroků 2-4. Krok 2. Pokud proud přesáhl konec seznamu, zvedněte vrchol u a vraťte proud na začátek seznamu. Krok 3. V opačném případě, pokud je povoleno posunutí z u na proud[u], udělejte to. Krok 4. Jinak posuňte proud o 1 prvek dopředu. Vlastnosti

Lemma 1 . Po každé iteraci cyklu, pokud se funkce nezastavila, vrchol u přeteče.
Důkaz . Vyplývá z kontroly v kroku 1.

Lemma 2 . Po každé iteraci cyklu je hrana (u, proud[u]) neplatná, neexistuje nebo se funkce zastaví. Aktuální je zde hodnota ukazatele na začátek iterace .
Důkaz . Pokud byla splněna podmínka v kroku 2, hrana neexistuje. V opačném případě, pokud nebyla splněna podmínka v kroku 3, byla hrana neplatná; protože push nevytváří nové platné hrany, zůstává neplatný. Nakonec, pokud bylo zatlačení provedeno v kroku 3, bylo buď saturující, nebo nenasycené. V prvním případě hrana (u, v) zmizela ze zbytkové sítě, což znamená, že je pro ni porušena první podmínka přípustnosti. Ve druhém případě vrchol nepřetekal, načež se funkce zastavila v kroku 1.

Lemma 3 . Když je splněna podmínka kroku 2, není povolena žádná hrana vycházející z u.
Důkaz . Uvažujme každou takovou hranu (u, v). Pokud vrchol v nesousedí s vrcholem u, pak ve zbytkové síti není žádná hrana, proto je porušena první podmínka přípustnosti. V opačném případě byl vrchol uvažován v kroku 3. Zvažte, kdy se to stalo naposledy. Ihned poté se hrana (u, v) podle předchozího lemmatu stala neplatnou. Dále nebylo možné ve funkci provádět žádné operace, kromě tlačení podél dalších hran vycházejících z u. Takové zatlačení nemohlo pomocí první vlastnosti přípustnosti učinit hranu (u, v) znovu přípustnou.

Nemovitost 1 . Tlačení a zvedání se provádí pouze tehdy, když je to povoleno.
Důkaz . Přípustnost každého push je kontrolována explicitně. Přípustnost zvedání je zaručena tím, že v kroku 2 bude vrchol u přetékat lemmatem 1, a také tím, že z něj lemma 3 nevycházejí žádné přípustné hrany.

Nemovitost 2 . Po ukončení funkce vrchol u nepřetéká.
Důkaz . Funkce se může zastavit pouze v kroku 1. K zastavení dojde pouze v případě, že vrchol u nepřeteče.

Popis algoritmu

Kromě prestreamu a výšek ukládá algoritmus "navýšení na začátek" seznam vrcholů L a ukazatel na jeden z jeho prvků (v C++ iterátor) it .

Inicializace:
- Inicializujte toky a výšky jako v algoritmu push preflow.
- Pokud neexistují žádné jiné vrcholy než zdroj a jímka, zastavte se; úkol je vyřešen.
- Sestavte seznamy sousedů všech vrcholů a nastavte iterátory na začátek seznamů.
- Napište v L seznam všech vrcholů, kromě zdroje a jímky, v libovolném pořadí.
- ukazuje na začátek seznamu.
Pokud to ukazuje na nějaký vrchol seznamu:
- Posuňte vrchol, na který ukazuje .
- Pokud vrchol během vybíjení změnil výšku, přeskupte jej a iterátor na začátek seznamu (takže na něj bude stále ukazovat).
- Posuňte iterátor o jednu pozici dopředu.

Vlastnosti

Topologický druh digrafu (V,E) je seznam některých jeho vrcholů, seřazených tak, že pro jakoukoli hranu je u v seznamu před v. $(u,v)\in E$

Lemma 1. Po každé iteraci vnější smyčky je seznam L topologickým druhem grafu přípustných hran (ATGGR).
Důkaz. Indukce na počtu iterací vnější smyčky.
Základna. Po inicializaci je výška zdroje rovna V, všechny ostatní vrcholy jsou 0. Zároveň , protože existují minimálně 2 vrcholy - zdroj a jímka. Proto je pro jakýkoli pár vrcholů porušena druhá podmínka přípustnosti a neexistují vůbec žádné přípustné hrany. Jakýkoli seznam vrcholů je tedy TSGDR. Krok. Podívejme se na v. $V\geq 2$

Pokud nebylo zvednuto, pořadí vrcholů se nezměnilo. Před zhlédnutím byl seznam TSGDR. Během skenování byly prováděny pouze push operace, které nevytvářejí nové platné hrany. Seznam tedy zůstal TSGDR.
Pokud byla zvednuta, byla přesunuta na začátek seznamu. Dokažme, že všechny přípustné hrany splňují podmínku topologického řazení.
- Odchozí z v: musí v každém případě splňovat podmínku topologického řazení, protože v je na začátku seznamu.
- Zahrnuto v: nejsou žádné. Vlastností výšky, před posledním zdvihem, pro jakoukoli hranu zbytkové sítě, . Nárůst se tedy zvýšil poté, co již byl proveden , což porušuje druhou vlastnost přípustnosti. Pro jakýkoli vrchol u tedy hrana bezprostředně po výstupu buď nevstoupila do zbytkové sítě, nebo porušila druhou vlastnost přípustnosti. V obou případech byla neplatná. Od té doby nebyly provedeny žádné operace, snad kromě tlačení. Jak jsme si ukázali, zatlačení nevytváří nové platné hrany. $(u,v)$ $h_{u}\leq h_{v}+1$ ${\displaystyle h_{v))$ $h_{u}<h_{v}+1$ $(u,v)$
- Non-incident v: během iterace se nezměnila ani jejich přípustnost, ani relativní pořadí vrcholů jiných než v. Proto všechny tyto hrany budou nadále splňovat podmínku topologického řazení.

Lemma 2. Po každé iteraci vnější smyčky se skenovaný vrchol a všechny vrcholy nalevo od něj v seznamu nepřetečou.
Důkaz. Indukce na počtu iterací vnější smyčky.
Základna. Po první iteraci není skenovaný vrchol přeplněn vlastností mezery a nalevo od něj nejsou žádné vrcholy.
Krok. Podívejme se na v. Ona sama nepřekypuje vlastností vypouštění. Pokud se zvedne, a proto se přesune na začátek seznamu, pak nalevo od něj nejsou žádné vrcholy a věta je dokázána. Jinak se při této iteraci prováděly pouze operace push z vrcholu v do vrcholů, do kterých vedou přípustné hrany z v. Protože operace push nevytváří nové platné hrany, všechny tyto hrany byly platné před začátkem iterace. Proto podle předchozího lemmatu byly všechny vrcholy, na které byl proveden push, v seznamu vpravo od v. Proto vrcholy nalevo od v v seznamu nemohly být při této iteraci přeplněny. Ale podle indukční hypotézy nebyly ani dříve přeplněné. Věta byla prokázána.

Lemma 3. Po dokončení algoritmu žádný vrchol nepřetéká.
Důkaz. Abychom dokončili algoritmus, musíme se podívat na poslední vrchol v seznamu L. Podle předchozího lemmatu již žádný vrchol seznamu L nepřetéká. Ale seznam L obsahuje všechny vrcholy kromě zdroje a jímky a zdroj a jímku nelze z definice přetékat.

Vlastnictví. Algoritmus lift-to-front (PHA) je speciálním případem algoritmu preflow push (PFP).
Důkaz. Inicializace výšek a předfuku v ALP je stejná jako v APS. Změny nadmořské výšky a před prouděním v ALP nastávají pouze spuštěním výboje, který zase provádí pouze legitimní operace tlačení a zvedání. Konečně na konci APN žádný vrchol nepřetéká, takže operace push nebo lift nejsou možné.

Otevírací doba

Pojďme odhadnout, kolikrát byly různé akce provedeny, a jejich celkovou dobu trvání.

Výboje

Při každém výhozu bez zvedání se posune o jednu pozici doprava. Seznam L obsahuje vrcholy V-2, proto není možné více výbojů než V-2 za sebou bez zvednutí. Počet stoupá , tedy počet výbojů . $O(V^{2})$ $O(V^{3})$

Samotné volání absolutoria a související náklady (postup iterátoru, zpětná smyčka) trvají konstantní čas. Celkový čas pro všechny takové akce je tedy . $O(V^{3})$

Lezení

Uvažujme libovolný vrchol u. Nechť je její stupeň. Vrchol lze zvednout maximálně 2V-1krát a čas strávený na každém výstupu je . Proto čas strávený zvedáním všech vrcholů je , nebo . ${\displaystyle d_{u))$ $O(d_{u})$ $O\left((2V-1)\sum _{u}d_{u}\right)$ $O(VE)$

Tlačení

Saturační tlaky, jak jsme dokázali dříve, nejsou více než O(VE).

Nenasycený tlak způsobí, že vršek není přeplněný, po kterém se vybíjení zastaví. Tudíž neexistuje více nesaturujících push než vybíjecích volání, tedy . $O(V^{3})$

Doba chodu jednoho stisknutí je konstantní. To znamená, že celková doba chodu tlaků je . $O(V^{3})$

Iterátor posouvá aktuální

Uvažujme libovolný vrchol u. Nechť je její stupeň. Každý posun proudu[u] způsobí, že vrchol stoupá. Celkové zdvihy ne více než 2V-1. Proto je počet posunů iterátoru pro všechny vrcholy , nebo . ${\displaystyle d_{u))$ ${\displaystyle d_{u))$ $O\left((2V-1)\sum _{u}d_{u}\right)$ $O(VE)$

Doba každé směny je konstantní.

Celkový čas

Shrneme-li předchozí sekce, dostaneme, že doba běhu algoritmu je , nebo . $O(V^{3}+VE)$ $O(V^{3})$

Poznámky

↑ Nový přístup k problému maximálního průtoku. - 1986. - S. 136-146. — (Výroční sympozium ACM o teorii výpočetní techniky, sborník z osmnáctého výročního sympozia ACM o teorii počítačů). — ISBN 0-89791-193-8 .
↑ Důkaz, že poslední tvrzení vyplývá z předposledního, naleznete v článku " Dopravní síť ".

Literatura

Thomas Kormen aj. Algoritmy: konstrukce a analýza = ÚVOD DO ALGORITHMŮ. - 2. vyd. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 . , kapitola 26