\:$g'(e) := g(e) - \delta$,
\:$g'(\overleftarrow{e}) := g(\overleftarrow{e}) - \delta$.
\endlist
-
- A tímto jsme to pøevedli na~nìkterý z~pøedchozích pøípadù, které u¾ umíme vyøe¹it.
+
+ Tok $g'$ nyní spadá pod nìkterý z~pøedchozích pøípadù, které u¾ umíme vyøe¹it.
\endlist
\:Teï musíme je¹tì dokázat, ¾e nový tok neporu¹uje Kirchhoffovy zákony: $$\forall v~\in V \setminus \{z,s\}: f'^\Delta(v)=0.$$
% neboli $$\forall v~\in V \setminus \{z,s\}: \sum_{u: uv \in E}{f'(uv)}=\sum_{u: vu \in E}{f'(vu)}.$$
- Vezmìme si~libovolnou hranu~$e = uv \in E$, ¾e $e=uv$. Uvìdomme si, ¾e pøi~pøechodu z~$f(e)$ na~$f'(e)$ a~z~$f(\overleftarrow{e})$ na~$f'(\overleftarrow{e})$ bylo:
+ Vezmìme si~libovolnou hranu~$e = uv \in E$. Uvìdomme si, ¾e pøi~pøechodu z~$f(e)$ na~$f'(e)$ a~z~$f(\overleftarrow{e})$ na~$f'(\overleftarrow{e})$ bylo:
\itemize\idot
\:$f^\Delta(u)$ sní¾eno o~$g(e)$
\:$f^\Delta(v)$ zvý¹eno o~$g(e)$.
\algo
\:Rozdìlíme vrcholy do~vrstev podle vzdálenosti od~$z$.
-\:Odstraníme vrstvy za~$s$, hrany do~minulých vrstev a~hrany uvnitø vrstev.
+\:Odstraníme vrstvy za~$s$ (tedy vrcholy, které jsou od~$z$ vzdálenìj¹í ne¾~$s$), hrany do~minulých vrstev a~hrany uvnitø vrstev.
\:Odstraníme \uv{slepé ulièky}, tedy vrcholy s~$\deg^{out}(v) = 0$, a~to opakovanì pomocí fronty. (Nejdøíve zaøadíme do~fronty v¹echny vrcholy s~ $\deg^{out}(v) = 0$. Pak dokud není fronta prázdná, v¾dy vybereme vrchol~$v$ z~fronty, odstraníme~$v$ a~v¹echny hrany~$uv$. Pro~ka¾dý takový vrchol~$u$ zkontrolujeme, zda se~tím nesní¾il výstupní stupeò vrcholu~$u$ na~nulu ($\deg^{out}(u) = 0$). Pokud sní¾il, tak ho zaøadíme do~fronty.)
\endalgo
\figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a~slepé ulièky.}{0.45\hsize}
-Hledání blokujícího toku zaèneme s~tokem nulovým. Pak vezmeme v¾dy orientovanou cestu ze~zdroje do~stoku v~síti~$C$. V~této cestì najdeme hranu s~nejni¾¹í hodnotou výrazu $r(e) - g(e)$ (neboli $c(e) - f(e)$ v~pùvodní síti). Tuto hodnotu oznaèíme~$\varepsilon$. Pak ke~ v¹em hranám pøièteme~$\varepsilon$. Pokud tok~$g$ na~nìjaké hranì dosáhne kapacity hrany, co¾ je zde~$r(e)$, tak hranu vyma¾eme. Následnì sí» doèistíme, aby splòovala podmínky vrstevnaté sítì. A~pokud je¹tì existuje nìjaká orientovaná cesta ze~zdroje do~stoku, tak opìt pokraèujeme s~touto cestou.
+Hledání blokujícího toku zaèneme s~tokem nulovým. Pak vezmeme v¾dy orientovanou cestu ze~zdroje do~stoku v~síti~$C$. V~této cestì najdeme hranu s~nejni¾¹í hodnotou výrazu $r(e) - g(e)$ (neboli $c(e) - f(e)$ v~pùvodní síti). Tuto hodnotu oznaèíme~$\varepsilon$. Pak ke~ v¹em hranám na~této cestì pøièteme~$\varepsilon$. Pokud tok~$g$ na~nìjaké hranì dosáhne kapacity hrany, co¾ je zde~$r(e)$, tak hranu vyma¾eme. Následnì sí» doèistíme, aby splòovala podmínky vrstevnaté sítì. A~pokud je¹tì existuje nìjaká orientovaná cesta ze~zdroje do~stoku, tak opìt pokraèujeme s~touto cestou.
\s{Algoritmus hledání blokujícího toku}
\s{Èasová slo¾itost} Rozeberme si~jednotlivé kroky algoritmu.
\numlist{\ndotted}
-\:Inicializace toku~$f$ \dots $\O(1)$.
+\:Inicializace toku~$f$ \dots $\O(m)$.
\:Sestrojení sítì rezerv a~smazání hran s~nulovou rezervou \dots $\O(m + n)$.
\:Najití nejkrat¹í cesty (prohledáváním do~¹íøky) \dots $\O(m + n)$.
\:Zkontrolování délky nejkrat¹í cesty \dots $\O(1)$.
\endlist
\:Najití blokujícího toku~$g$ \dots $\O(m \cdot n)$.
\numlist{\ndotted}
- \:Inicializace toku~$g$ \dots $\O(1)$.
+ \:Inicializace toku~$g$ \dots $\O(m)$.
\:Najití orientované cesty v~proèi¹tìné síti rezerv (staèí vzít libovolnou cestu ze~zdroje, nebo» ka¾dá z~nich v~této síti vede do~stoku) \dots $\O(n)$.
\:Výbìr minima z~výrazu $r(e) - g(e)$ pøes v¹echny hrany cesty -- ta mù¾e být dlouhá nejvý¹e~$n$ \dots $\O(n)$.
\:Pøepoèítání v¹ech hran cesty \dots $\O(n)$.
Podíváme se~na~prùbìh jednoho prùchodu vnìj¹ím cyklem. Délku aktuálnì nejkrat¹í cesty ze~zdroje do~stoku oznaème~$l$. V¹echny pùvodní cesty délky~$l$ se~bìhem prùchodu zaruèenì nasytí, proto¾e tok~$g$ 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.
-Hrany mohou pøibývat jen tehdy, kdy¾ jsme po~opaèné hranì nìco poslali. Ale my nìco posíláme po~hranách pouze z~vrstvy do~té následující. Hrany tedy pøibývají do~minulé vrstvy..
+Hrany mohou pøibývat jen tehdy, kdy¾ jsme po~opaèné hranì nìco poslali. Ale my nìco posíláme po~hranách pouze z~vrstvy do~té následující. Hrany tedy pøibývají do~minulé vrstvy.
-Vznikem nových hran by proto mohly vzniknout nové cesty ze~zdroje do~stoku, které pou¾ívají zpìtné hrany. Jen¾e cesta ze~zdroje do~stoku, 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$. Pokud cesta novou zpìtnou hranu nepou¾ije má buï délku~$> l$, co¾ je v~poøádku, nebo má délku~$= l$, pak je zablokovaná.
+Vznikem nových hran by proto mohly vzniknout nové cesty ze~zdroje do~stoku, které pou¾ívají zpìtné hrany. Jen¾e cesta ze~zdroje do~stoku, 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$. Pokud cesta novou zpìtnou hranu nepou¾ije, má buï délku~$> l$, co¾ je v~poøádku, nebo má délku~$= l$, pak je zablokovaná.
Tím je lemma dokázáno.
\qed
projects / ads2.git / blobdiff