\endalgo
\finalfix{\vskip-3pt}
-\figure{dinic-cistasit.epdf}{Pročištěná síť rozdělená do vrstev}{0.4\hsize}
+\figure{dinic-cistasit.epdf}{Pročištěná síť rozdělená do vrstev}{width 0.4\hsize}
\finalfix{\vskip-6pt}
\s{Složitost algoritmu:}
délka alespoň $l+2$. Tím je věta dokázána. \qed
% posunut dále, aby vyšla sazba
-\figure{dinic-neprocistenasit.epdf}{Nepročištěná síť. Obsahuje zpětné hrany, hrany uvnitř vrstvy a slepé uličky.}{0.45\hsize}
+\figure{dinic-neprocistenasit.epdf}{Nepročištěná síť. Obsahuje zpětné hrany, hrany uvnitř vrstvy a slepé uličky.}{width 0.45\hsize}
% HACK
\vskip -10pt
-\figure{dinic-cestashranouzpet.epdf}{Cesta užívající novou zpětnou hranu}{0.4\hsize}
+\figure{dinic-cestashranouzpet.epdf}{Cesta užívající novou zpětnou hranu}{width 0.4\hsize}
\h{Poznámky}
kapacity je $\O(m^{3/2})$. Tím jsme si pomohli pro řídké grafy.
\vbox{
-\inlinefig{dinic-vrcholrez.epdf}{0.2\hsize}
+\inlinefig{dinic-vrcholrez.epdf}{width 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)
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.epdf}{Kroky postupného třídění podle řádů}{0.4\hsize}
+%\figure{dinic-sort.epdf}{Kroky postupného třídění podle řádů}{width 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.
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.epdf}{Původní síť, na hranách jsou jejich kapacity v binárním zápisu}{0.3\hsize}
+\figure{dinic-scaling-original.epdf}{Původní síť, na hranách jsou jejich kapacity v binárním zápisu}{width 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$.
-\figure{dinic-scaling-g.epdf}{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.epdf}{Sítě $G_0$, $G_1$ a $G_2$, jak vyjdou pro síť z~předchozího obrázku}{width 0.9\hsize}
\>Přitom pro kapacity v~jednotlivých sítích platí: