From d81fc4332bc40324dbcbc8d6e1059632bde705c4 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 16 Jan 2007 21:56:48 +0100 Subject: [PATCH] Uvody na zacatku kapitol a ruzne mensi typograficke upravy. --- 1-toky/1-toky.tex | 13 ++++++++----- 10-decomp/10-decomp.tex | 8 ++++---- 11-planar/11-planar.tex | 14 +++++++------- 2-dinic/2-dinic.tex | 15 +++++++++------ 3-bipcon/3-bipcon.tex | 10 +++++----- 4-ght/4-ght.tex | 31 +++++++++++++++---------------- 5-mst/5-mst.tex | 38 ++++++++++++++++++-------------------- 6-borjar/6-borjar.tex | 3 +++ 7-ram/7-ram.tex | 6 +++--- 8-qheap/8-qheap.tex | 4 ++-- 9-suffix/9-suffix.tex | 14 +++++++------- sgr.tex | 6 ++++++ 12 files changed, 87 insertions(+), 75 deletions(-) diff --git a/1-toky/1-toky.tex b/1-toky/1-toky.tex index 63d6f7d..bf7abce 100644 --- a/1-toky/1-toky.tex +++ b/1-toky/1-toky.tex @@ -54,7 +54,7 @@ velikosti) a {\I minim \s{Vìtièka:} V~ka¾dé síti existuje maximální tok a minimální øez. -\s{Dùkaz:} Existence minimálního øezu je triviální, proto¾e øezù v~ka¾dé síti je koneènì mnoho; +\proof Existence minimálního øezu je triviální, proto¾e øezù v~ka¾dé síti je koneènì mnoho; pro toky v~sítích s~reálnými kapacitami to ov¹em není samozøejmost a je k~tomu potøeba trocha matematické analýzy (v~prostoru v¹ech ohodnocení hran tvoøí toky kompaktní mno¾inu, velikost toku je lineární funkce a~tedy i spojitá, proèe¾ nabývá maxima). Pro racionální kapacity dostaneme tuto vìtièku jako dùsledek @@ -72,7 +72,7 @@ Stejn \s{Lemma:} Pro ka¾dý øez $C$ platí, ¾e $\vert f\vert = -f^\Delta(C) \le \vert C \vert$. -\s{Dùkaz:} První èást indukcí: ka¾dý øez mù¾eme získat postupným pøidáváním vrcholù do~triviálního øezu $\{s\}$ +\proof První èást indukcí: ka¾dý øez mù¾eme získat postupným pøidáváním vrcholù do~triviálního øezu $\{s\}$ [tedy pøesouváním vrcholù zprava doleva], a~to, jak uká¾e jednoduchý rozbor pøípadù, nezmìní $f^\Delta$. Druhá èást: $-f^\Delta(C) = f^-(C) - f^+(C) \le f^-(C) \le \vert C \vert.$ \qed @@ -82,9 +82,10 @@ n \s{Vìta (Ford, Fulkerson):} V~ka¾dé síti je velikost maximálního toku rovna velikosti minimálního øezu. -\s{Dùkaz:} Jednu nerovnost jsme dokázali v~pøedchozím lemmatu, druhá plyne z~duality lineárního +\proof Jednu nerovnost jsme dokázali v~pøedchozím lemmatu, druhá plyne z~duality lineárního programování [max. tok a min. øez jsou navzájem duální úlohy], ale k~pìknému kombinatorickému dùkazu pùjde opìt pou¾ít Ford-Fulkersonùv algoritmus. +\qed \h{Ford-Fulkersonùv algoritmus} @@ -164,6 +165,8 @@ rovna velikosti minim \h{Øezy, separátory a $k$-souvislost} +Teorie tokù nám také poslou¾í ke~zkoumání násobné souvislosti grafù. + \s{Definice:} Pro ka¾dý neorientovaný graf $G$ a libovolné jeho vrcholy $s,t$ zavedeme: \itemize\ibull \:{\I $st$-øez} je mno¾ina hran $F$ taková, ¾e v~grafu $G-F$ jsou @@ -203,7 +206,7 @@ Bu $st$-øezu rovna maximálnímu poètu hranovì disjunktních $st$-cest.\foot{orientovaných cest z~$s$ do~$t$} -\s{Dùkaz:} Z~grafu sestrojíme sí» tak, ¾e $s$~bude zdroj, $t$~spotøebiè a v¹em +\proof Z~grafu sestrojíme sí» tak, ¾e $s$~bude zdroj, $t$~spotøebiè a v¹em hranám nastavíme kapacitu na~jednotku. Øezy v~této síti odpovídají øezùm v~pùvodním grafu. Podobnì ka¾dý systém hranovì disjunktních $st$-cest odpovídá toku stejné velikosti a naopak ke~ka¾dému celoèíselnému toku dovedeme najít systém disjunktních @@ -216,7 +219,7 @@ Bu Pak je velikost minimálního $st$-separátoru rovna maximálnímu poètu vrcholovì disjunktních $st$-cest.\foot{Tím myslíme cesty disjunktní a¾ na~krajní vrcholy.} -\s{Dùkaz:} Podobnì jako v~dùkazu pøedchozí vìty zkonstruujeme vhodnou sí». +\proof Podobnì jako v~dùkazu pøedchozí vìty zkonstruujeme vhodnou sí». Tentokrát ov¹em rozdìlíme ka¾dý vrchol na~vrcholy $v^+$ a $v^-$, v¹echny hrany, které pùvodnì vedly do~$v$, pøepojíme do~$v^+$, hrany vedoucí z~$v$ povedou z~$v^-$ a pøidáme novou hranu z~$v^+$ do~$v^-$. V¹echny hrany budou mít jednotkové kapacity. diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex index 03d484d..7a248f0 100644 --- a/10-decomp/10-decomp.tex +++ b/10-decomp/10-decomp.tex @@ -186,7 +186,7 @@ nejv \s{Vìta:} (Frederickson) Ka¾dá $c$-clusterizace grafu $G$ má $\O(V(G)/c)$ clusterù. Existuje algoritmus, který jednu takovou najde v~lineárním èase. -\s{Dùkaz:} První èast rozborem pøípadù, druhá hladovì pomocí DFS. \qed +\proof První èast rozborem pøípadù, druhá hladovì pomocí DFS. \qed \s{Pou¾ití:} Pøedchozí variantu Union-Find problemu bychom také mohli vyøe¹it nahrazením vrcholù stupnì $>3$ \uv{kruhovými objezdy bez jedné hrany}\foot{tzv. francouzský trik}, @@ -219,7 +219,7 @@ $a_1,\ldots a_n$ tak, abychom um \s{Lemma:} LCA lze pøevést na~RMQ s~lineárním èasem na~pøedzpracování a konstantním èasem na~pøevod dotazu. -\s{Dùkaz:} Strom projdeme do~hloubky a poka¾dé, kdy¾ nav¹tívíme vrchol (v~inorderu), +\proof Strom projdeme do~hloubky a poka¾dé, kdy¾ nav¹tívíme vrchol (v~inorderu), zapí¹eme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejhlub¹í vrchol mezi poslední náv¹tìvou~$x$ a první náv¹tìvou~$y$, nebo opaènì. \qed @@ -264,7 +264,7 @@ $a_1,\ldots,a_{j-1}$ a prav \s{Lemma:} Kartézský strom je mo¾né zkonstruovat v~lineárním èase. -\s{Dùkaz:} Pou¾ijeme inkrementální algoritmus, v¾dy si budeme pamatovat +\proof Pou¾ijeme inkrementální algoritmus, v¾dy si budeme pamatovat kartézský strom pro ji¾ zpracované prvky a pozici posledního zpracovaného prvku v~tomto stromu. Kdy¾ pøidáváme dal¹í prvek, hledáme místo, kam ho pøipojit, od~tohoto oznaèeného prvku nahoru. Pov¹imneme si, ¾e vzhledem @@ -275,7 +275,7 @@ prvku amortizovan \s{Lemma:} RMQ lze pøevést na~LCA s~lineárním èasem na~pøedzpracování a konstantním èasem na~pøevod dotazu. -\s{Dùkaz:} Sestrojíme kartézský strom a RMQ pøevedeme na~LCA v~tomto stromu. +\proof Sestrojíme kartézský strom a RMQ pøevedeme na~LCA v~tomto stromu. \qed Výsledky této podkapitoly mù¾eme shrnout do~následující vìty: diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index 120d0d3..2372ebd 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -141,7 +141,7 @@ Tento seznam udr nebo první prvek seznamu $\(w)$ má $\ < \(v)$. Navíc seznamy \ lze udr¾ovat v~amortizovanì konstantním èase. -\s{Dùkaz:} První èást plyne z~definice. V¹echny seznamy na~zaèátku bìhu algoritmu +\proof První èást plyne z~definice. V¹echny seznamy na~zaèátku bìhu algoritmu sestrojíme v~lineárním èase pøihrádkovým tøídìním a kdykoliv slouèíme blok s~nadøazeným blokem, odstraníme ho ze~seznamu v~pøíslu¹né artikulaci. \qed @@ -213,7 +213,7 @@ usnadn kreslených zpìtných hran a $l$ poèet vrcholù, které zmizely z~vnìj¹í stìny, èili amortizovaná konstanta. -\s{Dùkaz:} Alespoò polovina vrcholù, po~nich¾ jsme v~libovolném bloku pro¹li, +\proof Alespoò polovina vrcholù, po~nich¾ jsme v~libovolném bloku pro¹li, zmizí z~vnìj¹í stìny, tak¾e hledání koøenù blokù trvá $\O(l)$. Pro ka¾dou zpìtnou hranu oznaèíme jeden vrchol jako ¾ivý a pak pokraèujeme hledáním koøenù. \qed @@ -277,7 +277,7 @@ Cel \s{Vìta:} Tento algoritmus pro ka¾dý graf dobìhne v~èase $\O(n)$ a pokud byl graf rovinný, vydá jeho nakreslení, v~opaèném pøípadì ohlásí nerovinnost. -\s{Dùkaz:} První krok je korektní, jeliko¾ pro v¹echny rovinné grafy je $m\le 3n-6$; nadále +\proof První krok je korektní, jeliko¾ pro v¹echny rovinné grafy je $m\le 3n-6$; nadále tedy mù¾eme pøedpokládat, ¾e $m=\O(n)$. Lineární èasovou slo¾itost krokù 4--6 a~9 jsme ji¾ diskutovali, kroky~7--8 jsou lineární ve~velikosti ¾ivého podgrafu, a tedy také $\O(n)$. Nakreslení vydané algoritmem je v¾dy rovinné a v¹echny stromové hrany jsou v¾dy @@ -290,7 +290,7 @@ graf nebyl rovinn \s{Lemma:} Pokud existuje zpìtná hrana, kterou algoritmus nenakreslil, graf na~vstupu není rovinný. -\s{Dùkaz:} Pro spor pøedpokládejme, ¾e pøi zpracování vrcholu~$v$ existuje +\proof Pro spor pøedpokládejme, ¾e pøi zpracování vrcholu~$v$ existuje zpìtná hrana~$wv$, kterou algoritmus nenakreslil, èili ¾e pøístup z~$v$ k~$w$ je v~obou smìrech blokován externì aktivními vrcholy. Rozborem pøípadù uká¾eme, ¾e tato situace vede ke~sporu buïto s~pravidly \#1 a \#2 nebo s~rovinností grafu. @@ -338,17 +338,17 @@ hrana~$vw$, musela na~druh \:{\I zùstane 2-souvislý} a vznikne z~nìj nìjaký blok~$B'$ -- tehdy rozebereme, jaké hrany vedou mezi $v$ a $B'$: -\itemize\nparen +\numlist\nparen \:{\I více ne¾ dvì hrany} -- minor~$N_2$. \:{\I alespoò jedna hrana na \uv{horní} cestu} (to jest na~tu, na~ni¾ nele¾í~$w$) -- minor~$N_3$. \:{\I dvì hrany do~$x,y$ nebo na \uv{dolní} cestu} -- a» u¾ jsme vstoupili na~hranici bloku~$B'$ kteroukoliv hranou, pravidlo~\#2 nám øeklo, ¾e máme pokraèovat vrchem, co¾ je mo¾né jedinì tehdy, je-li na~spodní cestì je¹tì jeden externì aktivní vrchol, a~to dává minor~$N_4$. -\endlist +\qeditem \endlist -\qed +\endlist \s{Poznámka:} Podle tohoto dùkazu bychom také mohli v~lineárním èase v~ka¾dém nerovinném grafu nalézt Kuratowského podgraf, dokonce také v~$O(n)$, jeliko¾ kdy¾ je $m>3n-6$, diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index 7d39fc7..d818983 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -2,12 +2,15 @@ \prednaska{2}{Dinicùv algoritmus a jeho varianty}{} +V~této kapitole pojednáme o~Dinicovì algoritmu na~výpoèet maximálního +toku a o~rùzných jeho variantách pro sítì ve~speciálním tvaru. + \h{Dinicùv algoritmus} Dinicùv algoritmus je zalo¾en na my¹lence, ¾e ve Ford-Fulkersonovì algoritmu není potøeba pøièítat jen zlep¹ující cesty, ale je mo¾né pøièítat rovnou zlep¹ující toky, nejlépe takové, aby je nebylo obtí¾né najít, a~pøitom aby pùvodní tok - dostateènì zlep¹ovaly. Vhodnými objekty k~tomuto úèelu jsou: +dostateènì zlep¹ovaly. Vhodnými objekty k~tomuto úèelu jsou: \s{Definice:} {\I Blokující tok} je tok takový, ¾e ka¾dá orientovaná $st$-cesta obsahuje alespoò jednu nasycenou hranu. [Tj. takový tok, který by na¹el F-F algoritmus, @@ -100,7 +103,7 @@ T \h{Implementaèní poznámky} \itemize\ibull -\:Není potøeba tak brutální èi¹tìní. Vrcholy se vstupním stupnìm 0 nám +\:Není potøeba tak puntíèkáøské èi¹tìní. Vrcholy se vstupním stupnìm 0 nám nevadí -- stejnì se do nich nedostaneme. Vadí jen vrcholy s výstupním stupnìm 0, kde by mohl havarovat postup v podkroku 9. \:Je mo¾né dìlat prohledávání a èi¹tìní souèasnì. Jednodu¹e metodou Hrrr na nì a kdy¾ @@ -143,7 +146,7 @@ nejv Proto bychom chtìli omezit velikost toku $f_R$. Napøíklad øezem. Najdeme v síti rezerv øez $C$. Kde ho vzít?\foot{Pøeci v øeznictví. Kdepak, spí¹e v cukrárnì. -Myslíte, ¾e v cukrárnì mají Dinicovy øezy? Myslím, ¾e v cukrárnì je vìt¹ina øezù minimální.} +Myslíte, ¾e v cukrárnì mají Dinicovy øezy? Myslím, ¾e v cukrárnì je vìt¹ina øezù minimální. {\sl (odposlechnuto na~pøedná¹ce)}} Poèítejme jen hrany zleva doprava. Tìch je jistì nejvý¹e $m$ a tvoøí alespoò $k$ rozhraní mezi vrstvami. Tedy existuje rozhraní vrstev s~nejvý¹e $m/k$ hranami\foot{Princip holubníku a nìjaká ta $\pm1$.}. @@ -240,7 +243,7 @@ ov a výsledného bude malý, toti¾: $$ \vert f_i\vert - \vert 2f_{i-1}\vert \leq m.$$ -\s{Dùkaz:} +\proof Vezmeme minimální øez $R$ v $G_{i-1}$. Platí $\vert f_{i-1}\vert = \vert R\vert$\foot{F-F vìta.}. Øez $R$ obsahuje $\leq m$ hran. V $G_{i}$ má øez $R$ kapacitu maximálnì $2\vert R\vert+m$. Maximální tok je omezen ka¾dým øezem. Tedy i øezem $R$. Proto tok vzroste o $\leq m$. @@ -249,7 +252,7 @@ Maxim Proto podle pøedchozího odhadu výpoèet toku $f_i$ trvá $\O(mn)$. Takový tok se bude poèítat $k$-krát, tak¾e celková slo¾itost vyjde $\O(mn\log C)$. -\h{Dinicova tabulka} +\h{Pøehled variant Dinicova algoritmu} $$\vbox{\halign{# \hfil \quad &# \hfil \cr \it verze &\it èas \cr\noalign{\smallskip\hrule\smallskip} @@ -257,7 +260,7 @@ standardn jednotkové kapacity &$\O(nm)$ \cr jednotkové kapacity podruhé &$\O(\sqrt{m}\cdot m) = \O(m^{3/2})$ \cr jednotkové kapacity, 1 stupeò $\leq 1$ &$\O(\sqrt{n}\cdot m)$ \cr -jednotkové kapacity veseleji &$\O(n^{2/3}m)$ \cr +jednotkové kapacity potøetí &$\O(n^{2/3}m)$ \cr celoèíselné kapacity &$\O(\vert f\vert\cdot n + nm)$ \cr celoèíselné kapacity $ \leq C$ &$\O(Cn^2 + mn)$ \cr celoèíselné kapacity $ \leq C$ &$\O(mn\log C)$ \cr diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index 49c87f1..12bdd67 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -2,8 +2,8 @@ \prednaska{3}{Bipartitní párování a globální k-souvislost}{} -\>V~minulé kapitole jsme se zabývali aplikacemi tokù na~hledání maximálního párování -a minimálního øezu. V~této si pøedvedeme dva algoritmy pro podobné problémy, +V~minulé kapitole jsme se zabývali aplikacemi tokù na~hledání maximálního párování +a minimálního $st$-øezu. V~této si pøedvedeme dva algoritmy pro podobné problémy, které se obejdou bez tokù. \h{Maximální párování v regulárním bipartitním grafu \cite{alon:matching}} @@ -56,10 +56,10 @@ Slo Problém zji¹tìní {\I stupnì hranové souvislosti} grafu lze pøevést na problém hledání minimálního øezu, který ji¾ pro zadanou dvojici vrcholù umíme øe¹it pomocí Dinicova algoritmu v~èase $\O(n^{2/3}m)$. Pokud chceme najít minimum pøes v¹echny dvojice, mù¾eme vyzkou¹et v¹echny dvojice $(s,t)$. -To v¹ak lze snadno zrychlit, pokud si uvìdomíme, ¾e jeden z vrcholù (tøeba $s$) lze zvolit +To v¹ak lze snadno zrychlit, pokud si uvìdomíme, ¾e jeden z~vrcholù (tøeba $s$) lze zvolit pevnì: pokud vezmeme libovolný øez $C$, pak jistì najdeme alespoò jedno~$t$, které padne do~jiné komponenty ne¾ pevnì zvolené~$s$, tak¾e minimální $st$-øez bude nejvý¹e tak velký jako~$C$. -Pokud pracujeme s orientovanými grafy, musíme projít jak øezy pro $s \rightarrow t$, tak i $t \rightarrow s$. +Pokud pracujeme s~orientovanými grafy, musíme projít jak øezy pro $s \rightarrow t$, tak i $t \rightarrow s$. Algoritmus bude mít slo¾itost $\O(n^{{5/3}}m)$. U~{\I vrcholové $k$-souvislosti} to ov¹em tak snadno nepùjde. Pokud by toti¾ fixovaný vrchol byl souèástí nìjakého @@ -90,7 +90,7 @@ $d(\{v_1 \ldots v_{i-1}\},v_i) \geq d(\{v_1 \ldots v_{i-1}\},v_j)$ pro $1 \leq i \s{Lemma:} Je-li $v_1 \ldots v_n$ LU na $G$, pak $r(v_{n-1},v_n)=d(v_n)$. -\s{Dùkaz:} Buï $C$ nìjaký øez oddìlující $v_{n-1}$ a $v_n$. Utvoøme posloupnost vrcholù $u_i$ takto: +\proof Buï $C$ nìjaký øez oddìlující $v_{n-1}$ a $v_n$. Utvoøme posloupnost vrcholù $u_i$ takto: \algo \:$u_0 := v_1$ diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex index 1366c6d..53d870e 100644 --- a/4-ght/4-ght.tex +++ b/4-ght/4-ght.tex @@ -6,22 +6,20 @@ \def\rr{$r_1r_2$} \def\GHT{GHT} \def\PGHT{ÈGHT} -\def\th#1{\s{#1}} -\def\proof{\noindent{\it Dùkaz:} } \input ../sgr.tex \prednaska{4}{Gomory-Hu Trees}{} -Cílem této kapitoly je vytvoøit datovou strukturu, která po urèitém -pøedzpracování doká¾e rychle konstruovat pro libovolnou dvojici vrcholù v~grafu -minimální øez, který ji oddìluje. +Cílem této kapitoly je popsat datovou strukturu, která velice kompaktnì +popisuje minimální $st$-øezy pro v¹echny dvojice vrcholù $s,t$ v~daném +neorientovaném grafu. Tuto strukturu poprvé popsali Gomory a Hu v~èlánku \cite{gomoryhu}. Zatím umíme nalézt minimální \st-øez pro zadanou dvojici vrcholù v~neorientovaném grafu v~èase $\tau=\O(n^{2/3}m)$ pro~jednotkové kapacity, $\O(n^2m)$ pro obecné. Nalézt minimální \st-øez pro ka¾dou dvojici vrcholù bychom tedy dokázali v~èase $\O(n^2\tau)$. Tento výsledek budeme -chtít zlep¹it. \cite{gomoryhu} +chtít zlep¹it. \s{Znaèení:} Máme\li{} graf $(V,E)$ a $U\subseteq V$, $\d(U)$ znaèí hrany vedoucí mezi $U$ a $\overline U$, formálnì tedy $\d(U)=E \cap ((U \times \overline U) \cup (\overline U \times U))$. @@ -36,20 +34,20 @@ pro n \s{Definice:} {\I Gomory-Hu Tree} (dále jen \GHT) pro neorientovaný ohodnocený graf $G=(V,E)$ je strom $T=(V,F)$ takový,\nobreak{}\ \nobreak{}¾e $$\forall st \in F: \d(K_1)=\d(K_2)\hbox{ je minimální \st-øez, kde $K_1$ a $K_2$ jsou komponenty $T\setminus st$}.$$ -Pozor, $F$ nemusí být podmno¾ina pùvodních hran $E$. +[Pozor, $F$ nemusí být podmno¾ina pùvodních hran $E$.] \s{Dal¹í znaèení:} Pro $e\in F$ budeme øezem $\d(e)$ oznaèovat øez $\d(K_1)=\d(K_2)$ a $r(e)$ bude jeho kapacita. \>K~èemu takový \GHT{} je (existuje-li)? To nám poví následující -\th{Vìta (o~vyu¾ití \GHT):} Buï $T=(V,F)$ \GHT{} pro graf $G=(V,E)$ a mìjme dva vrcholy $s$ a $t$. Dále +\s{Vìta (o~vyu¾ití \GHT):} Buï $T=(V,F)$ \GHT{} pro graf $G=(V,E)$ a mìjme dva vrcholy $s$ a $t$. Dále nech» $P$ je cesta v~$T$ mezi vrcholy $s$ a $t$ a $e$ je hrana na cestì $P$ s~minimálním $r(e)$. Pak $\d(e)$ je minimální \st-øez. \proof Nejprve si doká¾eme jedno drobné -{\advance\leftskip by 2em -\th{Lemmátko:} Pro ka¾dou trojici vrcholù $x,y,z$ platí, ¾e $r(x,z) \ge \min(r(x,y),r(y,z))$. +{\advance\leftskip by 2em\advance\rightskip by 2em +\s{Lemmátko:} Pro ka¾dou trojici vrcholù $x,y,z$ platí, ¾e $r(x,z) \ge \min(r(x,y),r(y,z))$. \proof Buï $W$ minimální $xz$-øez. @@ -69,8 +67,9 @@ Na Urèitì je pravda, ¾e $r(s,x) \ge r(e)$, proto¾e $e$ byla hrana cesty $P$ s~nejmen¹ím $r(e)$. To, ¾e $r(x,t) \ge r(e)$, plyne z~indukèního pøedpokladu, proto¾e cesta mezi $x$ a $t$ je krat¹í ne¾ cesta $P$. Dostáváme tak, ¾e $r(s,t) \ge \min(r(s,x),r(x,t)) \ge r(e)$. +\qeditem \endlist -\qed + Pokud doká¾eme \GHT{} sestrojit, nalézt minimální \st-øez pro libovolnou dvojici vrcholù doká¾eme stejnì rychle jako nalézt hranu s~nejmen¹í kapacitou na cestì mezi $s$ a $t$ v~\GHT. K~tomu mù¾eme pou¾ít napøíklad Sleator-Tarjanovy stromy, které tuto operaci @@ -87,7 +86,7 @@ Nejprve v \vbox to 0pt{\vskip-\baselineskip\rightline{\epsfysize=2cm\epsfbox{4-ght-htl.eps}}\vss}\vskip-\baselineskip { \advance\rightskip by 17em -\th{Hnusnì technické lemma (HTL):} Buïte¾ $s,t$ vrcholy grafu $(V,E)$, $\d(U)$ minimální \st-øez a $u\ne v$ dva rùzné +\s{Hnusnì technické lemma (HTL):} Buïte¾ $s,t$ vrcholy grafu $(V,E)$, $\d(U)$ minimální \st-øez a $u\ne v$ dva rùzné vrcholy z~$U$. Pak existuje mno¾ina vrcholù $W \subseteq U$ taková, ¾e $\d(W)$ je minimální $uv$-øez. [To dùle¾ité a netriviální je, ¾e celá $W$ le¾í v~$U$.] @@ -149,8 +148,8 @@ U \setminus X&&&\hbox{---}&L_1,P_1\cr Stejnì jako v~pøedchozím pøípadì nerovnost $(4)$ platí. Odeètením $(4)$ a $(3)$ získáme $$c(U \setminus X) \le c(X),$$ z~èeho¾ opìt dostaneme, ¾e $\d(U \setminus X)$ je také minimální $uv$-øez. +\qeditem \endlist -\qed \bigskip \>Nyní se koneènì dostáváme ke konstrukci \GHT{}. Abychom mohli pou¾ívat @@ -166,7 +165,7 @@ Nav \endlist -\th{Vìta (o~existenci \PGHT{}):} Buï $(V,E)$ neorientovaný ohodnocený graf. Pro ka¾dou podmno¾inu vrcholù $R$ +\s{Vìta (o~existenci \PGHT{}):} Buï $(V,E)$ neorientovaný ohodnocený graf. Pro ka¾dou podmno¾inu vrcholù $R$ existuje \PGHT{}. \proof Doká¾eme indukcí podle velikosti mno¾iny $R$.\itemize\ibull @@ -205,15 +204,15 @@ k~nim HTL nám navíc øíká, ¾e existuje minimální øez, který ¾ije pouze v~pøíslu¹ném z~grafù $G_1$, $G_2$, tak¾e nalezený øez je minimální pro celý graf $G$. +\qeditem \endlist \endlist -\qed Nyní víme, ¾e \GHT{} existují, a také víme, jak by se daly konstruovat. Nicménì nalezení vrcholù $s,t$ tak, aby byl minimální \st-øez nejmen¹í mo¾ný, je èasovì nároèné. Proto si poslední vìtu je¹tì o~nìco vylep¹íme. -\th{Vylep¹ení vìty o~existenci \PGHT{}:} Na zaèátku dùkazu není nutné hledat vrcholy $s$ a $t$ +\s{Vylep¹ení vìty o~existenci \PGHT{}:} Na zaèátku dùkazu není nutné hledat vrcholy $s$ a $t$ takové, aby byl minimální \st-øez nejmen¹í mo¾ný. Staèí zvolit \ vrcholy $s,t\in R$ a nalézt minimální \st-øez $\d(W)$. diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index 2e0361f..44a8e33 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -3,12 +3,14 @@ \def\symdiff{\mathop{\Delta}} -\h{Minimální kostry a základní vìty okolo nich} +\>Tato kapitola uvede problém minimální kostry, základní vìty o~kostrách a klasické +algoritmy na~hledání minimálních koster. Budeme se inspirovat Tarjanovým pøístupem +z~knihy~\cite{tarjan:dsna}. V¹echny grafy v~této kapitole budou neorientované multigrafy +a jejich hrany budou ohodnoceny vahami $w: E \to {\bb R}$. \todo{Chybí zde obrázky, znaènì by hutný text projasnily.} -\>V~této kapitole se budeme zabývat výhradnì neorientovanými grafy, jejich¾ hrany -budou ohodnoceny vahami $w: E \to {\bb R}$. +\h{Minimální kostry a jejich vlastnosti} \s{Definice:} \itemize\ibull @@ -24,7 +26,6 @@ jako komponenty~$G$.] ka¾dé kostøe, její¾ váha je mezi v¹emi kostrami daného grafu minimální. \endlist -\s{Poznámka:} Toto je sice standardní definice MST, ale jinak je dosti ne¹ikovná, proto¾e vy¾aduje, aby bylo váhy mo¾né sèítat. Za~chvíli si uká¾eme, ¾e to není potøeba. @@ -37,7 +38,7 @@ Bu Ostatním hranám nele¾ícím v~kostøe budeme øíkat {\I tì¾ké.} \endlist -\s{Vìta:} (Tarjan \cite{tarjan:dsna}) Kostra~$T$ je minimální $\Leftrightarrow$ neexistuje hrana lehká vzhledem k~$T$. +\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 pouze porovnává, èili jí místo èísel staèí (kvazi)uspoøádání na~hranách. Ne¾ se dostaneme @@ -56,7 +57,7 @@ a vynech \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í \. -\s{Dùkaz:} +\proof Jeliko¾ $\vert T \vert = \vert T' \vert$, musí existovat $e' \in T'\setminus T$. Kru¾nice $T[e']+e'$ nemù¾e být celá obsa¾ena v~$T$, tak¾e existuje hrana $e\in T[e']\setminus T'$ a $\check{T} := \(T,e,e')$ je kostra, @@ -68,7 +69,7 @@ Po~kone Je-li $T$ kostra, k~ní¾ neexistují ¾ádné lehké hrany, a~$T'$ libovolná kostra, pak lze od~$T$ k~$T'$ pøejít posloupností swapù, pøi které váha kostry neklesá. -\s{Dùkaz:} +\proof Podobnì jako u~pøedchozího lemmatu budeme postupovat indukcí podle $\vert T \symdiff T' \vert$. Pokud zvolíme libovolnì hranu $e'\in T'\setminus T$ a k~ní $e\in T[e']\setminus T'$, musí $\check{T}:=\(T,e,e')$ být kostra bli¾¹í k~$T'$ a $w(\check{T})\ge w(T)$, @@ -96,14 +97,13 @@ Kostra $T' := \(T,e,e')$ je leh Uva¾me nìjakou minimální kostru $T_{min}$ a pou¾ijme monotónní swapovací lemma na~$T$ a $T_{min}$. Z~nìj plyne $w(T)\le w(T_{min})$, a~tedy $w(T)=w(T_{min})$. - +\qeditem \endlist -\qed \s{Vìta:} Jsou-li v¹echny váhy hran navzájem rùzné, je MST urèena jednoznaènì. -\s{Dùkaz:} +\proof Máme-li dvì MST $T_1$ a $T_2$, neobsahují podle pøedchozí vìty lehké hrany, tak¾e podle monotónního lemmatu mezi nimi lze pøeswapovat bez poklesu váhy. Pokud jsou ale váhy rùzné, musí ka¾dé swapnutí ostøe zvý¹it váhu, a~proto k~¾ádnému nemohlo dojít. @@ -119,17 +119,15 @@ V meta-algoritmu. Rozeberme si tedy rovnou ten. Formulujeme ho pro pøípad, kdy jsou v¹echny váhy hran navzájem rùzné. -\s{Meta-algoritmus:} (Tarjan \cite{tarjan:dsna}) +\s{Meta-algoritmus:} \algo \:Na poèátku jsou v¹echny hrany bezbarvé. \:Dokud to lze, pou¾ijeme jedno z~následujících pravidel: -\itemize\relax -\:{\I Modré pravidlo:} Vyber øez takový, ¾e jeho nejlehèí hrana není modrá,\foot{Za +\::{\I Modré pravidlo:} Vyber øez takový, ¾e jeho nejlehèí hrana není modrá,\foot{Za touto podmínkou nehledejte ¾ádná kouzla, je tu pouze proto, aby se algoritmus nemohl zacyklit neustálým provádìním pravidel, která nic nezmìní.} a obarvi ji na~modro. -\:{\I Èervené pravidlo:} Vyber cyklus takový, ¾e jeho nejtì¾¹í hrana není èervená, a obarvi ji na~èerveno. -\endlist +\::{\I Èervené pravidlo:} Vyber cyklus takový, ¾e jeho nejtì¾¹í hrana není èervená, a obarvi ji na~èerveno. \endalgo \s{Vìta:} @@ -143,7 +141,7 @@ podle vah plat \s{Modré lemma:} Je-li hrana~$e$ kdykoliv algoritmem obarvena na~modro, pak $e\in T_{min}$. -\s{Dùkaz:} Minimální kostra $T_{min}$ je urèena jednoznaènì (váhy jsou rùzné). +\proof Minimální kostra $T_{min}$ je urèena jednoznaènì (váhy jsou rùzné). Hrana~$e$ byla omodøena jako nejlehèí hrana nìjakého øezu~$C$. Pokud by existovala nìjaká jiná $e' \in C \cap T_{min}[e]$, mù¾eme provést $\(T_{min},e',e)$ a tím z~$T_{min}$ vytvoøit je¹tì lehèí kostru, @@ -154,7 +152,7 @@ co \s{Èervené lemma:} Je-li hrana~$e$ kdykoliv algoritmem obarvena na~èerveno, pak $e\not\in T_{min}$. -\s{Dùkaz:} Opìt sporem: Pøedpokládejme, ¾e~$e$ byla obarvena èervenì jako nejtì¾¹í na~nìjaké kru¾nici~$C$ +\proof Opìt sporem: Pøedpokládejme, ¾e~$e$ byla obarvena èervenì jako nejtì¾¹í na~nìjaké kru¾nici~$C$ a ¾e $e\in T_{min}$. Odebráním~$e$ se nam $T_min$ rozpadne na dvì komponenty $T_x$ a $T_y$. Nìkteré vrcholy kru¾nice pøipadnou do komponenty $T_x$, ostatní do $T_y$. Lze jednodu¹e nahlédnout, ¾e musí existovat hrana $e'\ne e$ taková, ¾e $x' \in T_x$ a $y' \in T_y$. @@ -167,7 +165,7 @@ co \s{Bezbarvé lemma:} Pokud existuje nìjaká neobarvená hrana, lze je¹tì pou¾ít nìkteré z~pravidel. -\s{Dùkaz:} Nech» existuje hrana~$e=xy$, která je stále bezbarvá. Oznaèíme si $M$ mno¾inu vrcholù, +\proof Nech» existuje hrana~$e=xy$, která je stále bezbarvá. Oznaèíme si $M$ mno¾inu vrcholù, do~nich¾ se lze z~$x$ dostat po~modrých hranách. Nyní mohou nastat dvì mo¾nosti: \itemize\ibull @@ -182,8 +180,8 @@ a mohu na ni pou \fig{05.eps}{3cm} +\qeditem \endlist -\qed \s{Dùkaz vìty:} \itemize\ibull @@ -191,8 +189,8 @@ a mohu na ni pou alespoò jedna obarvená hrana, tak¾e se algoritmus zastaví. \:{\I Obarví v¹e:} Pokud existuje alespoò jedna neobarvená hrana, pak podle bezbarvého lemmatu algoritmus pokraèuje. \:{\I Najde modrou MST:} Podle èerveného a modrého lemmatu le¾í v~$T_{min}$ právì modré hrany. +\qeditem \endlist -\qed \s{Poznámka:} Èervené a modré pravidlo jsou v~jistém smyslu duální. Pro rovinné grafy je na~sebe pøevede obyèejná rovinná diff --git a/6-borjar/6-borjar.tex b/6-borjar/6-borjar.tex index 3bd89a3..f9d16f5 100644 --- a/6-borjar/6-borjar.tex +++ b/6-borjar/6-borjar.tex @@ -2,6 +2,9 @@ \prednaska{6}{Rychlej¹í algoritmy na~minimální kostry}{} +V~této kapitole popí¹eme nìkolik pokroèilej¹ích algoritmù pro problém minimální +kostry. Vesmìs to budou rùzná vylep¹ení klasických algoritmù z~minulé kapitoly. + \h{Upravená verze Borùvkova algoritmu pro rovinné grafy} Vyjdeme z my¹lenky, ¾e mù¾eme po ka¾dém kroku pùvodního Borùvkova algoritmu vzniklé komponenty diff --git a/7-ram/7-ram.tex b/7-ram/7-ram.tex index 5ae3708..0dd0211 100644 --- a/7-ram/7-ram.tex +++ b/7-ram/7-ram.tex @@ -94,7 +94,7 @@ d \endlist -V~zbytku této kapitoly uká¾eme, ¾e na~RAMu lze poèítat mnohé vìci +Ve~zbytku této kapitoly uká¾eme, ¾e na~RAMu lze poèítat mnohé vìci efektivnìji ne¾ na~PM. Zamìøíme se pøevá¾nì na~Word-RAM, podobné konstrukce jdou provést i na~$AC^0$-RAMu. (Kombinace obou omezení vede ke~slab¹ímu modelu.) @@ -185,7 +185,7 @@ odpustit. \h{Modely inicializace} -\>Jak mù¾e definován obsah pamìti na~poèátku výpoètu: +\>Jak mù¾e být definován obsah pamìti na~poèátku výpoètu: \s{\uv{Pøi odchodu zhasni}:} Zavedeme, ¾e pamì» RAMu je na~poèátku inicializována nulami a program ji po~sobì musí uklidit (to je nutné, @@ -201,7 +201,7 @@ n pamìtí bì¾ící v èase $T(n)$. Pak existuje program~$P'$ pro Word-RAM s~neinicializovanou pamìtí poèítající toté¾ v~èase~$\O(T(n))$. -\s{Dùkaz:} Bìhem výpoètu si budeme pamatovat, ve~kterých pamì»ových +\proof Bìhem výpoètu si budeme pamatovat, ve~kterých pamì»ových buòkách u¾ nìco máme. Prokládanì ulo¾íme do pamìti dvì pole: $M$, co¾ bude pamì» pùvodního stroje, a~$L$ -- seznam èísel bunìk v~$M$, do~kterých u¾ program zapsal. Pøitom $L[0]$ bude udávat diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex index 8d62eb0..a0ee4d1 100644 --- a/8-qheap/8-qheap.tex +++ b/8-qheap/8-qheap.tex @@ -103,7 +103,7 @@ sou \:pozicí $b=\msb(x \oplus x_i)$. \endlist -\s{Dùkaz:} Pokud $x=x_i$, je zjevnì $\rank_X(x) = i$. Pøedpokládejme tedy $x\ne x_i$. +\proof Pokud $x=x_i$, je zjevnì $\rank_X(x) = i$. Pøedpokládejme tedy $x\ne x_i$. Hodnoty znaèek klesají ve~smìru od koøene k~listùm a na cestì od koøene k~$x_i$ se v¹echny bity v $x_i$ na~pozicích urèených znaèkami shodují s bity v $x$, pøièem¾ a¾ do~pozice $b$ se shodují i bity znaèkami netestované. Sledujme tuto cestu @@ -144,7 +144,7 @@ ekvivalentn \:$x[B]$ -- hodnot bitù na~\uv{zajímavých} pozicích v~èísle~$x$. \endlist -\s{Dùkaz:} Z~pøedchozího lemmatu: +\proof Z~pøedchozího lemmatu: \numlist\pnromanp \:Tvar stromu závisí jen na~nerovnostech mezi polohami znaèek, tak¾e je jednoznaènì urèený funkcí~$C$. diff --git a/9-suffix/9-suffix.tex b/9-suffix/9-suffix.tex index 5f29710..0ea06a6 100644 --- a/9-suffix/9-suffix.tex +++ b/9-suffix/9-suffix.tex @@ -2,7 +2,7 @@ \prednaska{9}{Suffixové stromy}{} -V~této kapitole popí¹eme jednu datovou strukturu, pomocí které doká¾eme problémy týkající +V~této kapitole popí¹eme jednu datovou strukturu, pomocí ní¾ doká¾eme problémy týkající se øetìzcù pøevádìt na grafové problémy a tak je øe¹it v~lineárním èase. \h{Øetìzce, trie a suffixové stromy} @@ -66,14 +66,14 @@ a \s{Lemma:} Suffixový strom pro slovo $\sigma$ délky $n$ je reprezentovatelný v~prostoru $\O(n)$. -\s{Dùkaz:} Strom má $\O(n)$ listù a ka¾dý vnitøní vrchol má alespoò $2$ syny, tak¾e vnitøních +\proof Strom má $\O(n)$ listù a ka¾dý vnitøní vrchol má alespoò $2$ syny, tak¾e vnitøních vrcholù je také $\O(n)$. Hran je rovnì¾ lineárnì. Nálepky na~hranách si staèí reprezentovat poèáteèní a koncovou pozicí v~$\sigma$. \qed \s{Vìta:} Suffixový strom pro slovo $\sigma$ délky $n$ lze sestrojit v~èase $\O(n)$. -\s{Dùkaz:} Ve~zbytku této kapitoly pøedvedeme dvì rùzné konstrukce v~lineárním èase. +\proof Ve~zbytku této kapitoly pøedvedeme dvì rùzné konstrukce v~lineárním èase. \qed \s{Aplikace:} (co v¹e doká¾eme v~lineárním èase, kdy¾ umíme lineárnì konstruovat ST) @@ -137,7 +137,7 @@ v~n \s{Vìta:} Suffixový strom s~dolarem pro slovo $\sigma$ je lineárnì ekvivalentní s~dvojicí $(A_\sigma,L_\sigma)$. [Jinými slovy, kdy¾ máme jedno, mù¾eme z~toho v~lineárním èase spoèítat druhé a naopak.] -\s{Dùkaz:} Kdy¾ projdeme ST($\sigma$) do hloubky, poøadí listù odpovídá $A_\sigma$ a písmenkové hloubky vnitøních +\proof Kdy¾ projdeme ST($\sigma$) do hloubky, poøadí listù odpovídá $A_\sigma$ a písmenkové hloubky vnitøních vrcholù v~inorderu odpovídají $L_\sigma$. Naopak ST($\sigma$) získáme tak, ¾e sestrojíme kartézský strom pro~$L_\sigma$ (to jsou vnitøní vrcholy ST), doplníme do~nìj listy a pøiøadíme jim suffixy podle~$A_\sigma$ a nakonec podle listù rekonstruujeme nálepky hran. @@ -231,11 +231,11 @@ vy \s{Lemma:} Suffix $\beta$ slova $\sigma$ je vnoøený $\Leftrightarrow$ $\vert\beta\vert \le \vert\alpha(\sigma)\vert.$ -\s{Dùkaz:} Ka¾dý suffix vnoøeného suffixu je opìt vnoøený. \qed +\proof Ka¾dý suffix vnoøeného suffixu je opìt vnoøený. \qed \s{Lemma:} Pro ka¾dé $\sigma$, $a$ platí: $\alpha(\sigma a)$ je suffixem $\alpha(\sigma)a.$ -\s{Dùkaz:} $\alpha(\sigma a)$ i $\alpha(\sigma)a$ jsou suffixy slova $\sigma a$, a~proto staèí porovnat jejich délky. +\proof $\alpha(\sigma a)$ i $\alpha(\sigma)a$ jsou suffixy slova $\sigma a$, a~proto staèí porovnat jejich délky. Slovo $\beta := \hbox{\uv{$\alpha(\sigma a)$ bez koncového~$a$}}$ je vnoøeným suffixem v~$\sigma$, tak¾e $\vert\beta\vert \le \vert\alpha(\sigma)\vert$, a~tedy také $\vert\alpha(\sigma a)\vert = \vert\beta a\vert \le \vert\alpha(\sigma)a\vert$. \qed @@ -245,7 +245,7 @@ $\vert\beta\vert \le \vert\alpha(\sigma)\vert$, a~tedy tak \s{Lemma:} Suffix $\beta$ je zralý $\Leftrightarrow$ $\vert\alpha(\sigma)a\vert \ge \vert\beta a\vert > \vert\alpha(\sigma a)\vert$. -\s{Dùkaz:} Jeliko¾ $\beta$ je vnoøeným suffixem $\sigma$, musí platit první nerovnost. Aby byl zralý, +\proof Jeliko¾ $\beta$ je vnoøeným suffixem $\sigma$, musí platit první nerovnost. Aby byl zralý, musí také nebýt vnoøeným suffixem $\sigma a$, èemu¾ odpovídá druhá nerovnost. \qed diff --git a/sgr.tex b/sgr.tex index bf59d47..4900e31 100644 --- a/sgr.tex +++ b/sgr.tex @@ -27,10 +27,16 @@ % Zvyrazneny zacatek odstavce coby podnadpis (napr. vety apod.) \def\s#1{\noindent {\bo #1}} +% Dùkaz +\def\proof{\noindent {\sl Dùkaz:} } + % Ctverecek na konci dukazu %\def\qed{{\parfillskip=0pt\quad\hfil\hbox{\I QED} \par}} \def\qed{\hfill\allowbreak\hfill\nobreak $\heartsuit$\par} +% pokud je v seznamu: +\def\qeditem{\hfill\rlap{\hskip\rightskip\llap{$\heartsuit$}}\par} + % Poznamky pod carou \newcount\footcnt \footcnt=0 -- 2.39.2