\input ../sgr.tex
-\prednaska{2}{Dinicùv algoritmus a jeho varianty}{}
+\prednaska{2}{Dinicův algoritmus a jeho varianty}{}
-Maximální tok v~síti u¾ umíme najít pomocí Fordova-Fulkersonova algoritmu
-z~minulé kapitoly. Nyní pojednáme o~efektivnìj¹ím Dinicovì algoritmu
-a o~rùzných jeho variantách pro sítì ve~speciálním tvaru.
+Maximální tok v~síti už umíme najít pomocí Fordova-Fulkersonova algoritmu
+z~minulé kapitoly. Nyní pojednáme o~efektivnějším Dinicově algoritmu
+a o~různých jeho variantách pro sítě ve~speciálním tvaru.
-\h{Dinicùv algoritmus}
+\h{Dinicův algoritmus}
-Dinicùv algoritmus je zalo¾en na~následující my¹lence: Ve~Fordovì-Fulkersonovì algoritmu
-nemusíme pøièítat jen zlep¹ující cesty, ale je mo¾né pøièítat rovnou zlep¹ující
-toky. Nejlépe toky takové, aby je nebylo obtí¾né najít, a~pøitom aby pùvodní tok
-dostateènì obohatily. Vhodnými objekty k~tomuto úèelu jsou blokující toky:
+Dinicův algoritmus je založen na~následující myšlence: Ve~Fordově-Fulkersonově algoritmu
+nemusíme přičítat jen zlepšující cesty, ale je možné přičítat rovnou zlepšující
+toky. Nejlépe toky takové, aby je nebylo obtížné najít, a~přitom aby původní tok
+dostatečně obohatily. Vhodnými objekty k~tomuto účelu jsou blokující toky:
-\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{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èneme s~libovolným tokem~$f$, napøíklad prázdným (v¹ude nulovým).
-\:Iterativnì vylep¹ujeme tok pomocí zlep¹ujících tokù: {\I (vnìj¹í cyklus)}
-\::Sestrojíme sí» rezerv: vrcholy a hrany jsou tyté¾, kapacity jsou urèeny rezervami v~pùvodní síti.
-Dále budeme pracovat s~ní.
-\::Najdeme nejkrat¹í $st$-cestu. Kdy¾ ¾ádná neexistuje, skonèíme.
-\::Proèistíme sí», tj. ponecháme v ní pouze vrcholy a hrany na nejkrat¹ích $st$-cestách.
-\::Najdeme v~proèi¹tìné síti blokující tok $f_B$:
-\:::$f_B \leftarrow \<prázdný tok>$
-\:::Postupnì pøidáváme $st$-cesty: {\I (vnitøní cyklus)}
-\::::Najdeme $st$-cestu. Napø. hladovì -- \uv{rovnou za nosem}.
-\::::Po¹leme co nejvíce po~nalezené cestì.
-\::::Sma¾eme nasycené hrany. (Pozor, smazáním hran mohou vzniknout slepé ulièky,
-èím¾ se zneèistí sí» a nebude fungovat hladové hledání cest.)
-\::::Doèistíme sí».
-\::Zlep¹íme $f$ podle $f_B$
+\:Začneme s~libovolným tokem~$f$, například prázdným (všude nulovým).
+\:Iterativně vylepšujeme tok pomocí zlepšujících toků: {\I (vnější cyklus)}
+\::Sestrojíme síť rezerv: vrcholy a hrany jsou tytéž, kapacity jsou určeny rezervami v~původní síti.
+Dále budeme pracovat s~ní.
+\::Najdeme nejkratší $st$-cestu. Když žádná neexistuje, skončíme.
+\::Pročistíme síť, tj. ponecháme v ní pouze vrcholy a hrany na nejkratších $st$-cestách.
+\::Najdeme v~pročištěné síti blokující tok $f_B$:
+\:::$f_B \leftarrow \<prázdný tok>$
+\:::Postupně přidáváme $st$-cesty: {\I (vnitřní cyklus)}
+\::::Najdeme $st$-cestu. Např. hladově -- \uv{rovnou za nosem}.
+\::::Pošleme co nejvíce po~nalezené cestě.
+\::::Smažeme nasycené hrany. (Pozor, smazáním hran mohou vzniknout slepé uličky,
+čímž se znečistí síť a nebude fungovat hladové hledání cest.)
+\::::Dočistíme síť.
+\::Zlepšíme $f$ podle $f_B$
\endalgo
\finalfix{\vskip-3pt}
-\figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do vrstev}{0.4\hsize}
+\figure{dinic-cistasit.eps}{Pročištěná síť rozdělená do vrstev}{0.4\hsize}
\finalfix{\vskip-6pt}
-\s{Slo¾itost algoritmu:}
-Oznaème $l$ délku nejkrat¹í $st$-cesty, $n$ poèet vrcholù sítì a $m$ poèet hran sítì.
+\s{Složitost algoritmu:}
+Označme $l$ délku nejkratší $st$-cesty, $n$ počet vrcholů sítě a $m$ počet hran sítě.
\itemize\ibull
-\:Jeden prùchod vnitøním cyklem trvá $\O(l)$, co¾ mù¾eme odhadnout jako $\O(n)$, proto¾e v¾dy platí $l \leq n$.
-\:Vnitøní cyklus se provede maximálnì $m$-krát, proto¾e se v¾dy alespoò jedna hrana nasytí
- a ze sítì vypadne, tak¾e krok~6 mimo podkroku~12 bude trvat $\O(mn)$.
-\:Èi¹tìní a doèi¹»ování sítì dohromady provedeme takto:
+\:Jeden průchod vnitřním cyklem trvá $\O(l)$, což můžeme odhadnout jako $\O(n)$, protože vždy platí $l \leq n$.
+\:Vnitřní cyklus se provede maximálně $m$-krát, protože se vždy alespoň jedna hrana nasytí
+ a ze sÃtÄ\9b vypadne, takže krok~6 mimo podkroku~12 bude trvat $\O(mn)$.
+\:Čištění a dočišťování sítě dohromady provedeme takto:
\itemize\ibull
- \:Rozvrstvíme vrcholy podle vzdálenosti od $s$.
- \:Zaøízneme dlouhé cesty (del¹í, ne¾ do vrstvy obsahující $t$).
- \:Dr¾íme si frontu vrcholù, které mají $\deg^+ = 0$ èi $\deg^- = 0$.
- \:Vrcholy z~fronty vybíráme a zahazujeme vèetnì hran, které vedou do/z nich.
- A pøípadnì pøidáváme do~fronty vrcholy, kterým pøi tom klesl jeden ze stupòù na 0.
- Vyma¾ou se tím slepé ulièky, které by vadily v podkroku~9.
+ \:Rozvrstvíme vrcholy podle vzdálenosti od $s$.
+ \:Zařízneme dlouhé cesty (delší, než do vrstvy obsahující $t$).
+ \:Držíme si frontu vrcholů, které mají $\deg^+ = 0$ či $\deg^- = 0$.
+ \:Vrcholy z~fronty vybíráme a zahazujeme včetně hran, které vedou do/z nich.
+ A případně přidáváme do~fronty vrcholy, kterým při tom klesl jeden ze stupňů na 0.
+ Vymažou se tím slepé uličky, které by vadily v podkroku~9.
\endlist
- Takto kroky 5 a 12 dohromady spotøebují èas $\O(m)$.
- \:Jeden prùchod vnìj¹ím cyklem tedy trvá $\O(mn)$.
- \:Jak za chvíli doká¾eme, ka¾dým prùchodem vnìj¹ím cyklem $l$ vzroste, tak¾e prùchodù
- bude maximálnì~$n$ a celý algoritmus tak pobì¾í v~èase $\O(n^2m)$.
+ Takto kroky 5 a 12 dohromady spotřebují čas $\O(m)$.
+ \:Jeden průchod vnějším cyklem tedy trvá $\O(mn)$.
+ \:Jak za chvíli dokážeme, každým průchodem vnějším cyklem $l$ vzroste, takže průchodů
+ bude maximálně~$n$ a celý algoritmus tak poběží v~čase $\O(n^2m)$.
\endlist
\s{Korektnost algoritmu:}
-Kdy¾ se Dinicùv algoritmus zastaví, nemù¾e u¾ existovat ¾ádná zlep¹ující cesta
-(viz krok~4) a tehdy, jak u¾ víme z~analýzy F-F algoritmu, je nalezený tok maximální.
+Když se Dinicův algoritmus zastaví, nemůže už existovat žádná zlepšující cesta
+(viz krok~4) a tehdy, jak už víme z~analýzy F-F algoritmu, je nalezený tok maximální.
-\s{Vìta:}
-V~ka¾dém prùchodu Dinicova algoritmu vzroste $l$ alespoò~o~1.
+\s{Věta:}
+V~každém průchodu Dinicova algoritmu vzroste $l$ alespoň~o~1.
\proof
-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$.
-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, tak 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~následujícím obrázku.
-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 vypadají v¹echny èernì.}
-se zahodí.
-
-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 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
-o~vrstvu zpìt a nikdy nemù¾e skoèit o~více ne¾ jednu vrstvu dopøedu, a~proto je její
-délka alespoò $l+2$. Tím je vìta dokázána. \qed
-
-% posunut dále, aby vy¹la sazba
-\figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a slepé ulièky.}{0.45\hsize}
+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$.
+VÅ¡echny původnà cesty délky~$l$ se bÄ\9bhem průchodu zaruÄ\8denÄ\9b 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, tak 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~následujícím obrázku.
+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 vypadají všechny černě.}
+se zahodí.
+
+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 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
+o~vrstvu zpět a nikdy nemůže skočit o~více než jednu vrstvu dopředu, a~proto je její
+délka alespoň $l+2$. Tím je věta dokázána. \qed
+
+% posunut dále, aby vyšla sazba
+\figure{dinic-neprocistenasit.eps}{Nepročištěná síť. Obsahuje zpětné hrany, hrany uvnitř vrstvy a slepé uličky.}{0.45\hsize}
% HACK
\vskip -10pt
-\figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.4\hsize}
+\figure{dinic-cestashranouzpet.eps}{Cesta užívající novou zpětnou hranu}{0.4\hsize}
-\h{Poznámky}
+\h{Poznámky}
\itemize\ibull
-\:Není potøeba tak puntièkáøské è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
+\:Není potřeba tak puntičkářské č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 prohledáváním do~hloubky:
- \uv{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ání si rovnou udr¾ujeme minimum z rezerv a pøi zpáteèní cestì
- opravujeme kapacity. Snadno zkombinujeme s~prohledáváním do~hloubky.
-\: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 po~Dinicovu algoritmu je¹tì jednu iterací F-F
+\:Je možné dělat prohledávání a čištění současně. Jednoduše prohledáváním do~hloubky:
+ \uv{Hrrr na nÄ\9b!} 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ání si rovnou udržujeme minimum z rezerv a při zpáteční cestě
+ opravujeme kapacity. Snadno zkombinujeme s~prohledáváním do~hloubky.
+\:V průbÄ\9bhu výpoÄ\8dtu udržujeme jen sÃÅ¥ rezerv a tok vypoÄ\8dteme až nakonec z rezerv a kapacit.
+\:Když budeme chtít hledat minimální řez, spustíme po~Dinicovu algoritmu ještě jednu iterací F-F
algoritmu.
\endlist
-\h{Speciální sítì (ubíráme na obecnosti)}
-
-Pøi pøevodu rùzných úloh na~hledání maximálního toku èasto dostaneme sí» v~nìjakém
-speciálním tvaru -- tøeba s~omezenými kapacitami èi stupni vrcholù. Podíváme se
-proto podrobnìji na~chování Dinicova algoritmu v~takových pøípadech a uká¾eme,
-¾e èasto pracuje pøekvapivì efektivnì.
-
-\s{Jednotkové kapacity:}
-Pokud sí» neobsahuje cykly délky~2 (dvojice navzájem opaèných hran), v¹echny rezervy
-jsou jen 0 nebo~1. Pokud obsahuje, mohou rezervy být i dvojky, a~proto sí» upravíme tak,
-¾e ke~ka¾dé hranì pøidáme hranu opaènou s~nulovou kapacitou a rezervu proti smìru
-toku pøiøkneme jí. Vzniknou tím sice paralelní hrany, ale to tokovým algoritmùm
-nikterak nevadí.%
-\foot{Èasto se to implementuje tak, ¾e protismìrné hrany vùbec nevytvoøíme a kdy¾
-hranu nasytíme, tak v~síti rezerv prostì obrátíme její orientaci.}
-
-Pøi hledání blokujícího toku tedy budou mít v¹echny hrany na~nalezené $st$-cestì
-stejnou, toti¾ jednotkovou, rezervu, tak¾e v¾dy z~grafu odstraníme celou cestu.
-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, tím ¾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ò lineární èas pro èi¹tìní.
-Mù¾eme se ale pokusit lépe odhadnout poèet iterací vnìj¹ího cyklu.
-
-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$. 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 nìjaký dost malý ø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í. {\sl (odposlechnuto na~pøedná¹ce)}}
-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$, 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})$.
-
-Tím jsme dokázali, ¾e celková slo¾itost Dinicova algoritmu pro jednotkové
-kapacity je $\O(m^{3/2})$. Tím jsme si pomohli pro øídké grafy.
+\h{Speciální sítě (ubíráme na obecnosti)}
+
+Při převodu různých úloh na~hledání maximálního toku často dostaneme síť v~nějakém
+speciálním tvaru -- třeba s~omezenými kapacitami či stupni vrcholů. Podíváme se
+proto podrobnÄ\9bji na~chovánà Dinicova algoritmu v~takových pÅ\99Ãpadech a ukážeme,
+že často pracuje překvapivě efektivně.
+
+\s{Jednotkové kapacity:}
+Pokud síť neobsahuje cykly délky~2 (dvojice navzájem opačných hran), všechny rezervy
+jsou jen 0 nebo~1. Pokud obsahuje, mohou rezervy být i dvojky, a~proto síť upravíme tak,
+že ke~každé hraně přidáme hranu opačnou s~nulovou kapacitou a rezervu proti směru
+toku přiřkneme jí. Vzniknou tím sice paralelní hrany, ale to tokovým algoritmům
+nikterak nevadí.%
+\foot{Ä\8casto se to implementuje tak, že protismÄ\9brné hrany vůbec nevytvoÅ\99Ãme a když
+hranu nasytíme, tak v~síti rezerv prostě obrátíme její orientaci.}
+
+Při hledání blokujícího toku tedy budou mít všechny hrany na~nalezené $st$-cestě
+stejnou, totiž jednotkovou, rezervu, takže vždy z~grafu odstraníme celou cestu.
+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, tÃm ž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ň lineární čas pro čištění.
+Můžeme se ale pokusit lépe odhadnout počet iterací vnějšího cyklu.
+
+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$. 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 nějaký dost malý ř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í. {\sl (odposlechnuto na~přednášce)}}
+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 Å\99ez. Tedy existuje Å\99ez~$C$, pro nÄ\9bjž $\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})$.
+
+Tím jsme dokázali, že celková složitost Dinicova algoritmu pro jednotkové
+kapacity je $\O(m^{3/2})$. Tím jsme si pomohli pro řídké grafy.
\vbox{
\inlinefig{dinic-vrcholrez.eps}{0.2\hsize}
-\s{Jednotkové kapacity a jeden ze stupòù roven 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í¾ má ka¾dý vrchol~$v\ne s,t$ buïto vstupní
-nebo výstupní stupeò roven jedné.
-Pro takovou sí» mù¾eme pøedchozí odhad je¹tì tro¹ku upravit. 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 tak, ¾e pro ka¾dý vrchol z~vrstvy vezmeme tu hranu,
-která je ve~svém smìru sama.
+\s{Jednotkové kapacity a jeden ze stupňů roven 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íž má každý vrchol~$v\ne s,t$ buďto vstupní
+nebo výstupní stupeň roven jedné.
+Pro takovou síť můžeme předchozí odhad ještě trošku upravit. 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 tak, že pro každý vrchol z~vrstvy vezmeme tu hranu,
+která je ve~svém směru sama.
}
-Po $k$ krocích máme alespoò $k$ vrstev, a~proto 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$ iterací.
-Nyní staèí zvolit $k = \sqrt{n}$ a slo¾itost
-celého algoritmu vyjde $\O(\sqrt{n}\cdot m)$.
-
-Mimochodem, hledání maximálního párování pomocí Dinicova algoritmu je také ekvivalentní
-známému Hopcroft-Karpovì algoritmu \cite{hopcroft:matching}. Ten je zalo¾en na~støídavých
-cestách z~pøedchozí kapitoly a v~ka¾dé iteraci nalezne mno¾inu vrcholovì disjuktních
-nejkrat¹ích støidavých cest, která je maximální vzhledem k~inkluzi.
-Touto mno¾inou pak aktuální párování pøexoruje, èím¾ ho zvìt¹í. V¹imnìte si, ¾e tyto
-mno¾iny cest odpovídají právì blokujícím tokùm v~proèi¹tìné síti rezerv, tak¾e mù¾eme
-i~zde pou¾ít ná¹ odhad na~poèet iterací.
-
-\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é
-sousední vrstvy a v¹echny hrany mezi nimi budou tvoøit námi hledaný malý øez.
-Budeme tentokrát pøedpokládat, ¾e na¹e sí» není multigraf, pøípadnì ¾e
-násobnost hran je alespoò omezena konstantou.
-
-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:
+Po $k$ krocích máme alespoň $k$ vrstev, a~proto 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$ iterací.
+Nynà staÄ\8dà zvolit $k = \sqrt{n}$ a složitost
+celého algoritmu vyjde $\O(\sqrt{n}\cdot m)$.
+
+Mimochodem, hledání maximálního párování pomocí Dinicova algoritmu je také ekvivalentní
+známému Hopcroft-Karpově algoritmu \cite{hopcroft:matching}. Ten je založen na~střídavých
+cestách z~předchozí kapitoly a v~každé iteraci nalezne množinu vrcholově disjuktních
+nejkratších střidavých cest, která je maximální vzhledem k~inkluzi.
+Touto množinou pak aktuálnà párovánà pÅ\99exoruje, Ä\8dÃmž ho zvÄ\9btÅ¡Ã. VÅ¡imnÄ\9bte si, že tyto
+množiny cest odpovÃdajà právÄ\9b blokujÃcÃm tokům v~proÄ\8diÅ¡tÄ\9bné sÃti rezerv, takže můžeme
+i~zde použít náš odhad na~počet iterací.
+
+\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é
+sousední vrstvy a všechny hrany mezi nimi budou tvořit námi hledaný malý řez.
+Budeme tentokrát pÅ\99edpokládat, že naÅ¡e sÃÅ¥ nenà multigraf, pÅ\99ÃpadnÄ\9b že
+násobnost hran je alespoň omezena konstantou.
+
+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.$$
-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$,
+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Å\99Ã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{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.
-Cestu najdeme v èase $\O(n)$. Celkem na~hledání
-cest spotøebujeme $\O(\vert f\vert\cdot n)$ za celou dobu bìhu algoritmu.
-
-Nesmíme ale zapomenout na èi¹tìní. V jedné iteraci velkého cyklu nás stojí èi¹tìní $\O(m)$ a velkých
-iterací je $\leq n$. Proto celková slo¾itost algoritmu èiní $\O(\vert f\vert n + 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
+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{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.
+Cestu najdeme v čase $\O(n)$. Celkem na~hledání
+cest spotřebujeme $\O(\vert f\vert\cdot n)$ za celou dobu běhu algoritmu.
+
+Nesmíme ale zapomenout na čištění. V jedné iteraci velkého cyklu nás stojí čištění $\O(m)$ a velkých
+iterací je $\leq n$. Proto celková složitost algoritmu činí $\O(\vert f\vert n + 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{©kálování kapacit}
+\h{Škálování kapacit}
-Pokud jsou kapacity hran vìt¹í celá èísla omezená nìjakou konstantou~$C$, mù¾eme si pomoci následujícím algoritmem.
-Jeho základní my¹lenka je podobná, jako u~tøídìní èísel postupnì po øádech pomocí
-radix-sortu neboli pøihrádkového tøídìní. Pro jistotu si ho pøipomeòme. Algoritmus nejprve setøídí èísla podle poslední
-(nejménì významné) cifry, poté podle pøedposlední, pøedpøedposlední a tak dále.
+Pokud jsou kapacity hran větší celá čísla omezená nějakou konstantou~$C$, můžeme si pomoci následujícím algoritmem.
+Jeho základní myšlenka je podobná, jako u~třídění čísel postupně po řádech pomocí
+radix-sortu neboli přihrádkového třídění. Pro jistotu si ho připomeňme. Algoritmus nejprve setřídí čísla podle poslední
+(nejméně významné) 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.4\hsize}
+%\figure{dinic-sort.eps}{Kroky postupného třídění podle řádů}{0.4\hsize}
-V na¹em pøípadì budeme postupnì budovat sítì èím dál podobnìj¹í zadané
-síti a v~nich poèítat toky, a¾ nakonec získáme tok pro ni.
+V našem případě budeme postupně budovat sítě čím dál podobnější zadané
+síti a v~nich počítat toky, až nakonec získáme tok pro ni.
-Pøesnìji: 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ì.
-Pøitom po~ka¾dém posunu zavoláme Dinicùv algoritmus, aby dopoèítal maximální tok.
-Pomocí pøedchozího odhadu uká¾eme, ¾e jeden takový krok nebude pøíli¹ drahý.
+Přesněji: 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ě.
+Přitom po~každém posunu zavoláme Dinicův algoritmus, aby dopočítal maximální tok.
+Pomocí předchozího odhadu ukážeme, že jeden takový krok 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.3\hsize}
+\figure{dinic-scaling-original.eps}{Původní síť, na hranách jsou jejich kapacity v binárním zápisu}{0.3\hsize}
-Oznaème $k$ index nejvy¹¹ího bitu v~zápisu kapacit v~zadané síti ($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, a¾ $G_k$ je pùvodní sí» $G$.
+Označme $k$ index nejvyššího bitu v~zápisu kapacit v~zadané síti ($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, až $G_k$ je původní síť $G$.
-\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.9\hsize}
+\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.9\hsize}
-\>Pøitom pro kapacity v~jednotlivých sítích platí:
+\>Přitom pro kapacity v~jednotlivých sítích platí:
$$ c_{i+1}(e) = \left\{
\eqalign{
- 2c_i(e), &\hbox{\quad pokud $(k-i-1)$-tý bit je 0,} \cr
- 2c_i(e)+1, &\hbox{\quad pokud $(k-i-1)$-tý bit je 1.} \cr}
+ 2c_i(e), &\hbox{\quad pokud $(k-i-1)$-tý bit je 0,} \cr
+ 2c_i(e)+1, &\hbox{\quad pokud $(k-i-1)$-tý bit je 1.} \cr}
\right.
$$
-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ý, toti¾:
+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ý, totiž:
\s{Lemma:} $\vert f_i\vert - \vert 2f_{i-1}\vert \leq m.$
\proof
-Vezmeme minimální øez $R$ v~$G_{i-1}$. Podle F-F vìty víme, ¾e $\vert f_{i-1}\vert = \vert R\vert$.
-Øez $R$ obsahuje $\leq m$ hran, a~tedy v~$G_{i}$ má tentý¾ øez kapacitu maximálnì $2\vert R\vert+m$.
-Maximální tok je omezen ka¾dým øezem, tedy i øezem $R$, a~proto tok vzroste nejvý¹e o~$m$.
+Vezmeme minimálnà Å\99ez $R$ v~$G_{i-1}$. Podle F-F vÄ\9bty vÃme, že $\vert f_{i-1}\vert = \vert R\vert$.
+Řez $R$ obsahuje $\leq m$ hran, a~tedy v~$G_{i}$ má tentýž řez kapacitu maximálně $2\vert R\vert+m$.
+Maximální tok je omezen každým řezem, tedy i řezem $R$, a~proto tok vzroste nejvýše o~$m$.
\qed
-Podle pøedchozího odhadu pro celoèíselné kapacity výpoèet toku $f_i$ trvá $\O(mn)$.
-Takový tok se bude poèítat $k$-krát, proèe¾ celková slo¾itost vyjde $\O(mn\log C)$.
+Podle předchozího odhadu pro celočíselné kapacity výpočet toku $f_i$ trvá $\O(mn)$.
+Takový tok se bude poÄ\8dÃtat $k$-krát, proÄ\8dež celková složitost vyjde $\O(mn\log C)$.
-\h{Algoritmus tøí Indù}
+\h{Algoritmus tří Indů}
-Pøekvapení na~konec: Dinicùv algoritmus lze pomìrnì snadno zrychlit i ve~zcela obecném
-pøípadì. Malhotra, Kumar a Maheshwari vymysleli efektivnìj¹í algoritmus \cite{threeinds}
-na~hledání blokujícího toku ve~vrstevnaté síti, který bì¾í v~èase $\O(n^2)$ a pou¾ijeme-li
-ho v~Dinicovì algoritmu, zrychlíme hledání maximálního toku na~$\O(n^3)$.
-Tento algoritmus ve¹el do~dìjin pod názvem Metoda tøí Indù.
+Překvapení na~konec: Dinicův algoritmus lze poměrně snadno zrychlit i ve~zcela obecném
+případě. Malhotra, Kumar a Maheshwari vymysleli efektivnější algoritmus \cite{threeinds}
+na~hledánà blokujÃcÃho toku ve~vrstevnaté sÃti, který bÄ\9bžà v~Ä\8dase $\O(n^2)$ a použijeme-li
+ho v~Dinicově algoritmu, zrychlíme hledání maximálního toku na~$\O(n^3)$.
+Tento algoritmus vešel do~dějin pod názvem Metoda tří Indů.
-Mìjme tedy nìjakou vrstevnatou sí». Zaèneme s~nulovým tokem a budeme ho postupnì zlep¹ovat.
-Prùbì¾nì si budeme udr¾ovat rezervy hran~$r(e)$\foot{poèítáme pouze rezervu ve~smìru hrany, nebo»
-nám staèí najít blokující tok, ne~nutnì maximální} a také následující rezervy vrcholù:
+Mějme tedy nějakou vrstevnatou síť. Začneme s~nulovým tokem a budeme ho postupně zlepšovat.
+Průběžně si budeme udržovat rezervy hran~$r(e)$\foot{počítáme pouze rezervu ve~směru hrany, neboť
+nám stačí najít blokující tok, ne~nutně maximální} a také následující rezervy vrcholů:
-\s{Definice:} $r^+(v)$ je souèet rezerv v¹ech hran vstupujících do~$v$, $r^-(v)$ souèet
-rezerv hran vystupujících z~$v$ a koneènì $r(v):=\min(r^+(v),r^-(v))$.
+\s{Definice:} $r^+(v)$ je součet rezerv všech hran vstupujících do~$v$, $r^-(v)$ součet
+rezerv hran vystupujících z~$v$ a konečně $r(v):=\min(r^+(v),r^-(v))$.
-V~ka¾dé iteraci algoritmu nalezneme vrchol s~nejni¾¹ím~$r(v)$ a zvìt¹íme tok tak, aby se
-tato rezerva vynulovala. Za~tímto úèelem nejdøíve pøepravíme $r(v)$ jednotek toku ze~zdroje
-do~$v$: u~ka¾dého vrcholu~$w$ si budeme pamatovat {\I plán} $p(w)$, co¾ bude mno¾ství
-tekutiny, které potøebujeme dostat ze~zdroje do~$w$. Nejdøíve budou plány v¹ude nulové
-a¾ na~$p(v)=r(v)$. Pak budeme postupovat po~vrstvách smìrem ke~zdroji a plány v¹ech
-vrcholù splníme tak, ¾e je pøevedeme na~plány vrcholù v~následující vrstvì, a¾ doputujeme
-ke~zdroji, jeho¾ plán je splnìn triviálnì. Nakonec analogickým zpùsobem protlaèíme $r(v)$
-jednotek z~$v$ do~spotøebièe.
+V~každé iteraci algoritmu nalezneme vrchol s~nejnižším~$r(v)$ a zvětšíme tok tak, aby se
+tato rezerva vynulovala. Za~tímto účelem nejdříve přepravíme $r(v)$ jednotek toku ze~zdroje
+do~$v$: u~každého vrcholu~$w$ si budeme pamatovat {\I plán} $p(w)$, což bude množství
+tekutiny, které potřebujeme dostat ze~zdroje do~$w$. Nejdříve budou plány všude nulové
+až na~$p(v)=r(v)$. Pak budeme postupovat po~vrstvách směrem ke~zdroji a plány všech
+vrcholů splnÃme tak, že je pÅ\99evedeme na~plány vrcholů v~následujÃcà vrstvÄ\9b, až doputujeme
+ke~zdroji, jehož plán je splněn triviálně. Nakonec analogickým způsobem protlačíme $r(v)$
+jednotek z~$v$ do~spotřebiče.
-Bìhem výpoètu prùbì¾nì pøepoèítáváme v¹echna $r^+$, $r^-$ a~$r$ podle toho, jak se mìní
-rezervy jednotlivých hran (pøi ka¾dé úpravì rezervy to zvládneme v~konstantním èase)
-a sí» èistíme stejnì jako u~Dinicova algoritmu.
+Během výpočtu průběžně přepočítáváme všechna $r^+$, $r^-$ a~$r$ podle toho, jak se mění
+rezervy jednotlivých hran (při každé úpravě rezervy to zvládneme v~konstantním čase)
+a síť čistíme stejně jako u~Dinicova algoritmu.
\finalfix{\goodbreak}
-\s{Algoritmus:} (hledání blokujícího toku ve~vrstevnaté síti podle tøí Indù)
+\s{Algoritmus:} (hledání blokujícího toku ve~vrstevnaté síti podle tří Indů)
\algo
-\:$f_B\leftarrow\<prázdný tok>$.
-\:Spoèítáme rezervy v¹ech hran a $r^+$, $r^-$ a $r$ v¹ech vrcholù. (Tyto hodnoty
- budeme posléze udr¾ovat pøi ka¾dé zmìnì toku po~hranì.)
-\:Dokud v~síti existují vrcholy s~nenulovou rezervou, vezmeme vrchol $v$ s~nejmen¹ím $r(v)$
- a provedeme pro nìj: {\I (vnìj¹í cyklus)}
-\::Pøevedeme $r(v)$ jednotek toku z~$s$ do~$v$ následovnì:
-\:::Polo¾íme $p(v)\leftarrow r(v)$, $p(\cdot)=0$.
-\:::Procházíme vrcholy sítì po~vrstvách od~$v$ smìrem k~$s$. Pro ka¾dý vrchol~$w$ provedeme:
+\:$f_B\leftarrow\<prázdný tok>$.
+\:Spočítáme rezervy všech hran a $r^+$, $r^-$ a $r$ všech vrcholů. (Tyto hodnoty
+ budeme posléze udržovat při každé změně toku po~hraně.)
+\:Dokud v~síti existují vrcholy s~nenulovou rezervou, vezmeme vrchol $v$ s~nejmenším $r(v)$
+ a provedeme pro něj: {\I (vnější cyklus)}
+\::Převedeme $r(v)$ jednotek toku z~$s$ do~$v$ následovně:
+\:::Položíme $p(v)\leftarrow r(v)$, $p(\cdot)=0$.
+\:::Procházíme vrcholy sítě po~vrstvách od~$v$ směrem k~$s$. Pro každý vrchol~$w$ provedeme:
\::::Dokud $p(w)>0$:
-\:::::Vezmeme libovolnou hranu $uw$ a tok po~ní zvý¹íme o~$\delta=\min(r(uw), p(w))$. Tím se
- $p(w)$ sní¾í~o~$\delta$ a $p(u)$ zvý¹í~o~$\delta$.
-\:::::Pokud se hrana~$uw$ nasytila, odstraníme jí ze sítì a sí» doèistíme.
-\::Analogicky pøevedeme $r(v)$ jednotek z~$v$ do~$t$.
+\:::::Vezmeme libovolnou hranu $uw$ a tok po~ní zvýšíme o~$\delta=\min(r(uw), p(w))$. Tím se
+ $p(w)$ sníží~o~$\delta$ a $p(u)$ zvýší~o~$\delta$.
+\:::::Pokud se hrana~$uw$ nasytila, odstraníme jí ze sítě a síť dočistíme.
+\::Analogicky převedeme $r(v)$ jednotek z~$v$ do~$t$.
\endalgo
-\s{Analýza:} Nejprve si v¹imneme, ¾e cyklus v~kroku~8 opravdu doká¾e vynulovat $p(w)$.
-Souèet v¹ech $p(w)$ pøes ka¾dou vrstvu je toti¾ nejvý¹e roven $r(v)$, tak¾e speciálnì ka¾dé
-$p(w)\le r(v)$. Jen¾e $r(v)$ jsme vybrali jako nejmen¹í, tak¾e $p(w)\le r(v)\le r(w)\le r^+(w)$,
-a~proto je plánovaný tok kudy pøivést. Proto se algoritmus zastaví a vydá blokující tok.
-
-Zbývá odhadnout èasovou slo¾itost: Kdy¾ oddìlíme pøevádìní plánù po~hranách (kroky 7--9),
-zbytek jedné iterace vnìj¹ího cyklu trvá~$\O(n)$ a tìchto iterací je nejvý¹e~$n$. V¹echna pøevedení
-plánu si rozdìlíme na~ta, kterými se nìjaká hrana nasytila, a~ta, která skonèila vynulováním $p(w)$.
-Tìch prvních je $\O(m)$, proto¾e ka¾dou takovou hranu vzápìtí odstraníme a èi¹tìní, jak u¾ víme,
-trvá také lineárnì dlouho. Druhý pøípad nastane pro ka¾dý vrchol nejvý¹e jednou za~iteraci.
-Dohromady tedy trvají v¹echna pøevedení $\O(n^2)$, stejnì jako zbytek algoritmu.
+\s{Analýza:} Nejprve si všimneme, že cyklus v~kroku~8 opravdu dokáže vynulovat $p(w)$.
+Součet všech $p(w)$ přes každou vrstvu je totiž nejvýše roven $r(v)$, takže speciálně každé
+$p(w)\le r(v)$. Jenže $r(v)$ jsme vybrali jako nejmenÅ¡Ã, takže $p(w)\le r(v)\le r(w)\le r^+(w)$,
+a~proto je plánovaný tok kudy přivést. Proto se algoritmus zastaví a vydá blokující tok.
+
+Zbývá odhadnout časovou složitost: Když oddělíme převádění plánů po~hranách (kroky 7--9),
+zbytek jedné iterace vnějšího cyklu trvá~$\O(n)$ a těchto iterací je nejvýše~$n$. Všechna převedení
+plánu si rozdělíme na~ta, kterými se nějaká hrana nasytila, a~ta, která skončila vynulováním $p(w)$.
+Těch prvních je $\O(m)$, protože každou takovou hranu vzápětí odstraníme a čištění, jak už víme,
+trvá také lineárně dlouho. Druhý případ nastane pro každý vrchol nejvýše jednou za~iteraci.
+Dohromady tedy trvají všechna převedení $\O(n^2)$, stejně jako zbytek algoritmu.
\qed
-\h{Pøehled variant Dinicova algoritmu}
+\h{Přehled variant Dinicova algoritmu}
\medskip
\centerline{\vbox{\halign{# \hfil \quad &# \hfil \cr
-\it varianta &\it èas \cr\noalign{\smallskip\hrule\smallskip}
-standardní &$\O(n^2m)$ \cr
-jednotkové kapacity &$\O(\sqrt{m}\cdot m) = \O(m^{3/2})$ \cr
-jednotkové kapacity, 1 stupeò $\leq 1$ &$\O(\sqrt{n}\cdot m)$ \cr
-jednotkové kapacity, prostý graf &$\O(n^{2/3}m)$ \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$ (¹kálování)&$\O(mn\log C)$ \cr
-tøi Indové &$\O(n^3)$ \cr
+\it varianta &\it čas \cr\noalign{\smallskip\hrule\smallskip}
+standardní &$\O(n^2m)$ \cr
+jednotkové kapacity &$\O(\sqrt{m}\cdot m) = \O(m^{3/2})$ \cr
+jednotkové kapacity, 1 stupeň $\leq 1$ &$\O(\sqrt{n}\cdot m)$ \cr
+jednotkové kapacity, prostý graf &$\O(n^{2/3}m)$ \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$ (škálování)&$\O(mn\log C)$ \cr
+tři Indové &$\O(n^3)$ \cr
}}}
\references
projects / ga.git / blobdiff