From 28da8f41ee35dedffc357dfd8d077b0b0a6da94a Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 25 Jan 2007 22:24:40 +0100 Subject: [PATCH] Drobne upravy sazby, sikovnejsi makro na zasazeni obrazku do odstavce. --- 2-dinic/2-dinic.tex | 20 ++++++++++---------- 5-mst/5-mst.tex | 12 ++++++------ all/preprocess | 2 +- sgr.tex | 20 ++++++++++++++++++++ 4 files changed, 37 insertions(+), 17 deletions(-) diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index d4189b0..e66560f 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -163,9 +163,7 @@ T kapacity je $\O(m^{3/2})$. Tím jsme si pomohli pro øídké grafy. \vbox{ -\vbox to 0pt{\vskip 2ex\rightline{\epsfxsize=0.2\hsize\epsfbox{dinic-vrcholrez.eps}}\vss}\vskip-\baselineskip -\hangindent=-0.25\hsize -\hangafter=-10 +\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) @@ -174,7 +172,7 @@ nebo v 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. +která je ve~svém smìru sama. } @@ -233,22 +231,24 @@ budeme zv 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.4\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$. +\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í: + $$ c_{i+1}(e) = \left\{ \eqalign{ - 2c_i(e), &\hbox{\quad pokud $(k-i-1)$-tý bitík je 0} \cr - 2c_i(e)+1, &\hbox{\quad pokud $(k-i-1)$-tý bitík 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. $$ -\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} - 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¾: @@ -269,7 +269,7 @@ Takov \medskip \centerline{\vbox{\halign{# \hfil \quad &# \hfil \cr -\it verze &\it èas \cr\noalign{\smallskip\hrule\smallskip} +\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 diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index 5357b78..327c325 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -36,8 +36,6 @@ Bu Ostatním hranám nele¾ícím v~kostøe budeme øíkat {\I tì¾ké.} \endlist -\figure{mst2.eps}{Kostra $T$, cesta $T[e]$ a výsledek operace $\(T,e,e')$}{\epsfxsize} - \s{Vìta:} Kostra~$T$ je minimální $\Leftrightarrow$ neexistuje hrana lehká vzhledem k~$T$. Tato vìta nám dává pìknou alternativní definici MST, která místo sèítání vah váhy @@ -52,6 +50,8 @@ 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.eps}{Kostra $T$, cesta $T[e]$ a výsledek operace $\(T,e,e')$}{\epsfxsize} + \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í \. @@ -182,7 +182,7 @@ m \qeditem \endlist -\s{Dùkaz vìty:} +\ss{Dùkaz vìty:} \itemize\ibull \:{\I Zastaví se:} Z~èerveného a modrého lemmatu plyne, ¾e ¾ádnou hranu nikdy nepøebarvíme. Ka¾dým krokem pøibude alespoò jedna obarvená hrana, tak¾e se algoritmus po~nejvý¹e $m$~krocích zastaví. @@ -198,7 +198,7 @@ je to dualita mezi matroidy, kter \h{Klasické algoritmy na hledání MST} -\s{Kruskalùv neboli Hladový:\foot{\rm Mo¾ná hladový s~malým `h', ale tento algoritmus je pradìdeèkem +\ss{Kruskalùv neboli Hladový:\foot{\rm Mo¾ná hladový s~malým `h', ale tento algoritmus je pradìdeèkem v¹ech ostatních hladových algoritmù, tak mu tu èest pøejme.}} \algo @@ -218,7 +218,7 @@ Pot této struktury dává slo¾itost obou operací $\O(\alpha(n))$ amortizovanì, tak¾e celkovì hladový algoritmus dobìhne v~èase $\O(m \log n + m \alpha(n))$. -\s{Borùvkùv:} +\ss{Borùvkùv:} Opìt si budeme pìstovat modrý les, av¹ak tentokrát jej budeme roz¹iøovat ve~fázích. V~jedné fázi nalezneme ke ka¾dému stromeèku nejlevnìj¹í incidentní hranu a v¹echny tyto nalezené hrany naráz pøidáme (aplikujeme nìkolik modrých pravidel najednou). Pokud jsou v¹echny váhy rùzné, cyklus @@ -228,7 +228,7 @@ Po implementujeme lineárním prùchodem celého grafu, dostaneme slo¾itost $\O(m\log n)$. Mimo to lze ka¾dou fázi výteènì paralelizovat. -\s{Jarníkùv:} +\ss{Jarníkùv:} Jarníkùv algoritmus je podobný Borùvkovi, ale s tím rozdílem, ¾e nenecháme rùst celý les, ale jen jeden modrý strom. V~ka¾dém okam¾iku nalezneme nejlevnìj¹í hranu vedoucí mezi stromem a zbytkem grafu a pøidáme ji ke~stromu (modré pravidlo); diff --git a/all/preprocess b/all/preprocess index 60141a7..dd82da8 100755 --- a/all/preprocess +++ b/all/preprocess @@ -11,7 +11,7 @@ foreach my $f (@ARGV) { /^\\input .*sgr\.tex/ && next; /^\\references/ && next; /^\\bye/ && last; - s@\\(figure|fig|epsfbox){([^}]+)}@\\$1\{$d$2}@g; + s@\\(figure|fig|inlinefig|epsfbox){([^}]+)}@\\$1\{$d$2}@g; s@\\(twofigures){([^}]+)}({[^}]+}{[^}]+}){([^}]+)}@\\$1\{$d$2}$3\{$d$4}@g; print; } diff --git a/sgr.tex b/sgr.tex index 1d4fa46..9e8b25d 100644 --- a/sgr.tex +++ b/sgr.tex @@ -100,6 +100,26 @@ \noalign{\smallskip} #2\cr}}}\bigskip} +% Obrazek vlozeny do praveho okraje odstavce {obrazek}{sirka} +% Pouzit na zacatku odstavce a nejlepe celou konstrukci zavrit do vboxu, aby se nerozlomila +\def\inlinefig#1#2{ +\setbox0=\hbox{\epsfxsize=#2\epsfbox{#1}} +\hangindent=-\wd0 +\advance\hangindent by -3em +\dimen0=\ht0 +\advance\dimen0 by 8ex +\advance\dimen0 by \normalbaselineskip +\count0=\dimen0 +\divide\count0 by \normalbaselineskip +\hangafter=-\count0 +\dimen0=\normalbaselineskip +\multiply\dimen0 by \count0 +\vbox to 0pt{} +\nointerlineskip +\vbox to 0pt{\vbox to \dimen0{\vss\rightline{\box0\hskip 1em}\vss}} +\nointerlineskip +} + % Todo \def\todo#1{{\bf TODO: \it #1}} -- 2.39.2