From 634fbc3eb751f64f5b725231783aa2bd2a012d90 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 6 Jun 2018 16:00:08 +0200 Subject: [PATCH] =?utf8?q?Konverze=20obr=C3=A1zk=C5=AF:=20krok=202?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 1-toky/1-toky.tex | 4 ++-- 10-suffix/10-suffix.tex | 2 +- 11-planar/11-planar.tex | 8 ++++---- 2-dinic/2-dinic.tex | 14 +++++++------- 4-ght/4-ght.tex | 10 +++++----- 5-mst/5-mst.tex | 8 ++++---- 8-qheap/8-qheap.tex | 2 +- 9-decomp/9-decomp.tex | 2 +- 8 files changed, 25 insertions(+), 25 deletions(-) diff --git a/1-toky/1-toky.tex b/1-toky/1-toky.tex index 53ec7a8..2a32dc0 100644 --- a/1-toky/1-toky.tex +++ b/1-toky/1-toky.tex @@ -200,7 +200,7 @@ a přidáme novou hranu z~$v^+$ do~$v^-$. Všechny hrany budou mít jednotkové Toky nyní odpovídají vrcholově disjunktním cestám, řezy v~síti separátorům. \qed -\figure{vertex-split.epdf}{Rozdělení vrcholu}{\epsfxsize} +\figure{vertex-split.epdf}{Rozdělení vrcholu}{} Podobně dostaneme neorientované lokální věty (neorientovanou hranu nahradíme orientovanými v~obou směrech) a z~nich pak i globální varianty popisující @@ -226,7 +226,7 @@ a navíc dva nové vrcholy $s$ a~$t$, dále pak všechny původní hrany oriento nové hrany z~$s$ do~všech vrcholů partity~$A$ a ze~všech vrcholů partity~$B$ do~$t$. Kapacity všech hran nastavíme na jedničky: -\fig{bipartitni.epdf}{0.4\hsize} +\fig{bipartitni.epdf}{width 0.4\hsize} Nyní si všimneme, že párování v~původním grafu odpovídají celočíselným tokům v~této síti a že velikost toku je rovna velikosti párování. Stačí tedy nalézt maximální celočíselný diff --git a/10-suffix/10-suffix.tex b/10-suffix/10-suffix.tex index fe26893..a596cc0 100644 --- a/10-suffix/10-suffix.tex +++ b/10-suffix/10-suffix.tex @@ -58,7 +58,7 @@ a žádný z~nich nemůže být vnořený. Takový suffixový strom budeme znač \s{Příklad:} -\figure{baraba.epdf}{Suffixy slova \uv{baraba}: trie, suffixový strom, ST s~dolarem}{\epsfxsize} +\figure{baraba.epdf}{Suffixy slova \uv{baraba}: trie, suffixový strom, ST s~dolarem}{} \>Nyní jak je to s~konstrukcí suffixových stromů: diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index 34573ec..e993bb4 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -100,8 +100,8 @@ rovinnost. \finalfix{ \smallskip -\figure{planar1.epdf}{Před nakreslením zpětných hran \dots}{\epsfxsize} -\figure{planar2.epdf}{\dots\ po něm (čtverečky jsou externí vrcholy)}{\epsfxsize} +\figure{planar1.epdf}{Před nakreslením zpětných hran \dots}{} +\figure{planar2.epdf}{\dots\ po něm (čtverečky jsou externí vrcholy)}{} } Všimněme si, že pokud vede z~nějakého už nakresleného vrcholu ještě nenakreslená hrana, @@ -120,8 +120,8 @@ po~okraji bloku touto hranou (tím vytvoří novou stěnu) a také může sloučit několik bloků do~jednoho, jak je vidět z~obrázků. \separatefix{ -\figure{planar1.epdf}{Před nakreslením zpětných hran \dots}{\epsfxsize} -\figure{planar2.epdf}{\dots\ po něm (čtverečky jsou externí vrcholy)}{\epsfxsize} +\figure{planar1.epdf}{Před nakreslením zpětných hran \dots}{} +\figure{planar2.epdf}{\dots\ po něm (čtverečky jsou externí vrcholy)}{} } Bude se nám hodit, že čas potřebný na~tuto operaci je přímo úměrný počtu diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index 58d7936..552f84e 100644 --- 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í: diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex index 5574816..db4d9fb 100644 --- a/4-ght/4-ght.tex +++ b/4-ght/4-ght.tex @@ -50,7 +50,7 @@ $$r(x,z) \ge \min(r(x,y),r(y,z)).$$ \proof Buď $W$ minimální $xz$-řez. -\fig{4-ght-rez.epdf}{\epsfxsize} +\fig{4-ght-rez.epdf}{} \noindent Vrchol $y$ musí být v~jedné z~komponent, Pokud je v~komponentě s~$x$, pak $r(y,z) \le d(W)$, protože $\d(W)$ je také $yz$-řez. Pokud v~té druhé, analogicky platí $r(x,y) \le d(W)$. @@ -87,7 +87,7 @@ Nejprve však budeme potřebovat jedno užitečné lemma s~hnusně technickým d vrcholy z~$U$. Pak existuje množina vrcholů $W \subseteq U$ taková, že $\d(W)$ je minimální $uv$-řez. \foot{To důležité a netriviální je, že celá $W$ leží v~$U$.} -\fig{4-ght-htl.epdf}{\epsfxsize} +\fig{4-ght-htl.epdf}{} \proof Nechť je $\d(X)$ minimální $uv$-řez. BÚNO můžeme předpokládat, že $s\in U$ a $t\not\in U$, $u\in X$ a $v\not\in X$ a $s\in X$. @@ -180,8 +180,8 @@ hrany, které mají ve $W$ jeden konec. Tím {\I zajímavé} myslíme to, že z~ do $v_1$ \ hrana, která z~něj vedla do množiny $V\setminus W$, případně žádná, pokud do této množiny žádná hrana nevedla.} -\fig{4-ght-g1g2-before.epdf}{0.45\hsize} -\fig{4-ght-g1g2-after.epdf}{0.9\hsize} +\fig{4-ght-g1g2-before.epdf}{width 0.45\hsize} +\fig{4-ght-g1g2-after.epdf}{width 0.9\hsize} \finalfix{\bigskip} Dále vytvoříme množiny vrcholů $R_1=R \cap \overline W$ a $R_2=R \cap W$. Dle indukčního @@ -230,7 +230,7 @@ Protože $\d(W)$ je minimální \st-řez a $\d(X)$ má menší kapacitu, $\d(X)$ $s$ a $t$. Přitom ale separuje $r_1$ a $r_2$, takže musí separovat buď $s$ a $r_1$, nebo $t$ a $r_2$. BÚNO nechť $X$ separuje $s$ a $r_1$. -\fig{4-ght-rezx.epdf}{12cm} +\fig{4-ght-rezx.epdf}{width 12cm} Podívejme se nyní na \PGHT{} $T_1$ (víme, že ten je korektní) a nalezněme v~něm nejlevnější hranu $e$ na cestě spojující $s$ a $r_1$. Tato hrana definuje řez $\d(U)$, což je minimální $sr_1$-řez, podle HTL i v~celém~$G$. Protože $\d(X)$ je $sr_1$-řez, diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index f9a8073..e77eb02 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -50,9 +50,9 @@ Pokud $e^\prime \not\in T$ a $e\in T[e^\prime]$, je $\(T,e,e^\prime)$ opě Stačí si uvědomit, že přidáním $e^\prime$ do~$T$ vznikne kružnice (konkrétně $T[e^\prime] + e^\prime$) a vynecháním libovolné hrany z~této kružnice získáme opět kostru. -\figure{mst2.epdf}{Kostra $T$, cesta $T[e]$ a výsledek operace $\(T,e',e)$}{\epsfxsize} +\figure{mst2.epdf}{Kostra $T$, cesta $T[e]$ a výsledek operace $\(T,e',e)$}{} -\figure{mst1.epdf}{Jeden krok důkazu swapovacího lemmatu}{\epsfxsize} +\figure{mst1.epdf}{Jeden krok důkazu swapovacího lemmatu}{} \s{Lemma o~swapování:} Máme-li libovolné kostry $T$ a $T'$, pak lze z~$T$ dostat $T'$ konečným počtem operací \. @@ -151,7 +151,7 @@ hranu~$e'$ řezu~$C$. Jenže $e'$ je těžší než~$e$, takže operací $\