Konverze obrázků: krok 2

[ga.git] / 2-dinic / 2-dinic.tex

diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex
index 58d7936fef656a5a4a6c6de3e769637cdd27213f..552f84ee511bdd27cbc2da8146c895ccede87532 100644 (file)
--- a/2-dinic/2-dinic.tex
+++ b/2-dinic/2-dinic.tex
@@ -38,7 +38,7 @@ Dále budeme pracovat s~ní.
 \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:}
@@ -94,12 +94,12 @@ o~vrstvu zpět a nikdy nemůže skočit o~více než jednu vrstvu dopředu, a~pr
 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}
 
@@ -169,7 +169,7 @@ 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.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)
@@ -235,7 +235,7 @@ Jeho základní myšlenka je podobná, jako u~třídění čísel postupně po 
 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.
@@ -245,14 +245,14 @@ budeme zvětšovat kapacity bit po bitu v~binárním zápisu až k~jejich skute
 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í: