-%%%%%%%%%%%%
-% Zápisek druhého semináøe z grafových algoritmù - ze dne 13.3.2006
-% Téma Dinicùv algoritmus a v¹emo¾né jeho modifikace.
-% Zapsal Bernard Lidický - bernard@matfyz.cz
-%
-% Verze z 29. dubna 2006
-%
-%%%%%%%%%%%
-
\input ../sgr.tex
-\prednaska{2}{Dinicùv algoritmus a jeho analýza}{zapsal Bernard Lidický}
+\prednaska{2}{Dinicùv algoritmus a jeho varianty}{zapsal Bernard Lidický}
\h{Dinicùv algoritmus}
Dinicùv algoritmus je zalo¾en na my¹lence, ¾e ve Ford-Fulkersonovì algoritmu
není potøeba pøièítat jen zlep¹ující cesty, ale je mo¾né pøièítat rovnou zlep¹ující
-toky. Funguje takto:
+toky, nejlépe takové, aby je nebylo obtí¾né najít, a~pøitom aby pùvodní tok
+ dostateènì zlep¹ovaly. Vhodnými objekty k~tomuto úèelu jsou:
+
+\s{Definice:} {\I Blokující tok} je tok takový, ¾e ka¾dá orientovaná $st$-cesta
+obsahuje alespoò jednu nasycenou hranu. [Tj. takový tok, který by na¹el F-F algoritmus,
+kdyby neuva¾oval rezervy v~protismìru.]
+
+\s{Algoritmus (Dinic):}
\algo
\:Zaèni s~libovolným tokem~$f$, napøíklad prázdným (v¹ude nulovým).
A pøípadnì pøidáváme do~fronty vrcholy, kterým klesl jeden ze stupòù na 0
pøi vyhazování hran. Vyma¾ou se tím slepé ulièky, které by vadily v podkroku~9.
\endlist
- Tedy kroky 5 a 12 dohromady spotøebují èas $\O(m)$\foot{Pøesnìji $\O(m+n)$, pokud by v síti byly izolované
- vrcholy, ale ty mù¾eme zahodit úplnì u¾ na zaèátku.}.
+ Tedy kroky 5 a 12 dohromady spotøebují èas $\O(m)$.
\:Jeden prùchod vnìj¹ím cyklem tedy trvá $\O(mn)$.
\endlist
délku $\leq n$. Celková slo¾itost algoritmu tedy bude $\O(n^2m)$
\s{Korektnost algoritmu:}
-Korektnost Dinicova algoritmu plyne z korektnosti FF algoritmu. Kdy¾ se Dinicùv
-algoritmus zastaví, musí vydat maximální tok. Pokud ne, tak podle FF algoritmu
+Korektnost Dinicova algoritmu plyne z korektnosti F-F algoritmu. Kdy¾ se Dinicùv
+algoritmus zastaví, musí vydat maximální tok. Pokud ne, tak podle F-F algoritmu
existuje zlep¹ující cesta, ale to je ve sporu s~krokem~4, který po¾aduje, ¾e ¾ádná
zlep¹ující cesta neexistuje.
\s{Dùkaz vìty:}
-Podíváme se na výpoèet jednoho prùchodu vnìj¹ím cyklem.
+Podíváme se na~prùbìh jednoho prùchodu vnìj¹ím cyklem.
Délku aktuálnì nejkrat¹í $st$-cesty oznaème~$l$.
-Vypozorujeme, ¾e délka cest, které pøípadnì vzniknou pøi hledání a sycení
-v¹ech cest délky $l$, musí být vìt¹í ne¾ $l$. Jinak øeèeno, nestane se,
-¾e by vznikaly nové krátké cesty.
+V¹echny pùvodní cesty délky~$l$ se bìhem prùchodu zaruèenì nasytí, proto¾e
+tok~$f_B$ je blokující. Musíme v¹ak dokázat, ¾e nemohou vzniknout ¾ádné
+nové cesty délky~$l$ nebo men¹í. V~síti rezerv toti¾ mohou hrany nejen
+ubývat, ale i pøibývat: pokud po¹leme tok po~hranì, po~které je¹tì nic
+neteklo, mù¾e se stát, ¾e v~protismìru z~dosud nulové rezervy vyrobíme
+nenulovou. Rozmysleme si tedy, jaké hrany mohou pøibývat:
Vnìj¹í cyklus zaèíná s neproèi¹tìnou sítí. Pøíklad takové sítì je na obrázku nìkde
-okolo. Po proèi¹tìní zùstanou v~síti jen èerné hrany. Èervené a modré\foot{Modré jsou
-ty, které vedou v rámci jedné vrstvy, èervené vedou zpìt èi za~spotøebiè èi do~slepých
-ulièek. Pøi vyti¹tìní na papír není snadné je barevnì odli¹it od èerných.} se zahodí.
+okolo. Po proèi¹tìní zùstanou v~síti jen èerné hrany, tedy hrany vedoucí z~$i$-té
+vrstvy do~$(i+1)$-ní. Èervené a modré\foot{Modré jsou ty, které vedou v rámci jedné vrstvy,
+èervené vedou zpìt èi za~spotøebiè èi do~slepých ulièek. Pøi vyti¹tìní na papír není snadné
+je barevnì odli¹it od èerných.} se zahodí.
+
\figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a slepé ulièky.}{0.3\hsize}
-Nové hrany tak mohou vznikat jen díky èerným hranám, proto¾e s hranami zahozenými pøi èi¹tìní algoritmus
-dále nepoèítá.
-
-Nová hrana mù¾e vzniknout zlep¹ení toku po nìjaké zlep¹ující cestì, proto¾e
-kdy¾ po hranì po¹leme nìjaký tok, zvedne se rezerva hrany opaèné, která mohla být
-nulová\foot{Tedy po zpìtné hranì ne¹lo nic poslat a nepoèítalo se s ní.}.
-Tím vznikne nová zpìtná hrana. ®ádné novì dopøedné hrany pøeskakující více vrstev nevznikají.
-\figure{dinic-zpetnahrana.eps}{Vznik nové zpìtné hrany}{0.3\hsize}
-Poka¾dé, kdy¾ se zlep¹í tok podél nìjaké cesty, budou v grafu ke v¹em hranám cesty
-existovat hrany opaèného smìru s~nenulovou rezervou. Nìkteré
-tyto opaèné hrany u¾ v~grafu mohly být, ale tím lépe pro nás\foot{Tento odstavec
-je spí¹e informativní a slou¾í malinko pro osvícení ètenáøe. V dùkazu nemá ¾ádný smysl.}.
+Nové hrany mohou vznikat výhradnì jako opaèné k~èerným hranám (hrany ostatních barev
+padly za obì» proèi¹tìní). Jsou to tedy v¾dy zpìtné hrany vedoucí z~$i$-té vrstvy do~$(i-1)$-ní.
-Vznikem nových hran by mohly vzniknout nové $st$-cesty, které pou¾ívají
-zpìtné hrany. Ale $st$-cesta, která pou¾ívá zpìtnou hranu, musí alespoò jednou skoèit zpìt.
-Tedy její délka je alespoò $l+2$.
+\figure{dinic-zpetnahrana.eps}{Vznik nové zpìtné hrany}{0.3\hsize}
-\figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.3\hsize}
+Vznikem nových hran by proto mohly vzniknout nové $st$-cesty, které pou¾ívají
+zpìtné hrany. Jen¾e $st$-cesta, která pou¾ije zpìtnou hranu, musí alespoò jednou skoèit zpìt
+a nikdy nemù¾e skoèit dopøedu o~více ne¾ jednu vrstvu, a~proto je její délka alespoò $l+2$.
+Tím je vìta dokázána. \qed
-Tedy ve vnitøním cyklu zaniknou v¹echny $st$-cesty délky $l$ a pøitom nevzniknou ¾ádné nové krat¹í $st$-cesty.
-Proto délka nejkrat¹ích cest vzroste alespoò o 1.
-\qed
+\figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.3\hsize}
\h{Implementaèní poznámky}
\:Není potøeba tak brutální èi¹tìní. Vrcholy se vstupním stupnìm 0 nám
nevadí -- stejnì se do nich nedostaneme. Vadí jen vrcholy s výstupním stupnìm 0, kde by mohl
havarovat postup v podkroku 9.
-\:Je mo¾né dìlat prohledávání a èi¹tìní souèasnì. Jednodu¹e metodou HRRR na nì a kdy¾
+\:Je mo¾né dìlat prohledávání a èi¹tìní souèasnì. Jednodu¹e metodou Hrrr na nì a kdy¾
to nevyjde (dostaneme se do slepé ulièky), kus ustoupíme a pøi ústupu èistíme sí»
odstraòováním slepé ulièky.
\:U¾ pøi prohledáváni si rovnou udr¾ujeme minimum z rezerv a pøi zpáteèní cestì
V ka¾dé úrovni rekurze si zapamatujeme minimum, jaké bylo, kdy¾ jsme tam pøi¹li. Pokud
se vracíme, recyklujeme toto minimum.}
\:V prùbìhu výpoètu udr¾ujeme jen sí» rezerv a tok vypoèteme a¾ nakonec z rezerv a kapacit.
-\:Kdy¾ budeme chtít hledat minimální øez, spustíme Dinicùv algoritmus, pak jednou iterací FF
- algoritmu dostaneme jeden z minimálních øezù\foot{Samozøejmì získáme i maximální tok.}.
+\:Kdy¾ budeme chtít hledat minimální øez, spustíme po~Dinicovu algoritmu je¹tì jednu iterací F-F
+ algoritmu.
\endlist
-\s{Na pøemý¹lení:} Máme minimální øez. Jak zjistíme maximální tok?
-
\h{Speciální sítì (ubíráme na obecnosti)}
-Dále se budeme vìnovat modifikacím algoritmu na speciální druhy sítí,
+Dále se budeme vìnovat modifikacím Dinicova algoritmu na speciální druhy sítí,
kde je mo¾né dostat lep¹í èasovou slo¾itost ne¾ v~obecném pøípadì.
\s{Jednotkové kapacity:}
V¹echny rezervy jsou jen 0 nebo~1. Na $st$-cestì má v¹echno kapacitu/rezervu~1.
Mù¾eme poslat~1~a rovnou celou cestu zahodit -- není potøeba si pamatovat minimum z~rezerv.
-Kdy¾ máme $m$ hran, zlep¹eních po cestách délky $l$ bude maximálnì $m/l$.
+Kdy¾ máme $m$ hran, poèet zlep¹ení po cestách délky $l$ bude maximálnì $m/l$.
Proto slo¾itost podkrokù 9, 10 a 11 bude $m/l \cdot \O(l) = \O(m)$.%
\foot{Nebo by ¹lo argumentovat, ¾e ka¾dou hranu pou¾ijeme jen $1\times$.}
Tedy pro jednotkové kapacity dostáváme slo¾itost $\O(nm)$.
\s{Jednotkové kapacity znovu a lépe:}
-Vnitøní cyklus lépe udìlat nepùjde. Je potøeba alespoò $\O(m)$ pro èi¹tìní.
+Vnitøní cyklus lépe udìlat nepùjde. Je potøeba alespoò lineární èas pro èi¹tìní.
Mù¾eme se ale pokusit lépe odhadnout poèet iterací vnìj¹ího cyklu.
-Sledujeme stav sítì po $k$ iteracích vnìj¹ího cyklu a pokusíme se odhadnout, kolik iterací
-je¹tì algoritmus udìlá. Oznaème délku nejkrat¹í $st$-cesty $l$.
-Víme, ¾e $l \geq k$, proto¾e v ka¾dé iteraci vzroste $l$ alespoò o 1.
+Sledujme stav sítì po $k$ iteracích vnìj¹ího cyklu a pokusme se odhadnout, kolik iterací
+je¹tì algoritmus udìlá. Oznaème~$l$ délku nejkrat¹í $st$-cesty.
+Víme, ¾e $l>k$, proto¾e v ka¾dé iteraci vzroste $l$ alespoò o 1.
-Máme tok $f_k$ a chceme dostat maximální tok $f$. $f - f_k$ je tok v~síti rezerv.
-Tedy $\exists f_R$ tok v síti rezerv takový, ¾e
-zlep¹ení $f_k$ podle $f_R$ je $f$.
+Máme tok $f_k$ a chceme dostat maximální tok $f$. Rozdíl $f-f_k$ je tok v~síti rezerv
+(tok v~pùvodní síti to ov¹em být nemusí!), oznaème si ho~$f_R$.
Ka¾dá iterace velkého cyklu zlep¹í $f_k$ alespoò o 1. Tedy nám zbývá je¹tì
nejvý¹e $\vert f_R \vert$ iterací.
Proto bychom chtìli omezit velikost toku $f_R$. Napøíklad øezem.
-
+
Najdeme v síti rezerv øez $C$. Kde ho vzít?\foot{Pøeci v øeznictví. Kdepak, spí¹e v cukrárnì.
Myslíte, ¾e v cukrárnì mají Dinicovy øezy? Myslím, ¾e v cukrárnì je vìt¹ina øezù minimální.}
-Poèítejme jen hrany zleva doprava. Tìch je jistì nejvý¹e $m$ a tvoøí $k-1$ rozhraní mezi
-$k$ vrstvami. Tedy existuje rozhraní vrstev
+Poèítejme jen hrany zleva doprava. Tìch je jistì nejvý¹e $m$ a tvoøí alespoò $k$ rozhraní mezi
+vrstvami. Tedy existuje rozhraní vrstev
s~nejvý¹e $m/k$ hranami\foot{Princip holubníku a nìjaká ta $\pm1$.}.
-Toto rozhraní je øez. Tedy existuje øez $C$, ¾e $\vert C\vert \leq m/k$
-Algoritmu tedy zbývá maximálnì $m/k$ krokù.
-Celkový poèet krokù je nejvý¹ $k + m/k$. Staèí zvolit $k = \sqrt{m}$. Poèet krokù
-pak bude $\O(\sqrt{m})$.
+Toto rozhraní je øez. Tedy existuje øez $C$, pro nìj¾ $\vert C\vert \leq m/k$,
+a~algoritmu zbývá maximálnì $m/k$ dal¹ích krokù.
+Celkový poèet krokù je nejvý¹ $k + m/k$, tak¾e staèí zvolit $k = \sqrt{m}$ a získáme
+odhad na~poèet krokù $\O(\sqrt{m})$.
-Celkovì slo¾itost Dinicova algoritmu pro jednotkové kapacity znovu a lépe
-je $\O(\sqrt{m} m) = \O(m^{3/2})$. Pomohli jsme si pro øídké grafy.
+Celkovì slo¾itost Dinicova algoritmu pro jednotkové kapacity znovu a lépe
+je $\O(\sqrt{m} \cdot m) = \O(m^{3/2})$. Pomohli jsme si pro øídké grafy.
\s{Jednotkové kapacity a jeden ze stupòù roven 1:}
-Úlohu hledání maximálního párování v bipartitním grafu lze
-hezky pøevést na hledání maximálního toku. Z grafu se vytvoøí
-sí» tak, ¾e v¹echny vrcholy jedné partity se napojí na $s$ a v¹echny
-vrcholy druhé partity se napojí na $t$.\foot{$s,t$ jsou novì pøidané vrcholy.}
-Na v¹echny hrany se dají jednotkové kapacity a orientace ka¾dé bude smìrem\foot{%
-V¹echny hrany v bipartitním grafu se zorientují smìrem ke komponentì, kde je napojený
-vrchol $t$. Hrany obsahující vrchol $t$ se zorientují smìrem do $t$. Hrany obsahující vrchol
-$s$ se zorientují smìrem od $s$. Snad je to intuitivnì vidìt. Pro jistotu je nìkde okolo
-obrázek popisované sítì.} k~$t$.
-Najde se maximální tok a hrany v~toku tvoøí maximální párování. Proto mù¾e být
-u¾iteèné zkoumat tento speciální pøípad sítí.
-
-\figure{dinic-bipartitni.eps}{Sí» vzniklá z bipartitního grafu}{0.4\hsize}
-
-Sí» se vyznaèuje tím, ¾e ka¾dý vrchol krom $s$ a $t$ má vstupní nebo výstupní stupeò 1.
+Úlohu hledání maximálního párování v~bipartitním grafu, pøípadnì hledání
+vrcholovì disjunktních cest v~obecném grafu lze pøevést (viz pøedchozí kapitola)
+na~hledání maximálního toku v~síti, v~ní¾ $\forall v \neq s,t: \min(\deg^-(v), \deg^+(v)) \leq 1$.
Pro takovou sí» mù¾eme odhad je¹tì tro¹ku upravit. My¹lenka je stejná jako minule. Pokusíme
se nalézt v síti po $k$ krocích nìjaký malý øez. Místo rozhraní budeme hledat jednu malou
-vrstvu a z malé vrstvy vytvoøíme malý øez. Pro ka¾dý vrchol z vrstvy vezmeme tu hranu,
-která je ve svém smìru sama, a tím získáme øez.
+vrstvu a z malé vrstvy vytvoøíme malý øez: Pro ka¾dý vrchol z vrstvy vezmeme tu hranu,
+která je ve svém smìru sama.
\figure{dinic-vrcholrez.eps}{Øez podle vrcholù ve vrstvì}{0.2\hsize}
-Tedy $\forall v \neq s,t: \min(\deg^-(v), \deg^+(v)) \leq 1$.
-Po $k$ krocích máme $k$ vrstev. Tedy existuje vrstva $\delta$ s nejvý¹e $n/k$ vrcholy\foot{Holubníkový princip.}.
-Tedy existuje øez $C$, ¾e $\vert C\vert \leq n/k$, který získáme z vrstvy $\delta$ vý¹e popsaným postupem.
-Algoritmu zbývá do konce $\leq n/k$ iterací vnìj¹ího cyklu. Algoritmus celkem udìlá $k + n/k$ krokù%
-\foot{Mo¾ná chybí nìjaké $\pm1$, ale to nehraje roli.}. Staèí zvolit $k = \sqrt{n}$ a slo¾itost
-celého algoritmu vyjde $\O(\sqrt{n}m)$\foot{Poèet iterací vnìj¹ího cyklu je $\O(\sqrt{n})$ a
+Po $k$ krocích máme alespoò $k$ vrstev. Tedy existuje vrstva $\delta$ s nejvý¹e $n/k$ vrcholy.
+Tedy existuje øez $C$ o~velikosti $\vert C\vert \leq n/k$ (získáme z vrstvy $\delta$ vý¹e popsaným postupem).
+Algoritmu zbývá do konce $\leq n/k$ iterací vnìj¹ího cyklu, celkem tedy udìlá $k + n/k$ krokù.
+Nyní staèí zvolit $k = \sqrt{n}$ a slo¾itost
+celého algoritmu vyjde $\O(\sqrt{n}\cdot m)$\foot{Poèet iterací vnìj¹ího cyklu je $\O(\sqrt{n})$ a
vnitøní cyklus má $\O(m)$.}.
\s{Tøetí pokus pro jednotkové kapacity bez omezení na stupnì vrcholù v síti:}
-Hlavní my¹lenkou je opìt po $k$ krocích najít nìjaký malý øez. Najdeme dvì malé\foot{Co do souètu
-poètu vrcholù v obou vrstvách.} sousední vrstvy a v¹echny hrany mezi nimi budou tvoøit námi hledaný malý øez.
+Hlavní my¹lenkou je opìt po $k$ krocích najít nìjaký malý øez. Najdeme dvì malé
+sousední vrstvy a v¹echny hrany mezi nimi budou tvoøit námi hledaný malý øez.
Oznaème $s_i$ poèet vrcholù v $i$-té vrstvì. Souèet poètu vrcholù ve dvou
-sousedních vrstvách oznaèíme $t_i = s_i + s_{i+1}$. Bude tedy platit nerovnost
-$$\sum_i t_i \leq 2\sum_i s_i \leq 2n {\rm .}$$
-
-Tedy existuje $i$, ¾e $t_i \leq 2n/k$\foot{Holubníkový princip. Zase.}.
-Tedy $\exists i: s_i + s_{i+1} \leq 2n/k$. Poèet hran mezi $s_i$ a $s_{i+1}$ je velikost øezu
-$C$ a to je men¹í ne¾ $s_i \cdot s_{i+1}$.
-Nejhor¹í pøípad je, kdy¾ $s_i = s_{i+1} = n/k$. Tedy $\vert C\vert \leq {(n/k)}^2$.
-Pro jistotu je¹tì jednou v celku jako dlouhá nerovnost:
-$$ \<\# hran mezi>\ s_i, s_{i+1} = \vert C\vert \leq s_i\cdot s_{i+1} \leq {(n/k)}^2 {\rm .}$$
-Proto poèet iterací velkého cyklu je $\leq \<konstanta> + k + {(n/k)}^2$.
+sousedních vrstvách oznaèíme $t_i = s_i + s_{i+1}$. Bude tedy platit nerovnost:
+$$\sum_i t_i \leq 2\sum_i s_i \leq 2n.$$
+Podle holubníkového principu existuje $i$ takové, ¾e $t_i \leq 2n/k$, èili
+$s_i + s_{i+1} \leq 2n/k$. Poèet hran mezi $s_i$ a $s_{i+1}$ je velikost øezu
+$C$, a to je shora omezeno $s_i \cdot s_{i+1}$. Nejhor¹í pøípad nastane, kdy¾ $s_i = s_{i+1} = n/k$,
+a~proto $\vert C\vert \leq {(n/k)}^2$.
+Proto poèet iterací velkého cyklu je $\leq k + {(n/k)}^2$.
Chytøe zvolíme $k = n^{2/3}$. Slo¾itost celého algoritmu pak bude $\O(n^{2/3}m)$.
-\s{Poslední odhad pro celoèíselné kapacity:}
-Poslední\foot{Samozøejmì následuje je¹tì jeden algoritmus i s odhadem pro celoèíselné kapacity.
-Ale to u¾ není pøímo Dinicùv algoritmus. Jen Dinice pou¾ívá jako podprogram.} odhad je zalo¾en na velikosti
+\s{Obecný odhad pro celoèíselné kapacity:}
+Tento odhad je zalo¾en na velikosti
maximálního toku $f$ a pøedpokladu celoèíselných kapacit.
Za jednu iteraci velkého cyklu projdeme malým cyklem maximálnì tolikrát,
o kolik se v nìm zvedl tok, proto¾e ka¾dá zlep¹ující cesta ho zvedne alespoò o $1$.
-Zlep¹ující cesta se tedy hledá maximálnì $\vert f\vert$ krát za celou dobu bìhu algoritmu.
+Zlep¹ující cesta se tedy hledá maximálnì $\vert f\vert$-krát za celou dobu bìhu algoritmu.
Cestu najedeme v èase $\O(n)$. Celkem na hledání
-cest spotøebujeme $\O(\vert f\vert n)$ za celou dobu bìhu algoritmu.
+cest spotøebujeme $\O(\vert f\vert\cdot n)$ za celou dobu bìhu algoritmu.
Nesmíme ale zapomenout na cleanupy. V jedné iteraci velkého cyklu stojí cleanupy $\O(m)$ a velkých
-iterací je $\leq n$. Proto celková slo¾itost algoritmu je $\O(\vert f\vert n + nm)$
+iterací je $\leq n$. Proto celková slo¾itost algoritmu èiní $\O(\vert f\vert n + nm)$
-Pokud navíc budeme pøedpokládat omezení na maximální kapacitu hran $ \leq C$,
-lze získat je¹tì jeden odhad tím, ¾e odhadneme maximální velikost toku jako $ \leq Cn$.
-Co¾ lze odùvodnit napøíklad tak, ¾e z $s$ jde maximálnì $n$~hran\foot{Nepøedpokládáme multigraf.}
-a kapacita ka¾dé je $ \leq C$. Proto celkový tok musí být $ \leq Cn$.
-Dostaneme odhad $\O(Cn^2 + nm)$.
+Pokud navíc budeme pøedpokládat, ¾e kapacita hran je nejvý¹e~$C$ a $G$ není multigraf,
+mù¾eme vyu¾ít toho, ¾e $\vert f\vert \le Cn$ (omezeno øezem okolo~$s$) a získat odhad
+$\O(Cn^2 + nm)$.
\h{Scaling kapacit}
-Základní my¹lenka je podobná, jako u algoritmu pro tøídìní dlouhých èísel postupnì po øádech pomocí
+Základní my¹lenka je podobná, jako u algoritmu pro tøídìní dlouhých èísel postupnì po øádech pomocí
radix-sortu. Pro jistotu si ho pøipomeòme. Algoritmus nejprve setøídí èísla podle poslední%
\foot{Poslední cifrou myslíme nejménì významnou cifru.}
-cifry, poté podle pøedposlední, pøedpøedposlední a tak dále.
+cifry, poté podle pøedposlední, pøedpøedposlední a tak dále.
\figure{dinic-sort.eps}{Kroky postupného tøídìní podle øádù}{0.2\hsize}
V na¹em pøípadì budeme postupnì budovat sítì a v nich poèítat toky, a¾ nakonec získáme tok pro celou sí».
-
+
Pøedpokládejme celoèíselné kapacity. Maximální tok v síti $G$ budeme hledat tak, ¾e hranám postupnì
-budeme zvìt¹ovat kapacity bit po bitu v binárním zápisu, a¾ k jejich skuteèné kapacitì.
+budeme zvìt¹ovat kapacity bit po bitu v binárním zápisu a¾ k jejich skuteèné kapacitì.
Pøitom po~ka¾dém posunu zavoláme Dinicùv algoritmus. Pomocí pøedchozího odhadu uká¾eme, ¾e jedno
volání Dinice nebude pøíli¹ drahé.
\figure{dinic-scaling-original.eps}{Pùvodní sí», na hranách jsou jejich kapacity v binárním zápisu}{0.2\hsize}
-Oznaème $k$ poèet bitù v zápisu nejvìt¹í kapacity z celé sítì. $k = \lceil \log_2C \rceil$.
-Postupnì budeme budovat sítì $G_i$ s kapacitami $C_i(e) = \lfloor {C(e) / 2^{k-i}} \rfloor$.
-$G_0$ je nejoøezanìj¹í sí», kde ka¾dá hrana má kapacitu jako je nejvy¹¹í bit v binárním zápisu
+Oznaème $k$ poèet bitù v zápisu nejvìt¹í kapacity z celé sítì. $k = \lfloor \log_2C \rfloor$.
+Postupnì budeme budovat sítì $G_i$ s~kapacitami $c_i(e) = \lfloor {c(e) / 2^{k-i}} \rfloor$.
+$G_0$ je nejoøezanìj¹í sí», kde ka¾dá hrana má kapacitu rovnou nejvy¹¹ímu bitu v~binárním zápisu
její skuteèné kapacity. $G_k$ je pùvodní sí» $G$.
- $$ C_{i+1}(e) = \left\{
+$$ c_{i+1}(e) = \left\{
\eqalign{
- 2C_i(e), &\hbox{\quad pokud $(k-i-1)$-tý bitík je 0} \cr
- 2C_i(e)+1, &\hbox{\quad pokud $(k-i-1)$-tý bitík je 1} \cr}
+ 2c_i(e), &\hbox{\quad pokud $(k-i-1)$-tý bitík je 0} \cr
+ 2c_i(e)+1, &\hbox{\quad pokud $(k-i-1)$-tý bitík je 1} \cr}
\right.
- $$
+$$
\figure{dinic-scaling-g.eps}{Sítì $G_0$, $G_1$ a $G_2$, jak vyjdou pro sí» z~pøedchozího obrázku}{0.8\hsize}
-Na spoètení maximálního toku $f_i$ v síti $G_i$ zavoláme Dinicùv algoritmus,
+Na spoètení maximálního toku $f_i$ v síti $G_i$ zavoláme Dinicùv algoritmus,
ov¹em do zaèátku nepou¾ijeme nulový tok, nýbr¾ tok $2f_{i-1}$. Rozdíl toku z inicializace
-a výsledného bude malý.
-
-Tvrdíme, ¾e:
+a výsledného bude malý, toti¾:
$$ \vert f_i\vert - \vert 2f_{i-1}\vert \leq m.$$
\s{Dùkaz:}
-Vezmeme minimální øez $R$ v $G_{i-1}$. Platí $\vert f_{i-1}\vert = \vert R\vert$\foot{Minimaxová vìta.}.
+Vezmeme minimální øez $R$ v $G_{i-1}$. Platí $\vert f_{i-1}\vert = \vert R\vert$\foot{F-F vìta.}.
Øez $R$ obsahuje $\leq m$ hran. V $G_{i}$ má øez $R$ kapacitu maximálnì $2\vert R\vert+m$.
Maximální tok je omezen ka¾dým øezem. Tedy i øezem $R$. Proto tok vzroste o $\leq m$.
-
-Proto podle pøedchozího odhadu výpoèet toku $f_i$ trvá $\O(mn)$. Tok se bude poèítat $k$-krát.
-Celková slo¾itost bude $\O(mn\log C)$.
\qed
+Proto podle pøedchozího odhadu výpoèet toku $f_i$ trvá $\O(mn)$. Takový tok se bude poèítat $k$-krát,
+tak¾e celková slo¾itost vyjde $\O(mn\log C)$.
+
\h{Dinicova tabulka}
$$\vbox{\halign{# \hfil \quad &# \hfil \cr
\it verze &\it èas \cr\noalign{\smallskip\hrule\smallskip}
standardní &$\O(n^2m)$ \cr
jednotkové kapacity &$\O(nm)$ \cr
-jednotkové kapacity podruhé &$\O(\sqrt{m}m) = \O(m^{3/2})$ \cr
-jednotkové kapacity, 1 stupeò $\leq 1$ &$\O(\sqrt{n}m)$ \cr
+jednotkové kapacity podruhé &$\O(\sqrt{m}\cdot m) = \O(m^{3/2})$ \cr
+jednotkové kapacity, 1 stupeò $\leq 1$ &$\O(\sqrt{n}\cdot m)$ \cr
jednotkové kapacity veseleji &$\O(n^{2/3}m)$ \cr
-celoèíselné kapacity &$\O(\vert f\vert n + nm)$ \cr
+celoèíselné kapacity &$\O(\vert f\vert\cdot n + nm)$ \cr
celoèíselné kapacity $ \leq C$ &$\O(Cn^2 + mn)$ \cr
celoèíselné kapacity $ \leq C$ &$\O(mn\log C)$ \cr
}}$$
projects / ga.git / blobdiff