X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=12-kostry%2F12-kostry.tex;h=bf0f016a3c5fa424fdc940089be3b4049ac455b6;hb=a330729c77ea77e13d21ea707704bc8428e5dffd;hp=6b0c726d5740d297fd376030f6858d7714fe7d82;hpb=87b445933d0c6b1cdfaa97f3128bc914e111dfa4;p=ads1.git diff --git a/12-kostry/12-kostry.tex b/12-kostry/12-kostry.tex index 6b0c726..bf0f016 100644 --- a/12-kostry/12-kostry.tex +++ b/12-kostry/12-kostry.tex @@ -1,195 +1,230 @@ \input lecnotes.tex -\prednaska{10}{Problém minimálni kostry}{(zapsali K. Ka¹èák a M. Vachna)} +\prednaska{12}{Problém minimální kostry}{(zapsali K. Ka¹èák a M. Vachna)} -Pro zaèátek si definujme, co budeme dìlat, v jakých grafech budeme minimálni kostru hledat. +\s{Zadání úlohy:} Pro neorientovaný graf $G$ s~ohodnocením hran {\I váhami} $w: E(G) \rightarrow \bb R$, +chceme najít kostru $T$ s minimálním ohodnocením $w(T)=\sum_{e\in E(T)} w(e)$. -\s{Zadání úlohy:} Pro neorientovaný graf $G$ s ohodnocením hran $w: E(G) \rightarrow R$, -chceme najít kostru $T$ s minimálnim ohodnocením $w(T)=\sum_{e\in E(T)} w(e)$. - -\s{Pøedpoklady úlohy:} +\s{Navíc pøedpokládáme:} (bez újmy na~obecnosti) \itemize\ibull -\:BÚNO graf $G$ je souvislý -\:$\forall e,f \in E(G$) : $e\neq f \Rightarrow w(e)\neq w(f)$ +\:Graf $G$ je souvislý (jinak ho nejprve rozlo¾íme na komponenty). +\:$\forall e,f \in E(G$) : $e\neq f \Rightarrow w(e)\neq w(f)$. \endlist -Nyní si uká¾eme tøi algoritmy øe¹íci zadanú úlohu, konkrétne se jedná o Jarníkùv, Borùvkùv a Kruskalùv -algoritmus. +Nyní si uká¾eme tøi algoritmy pro hledání minimální kostry, konkrétnì se jedná +o~Jarníkùv, Borùvkùv a Kruskalùv algoritmus. -\s{Algoritmus:} (Jarníkùv) +\h{Jarníkùv algoritmus} -\def\concat{\mathop{\hbox{.}}} +\s{Algoritmus:} \algo -\:Zvolíme libovolný vrchol $v_0\in V(G)$, $T=(\left\{v_0\right\},\emptyset)$. -\:Dokud $\vert V(T) \vert \neq n$ : -\: vybereme hranu $uv\in E(G) : u\in V(T), v\notin V(T)$, min $w(uv)$ -\: $T\leftarrow T+uv$ +\algin Graf~$G$ s~ohodnocením~$w$. +\:Zvolíme libovolný vrchol $v_0\in V(G)$. +\:$T\leftarrow(\left\{v_0\right\},\emptyset)$ (zatím jednovrcholový strom) +\:Dokud $\vert V(T) \vert \neq n$: +\::Vybereme hranu $uv\in E(G) : u\in V(T), v\notin V(T)$ tak, aby $w(uv)$ byla minimálni. +\::$T\leftarrow T+uv$. +\algout Minimální kostra~$T$. \endalgo -\s{Vìta:} Jarníkùv algorimtus se zastaví po maximálne $n$ iteracích a vydá minimálni kostru grafu $G$. +\s{Vìta:} Jarníkùv algoritmus se zastaví po maximálnì $n$ iteracích a vydá minimální kostru grafu $G$. \proof -Koneènost - pøi ka¾dé iteraci se pøidá jeden vrchol $\Rightarrow$ po maximálne $n$ iteracích se zastaví. -Vydaný graf je strom, proto¾e se stále pøidáva list k ji¾ existujícimu stromu. Vydaný graf má $n$ -vrcholù $\Rightarrow$ vydaný graf je kostra. Ostáva nám u¾ jen dokázat, ¾e kostra je minimálni. To -dokazuje nesledujíci Lemma. -\qed +Pøi ka¾dé iteraci algoritmus pøidá jeden vrchol do~$T$, a~proto se po~maximálnì $n$ iteracích zastaví. +Vydaný graf je strom, proto¾e se stále pøidává list k ji¾ existujícímu stromu, a~jeliko¾ má $n$~vrcholù, +je to kostra. Zbývá nám u¾ jen dokázat, ¾e nalezená kostra je minimální. K~tomu pomu¾e následující lemma: -Proto aby jsme byli schopni sformulovat i dokázat Lemma, je nutná je¹tì vysvìtlit pojem øez v grafu. +{\narrower -\s{Definice:} Øez v grafu $G=(V,E)$ je mno¾ina hran $F\subseteq E$ taková, ¾e $\exists U\subset V$ : -$F=\left\{uv\in E \vert u\in U, v\notin U \right\}$. +\s{Definice:} {\I Øez} v~grafu $G=(V,E)$ je mno¾ina hran $F\subseteq E$ taková, ¾e $\exists U\subset V$ : +$F=\left\{uv\in E:u\in U, v\notin U \right\}$. \s{Lemma:} Pokud $G$ je graf, $w$ jeho prosté ohodnocení, $F$ je øez v grafu $G$ a $f$ je nejlehèí hrana v øezu -$F$, pak pro ka¾dou minimálni kostru $G$ je $f\in E(T)$. +$F$, pak pro ka¾dou minimální kostru $T$ grafu $G$ je $f\in E(T)$. \proof -Buï $T$ kostra a $f\notin E(T)$, pak $\exists$ cesta $P\subseteq T$ spojujíci $u$ a $v$ (vrcholy hrany $f$). -Cesta musí øez alespoò jednou projít. $\exists e\in P \cap F$ taková, ¾e $w(e) > w(f)$. Uva¾me $T'=T-e+f$. -$T'$ je rovne¾ kostra grafu $G$, proto¾e odebraním hrany $e$ se graf rozpadne na dvì komponenty a pøidáním -hrany $f$ se opìt spojí. $w(T')=w(T)-w(e)+w(f) w(f)$. Uva¾me $T'=T-e+f$. +Tento graf je rovnì¾ kostra grafu $G$, proto¾e odebraním hrany $e$ se graf rozpadne na dvì komponenty a pøidáním +hrany $f$ se tyto komponenty opìt spojí. Navíc $w(T')=w(T)-w(e)+w(f)V~dùkazu korektnosti Jarníkova algoritmu toto lemma vyu¾ijeme tak, ¾e si v¹imneme, ¾e hrany mezi +vrcholy stromu~$T$ a zbytkem grafu tvoøí øez a algoritmus nejlehèí hranu tohoto øezu pøidá +do~$T$. Podle lemmatu tedy v¹echny hrany~$T$ musí být souèástí ka¾dé minimální kostry a jeliko¾~$T$ je strom, +musí být minimální kostrou. + +\qed + + +\s{Dùsledky:} Graf $G$ s prostým ohodnocením má pravì jednu minimální kostru. Minimální kostra je +jednoznaènì urèená lineárním uspoøádáním hran. \s{Implementace:} \itemize\ibull -\:Pøímoèaøá - pamatujeme si, které vrcholy a hrany jsou v kostøe $T$ a které ne. Èasová slo¾itost je $\O(nm)$ -\:Pro $v\notin V(T)$ si pamatujeme $D(v)=$min$\left\{uv, u\in T\right\}$. Èasová slo¾itost je $\O(n^2+m)=\O(n^2)$ +\:Pøímoèará: pamatujeme si, které vrcholy a hrany jsou v kostøe $T$ a které ne. Èasová slo¾itost je $\O(nm)$. +\:Chytøej¹í: Pro $v\notin V(T)$ si pamatujeme $D(v)=\min\left\{w(uv):u\in T\right\}$. Pøi ka¾dém +prùchodu hlavním cyklem pak procházíme v¹echna~$D(v)$ (to v¾dy trvá $\O(n)$) a pøi pøidání vrcholu do~$T$ kontrolujeme +okolní~$D(w)$ pro $vw\in E$ a pøípadnì je sni¾ujeme (za~ka¾dou hranu~$\O(1)$). Èasovou slo¾itost tím celkovì +zlep¹íme na~$\O(n^2+m)=\O(n^2)$. +\:Také se dá pou¾ít halda pro uchovávání hran nebo hodnot~$D(v)$. \endlist -\s{Algoritmus:} (Borùvkùv) +\h{Borùvkùv algoritmus} -\def\concat{\mathop{\hbox{.}}} +\s{Algoritmus:} \algo -\:Les $F=(V(G),\emptyset)$. -\:Dokud $F$ má alespoò dvì komponenty : -\: $\forall$ komponentu $T_i$ vybereme nejlehèí incidentní hranu $t_i$. -\: V¹echny hrany $t_i$ pøidáme do $F$. +\algin Graf~$G$ s~ohodnocením~$w$. +\:$F\leftarrow(V(G),\emptyset)$ +\:Dokud $F$ má alespoò dvì komponenty: +\::Pro ka¾dou komponentu $T_i$ grafu $F$ vybereme nejlehèí incidentní hranu $t_i$. +\::V¹echny hrany $t_i$ pøidáme do $F$. +\algout Minimální kostra~$F$. \endalgo -\s{Vìta:} Borùvkùv algorimtus se zastaví po $\left\lceil \log_2 n\right\rceil$ iteracích a vydá minimálni kostru grafu $G$. +\s{Vìta:} Borùvkùv algoritmus se zastaví po $\left\lceil \log_2 n\right\rceil$ iteracích a vydá minimální kostru grafu $G$. \proof -Po $k$ iteracích mají v¹echny stromy minimálne $2^k$ vrcholù, $\forall$ i : $\vert T_i\vert \geq 2^k$. -Indukcí podle $k$: ka¾dá incidentní hrana vede z $T_i$ do $T_j$. Po $k$ iteracích pøidáním incidentní hrany -spojíme 2 stromy s alespoò $2^k$ vrcholama, tím vznikne strom s $2^{k+1}$ vrcholama. -Algoritmus vydá kostru, staèí nahlédnout, zda je minimálni. To se lehce uká¾e u¾itím pøedchozí Lemmy. -V¾dy pøidávame hranu, která je minimálni mezi $T$ a ostatními vrcholy grafu $G$. +V¹imnìme si nejprve, ¾e po~$k$ iteracích mají v¹echny komponenty grafu~$F$ minimálnì $2^k$ vrcholù +(na~poèátku jsou v¹echny komponenty jednovrcholové, v~ka¾dé dal¹í iteraci se komponenty sluèují do~vìt¹ích, +ka¾dá s~alespoò jednou sousední, tak¾e se velikosti komponent minimálnì zdvojnásobí). +Proto nejpozdìji po~$\left\lceil \log_2 n\right\rceil$ iteracích u¾~velikost komponenty dosáhne poètu v¹ech vrcholù a algoritmus +se zastaví. + +Hrany mezi ka¾dou komponentou a~zbytkem grafu tvoøí øez, tak¾e podle pøedchozího lemmatu v¹echny +hrany pøidané do~$F$ musí být souèástí (jednoznaènì urèené) minimální kostry. Graf $F\subseteq G$ +je tedy v¾dy les a a¾ se algoritmus zastaví, bude roven minimální kostøe. \qed -\s{Implemntace:} +\s{Implementace:} \itemize\ibull -\:Inicializace pøímoèaøá. -\:Pomocí DFS rozlo¾íme les na komponenty. $\forall$ vrchol si pamatujeme èíslo komponenty. -\:Pro $\forall$ hranu zjistíme, do které komponenty patøí a pro ka¾dou komponentu -jsi uchováme nejlehèí hranu. - -Rozlo¾ení lesa a zji¹tìní, do jaké komponenty patøí ka¾dá hrana má èasovou slo¾itost $\O(m)$. Výslední èasová slo¾itost je $\O(m\log n)$ +\:Inicializace pøímoèará. +\:Pomocí DFS rozlo¾íme les na komponenty. Pro ka¾dý vrchol si pamatujeme èíslo komponenty. +\:Pro ka¾dou hranu zjistíme, do které komponenty patøí, a pro ka¾dou komponentu +si uchováme nejlehèí hranu. \endlist -\s{Algoritmus:} (Kruskalùv èili `hladový`) +\>Takto doká¾eme ka¾dou iteraci provést v~èase $\O(m)$ a celý algoritmus dobìhne v~$\O(m\log n)$. + +\h{Kruskalùv neboli hladový algoritmus} -\def\concat{\mathop{\hbox{.}}} +\s{Algoritmus:} \algo -\:Zetøídime v¹echny hrany z $E$ : $w(e_1)<...), a~$(n-1)$-krát spojíme + dvì komponenty do jedné (\). \endlist +\>Kruskalùv algoritmus tedy pobì¾í v~èase $\O(m\log n + mT_f + nT_u)$, kde~$T_u$ je +èas na~provedení jedné operace \ a $T_f$ na~operaci \. + +\s{Jednoduchá struktura pro komponenty:} +Budeme pamatovat v~poli èísla komponent, ve~kterých le¾í jednotlivé vrcholy. \ zvládneme v~èase $\O(1)$, +ale \ bude stát $\O(n)$. Celý algoritmus pak pobì¾í v~èase $\O(m\log n+ m + n^2) = \O(m\log n+n^2)$. + +\s{Chytøej¹í struktura:} Ka¾dou komponentou si ulo¾íme jako strom orientovaný smìrem ke koøeni +-- ka¾dý vrchol si pamatuje svého otce, navíc ka¾dý koøen si pamatuje velikost komponenty. +Operace \ vystoupá z~obou vrcholù ke~koøeni a koøeny porovná. \ rovnì¾ najde +koøeny a pøipojí koøen men¹í komponenty pod koøen té vìt¹í. Obojí zvládneme v~èase lineárním +v~hloubce stromu a jak si uká¾eme, tato hloubka je v¾dy nejvý¹e logaritmická, a proto celý Kruskalùv +algoritmus pobì¾í v~èase $\O(m\log n + m\log n + n\log n) = \O(m\log n)$.\foot{% +Drobnou úpravou bychom mohli dosáhnout daleko efektivnìj¹í struktury, ale tu bychom neupotøebili, +jeliko¾ by nás stejnì brzdilo tøídìní, a analýza slo¾itosti by byla \dots\ inu, slo¾itìj¹í.} + \s{Lemma:} Strom hloubky $h$ má alespoò $2^h$ prvkù. \proof -Pokud Union spojí stromy jeden s hloubkou $h$ a druhý s hloubkou men¹í ne¾ $h$, pak hloubka výsledního -stromu zústava $h$. Pokud spojuje dva stromy hloubky $h$, pak vyslední strom má hloubku $h+1$. Jak ji¾ -víme, strom hloubky $h$ má minimálne $2^h$, proto výslednej strom hloubky $h+1$ má $2^{h+1}$ vrcholù. -\qed +Indukcí: Pokud \ spojí strom s~hloubkou $h$ s jiným s~hloubkou men¹í ne¾ $h$, pak hloubka výsledného +stromu zùstává~$h$. Pokud spojuje dva stromy stejné hloubky~$h$, pak má výsledný strom hloubku $h+1$. +Z~indukèního pøedpokladu víme, ¾e strom hloubky $h$ má minimálnì $2^h$ vrcholù, +a~tedy výsledný strom hloubky $h+1$ má alespoò $2^{h+1}$ vrcholù. \qed \h{Èerveno-èerné stromy} -\s{Definice:} Èerveno-èerný strom je binárny vyhledávaci strom s barevnými(èervenými a èernými) vrcholy a -externými vrcholy. Kdy¾ vrchol nemá nìkterého ze synú, na jeho míste je externý vrchol. +Ve~zbytku pøedná¹ky se vrátíme k~vyhledávacím stromùm a uká¾eme si je¹tì jeden zpùsob, +jak udr¾et logaritmickou hloubku stromu. + +\s{Definice:} {\I Èerveno-èerný strom} je binární vyhledávací strom, jeho¾ vrcholy jsou +obarvené (nìkteré èervenì, zbylé èernì), a ke~kterému byly pøidány externí vrcholy v¹ude +tam, kde pùvodnímu vrcholu chybí nìkterý ze~synù. Listy è-è stromu jsou tedy v¾dy externí. +Navíc platí následující axiomy: \s{Axiomy:} \itemize\ibull -\:Koøen a externé vrcholy sú èerné. +\:Koøen a externí vrcholy jsou èerné. \:Otec èerveného vrcholu je èerný. -\:Na v¹ech cestách z koøene do externího vrcholu je stejný poèet èerných vrcholù. +\:Na v¹ech cestách z~koøene do~externího vrcholu je stejný poèet èerných vrcholù. \endlist -\s{Vìta:} Èerveno-èerný strom na $n$ vrcholech má hloubku $\O(\log n)$. - -K této vìtì nabízime dva dùkazy. +\s{Vìta:} Èerveno-èerný strom o~$n$ vrcholech má hloubku $\O(\log n)$. \proof -1. Skomprimujeme hrany èerný-èervený a èerné vrcholy, které májí dva èervené syny, na vrchol. -Vznikne $2,4-$strom, který ma hloubku $\log n$, a proto je èerveno-èerný strom maximálne -2x vìt¹í. +Zkomprimujeme v¹echny hrany spojující èerný a èervený vrchol, èím¾ v¹echny èervené +vrcholy \uv{zasuneme} do~jejich èerných otcù. Vznikne $2,4$-strom a ten, jak u¾ víme, +má hloubku $\O(\log n)$. Pùvodní è-è strom má tedy hloubku nejvý¹e $2\log n$, co¾ je +asymptoticky taky $\O(\log n)$. \qed -\proof -2. Pøedpokladejme, ¾e $T$ je èerveno-èerný strom, který má na cestì z koøene do listu -$k$ èerných vrcholù. Pak pre poèet vrcholù stromu $T$ platí $2^k-1\leq n \leq 2^{2k}-1$. Nejmen¹í takový strom má v¹echny vrcholy obarvené èernì a je to úplný -pravidelný binární strom o hloubce $k-1$, co¾ dáva dolní odhad. Nejvìt¹í takový strom má v¹echny vrcholy v sudých hladinách obarveny èervenì a v lichých hladinách èernì, je to ùplný pravidelný binární strom o hloubce $2k-1$ a tím je dán horní odhad. Tedy $k\leq 1+\log n$. Z vlastností èerveno-èerných stromù plyne, ¾e $k\leq hloubka(T) \leq 2k$. +\noindent{\sl Alternativní dùkaz:} \foot{\uv{Vy máte protipøíklad? Nevadí, já mám dva dùkazy :)}} +Pøedpokládejme, ¾e $T$ je èerveno-èerný strom, který má na cestì z koøene do listu +$k$ èerných vrcholù. Pak pro poèet vrcholù stromu $T$ platí $2^k-1\leq n \leq 2^{2k}-1$. Nejmen¹í takový strom má v¹echny vrcholy obarvené èernì a je to úplný +pravidelný binární strom o hloubce $k-1$, co¾ dává dolní odhad. Nejvìt¹í takový strom má v¹echny vrcholy v sudých hladinách obarveny èervenì a v lichých hladinách èernì, je to úplný pravidelný binární strom o hloubce $2k-1$ a tím je dán horní odhad. Tedy $k\leq 1+\log n$. Z vlastností èerveno-èerných stromù plyne, ¾e $k\leq \(T) \leq 2k$. \qed -Niní si uká¾eme a rozebereme vkládaní do èerveno-èerných stromù. +Nyní si rozebereme vkládaní do èerveno-èerných stromù. -\s{Insert:} (v èerveno-èernom strome) -BÚNO nový uzel $t$ bude èervený. -Vlo¾íme uzel do stromu jako do standartního binárního vyhledávacího stromu. -Jestli¾e je pøedek èerný, jsme hotovi (viï obr. 1). -\figure{01.eps}{obr. 1}{2in} -Jestli¾e nikoliv, mù¾u nastat tøi nasledujíci pøípady: -\itemize\ibull -\:Je-li vrchol $t$ èervený a jeho otec je také èervený, pak øekneme, ¾e $t$ je porucha. Je-li $t$ porucha, -pak ji musíme nìjak opravit. Situace je na obrázku 2 - nejprve zále¾í na tom, jakou barvu má $s$, strýc $t$: -\figure{02.eps}{obr. 2}{1.5in} -\algo -\:$s$ je èervený. Pak pouze pøebarvíme $o$, $d$ a $s$ podle obrázku 3. -Nyní $d$ mù¾e být porucha, ov¹em posunutá o 2 hladiny vý¹e. -\figure{03.eps}{obr. 3}{3.5in} -Pro splnìní poslední podmínky je je je¹tì nutné pøebarvit koøen $d$ na èerno. - -\:$s$ je èerný. Pak zále¾í na tom, zda hodnota $t$ le¾í mezi hodnotami $o$ a $d$ nebo ne. Jinými slovy, zda cesta $t-o-d$ obsahuje zatáèku. -(a) Bez zatáèky: Provedeme rotaci a pøebarvíme podle obrázku 4. Splnìny budou podmínky 1, 2 i 3, tedy máme èervenoèerný strom: -\figure{04.eps}{obr. 4}{4in} -(b) Se zatáèkou. Provedeme dvojitou (LR) rotaci a pøebarvíme podle obrázku 5. Splnìny budou podmínky 1, 2 i 3, opìt máme rovnou èervenoèerný strom. -\figure{05.eps}{obr. 5}{4in} -\endalgo -\endlist +\s{Insert:} +Vlo¾íme hodnotu do stromu jako do standardního binárního vyhledávacího stromu, tedy jako list, +a obarvíme èervenì. První ani tøetí axiom jsme neporu¹ili a pokud je pøedek èerný, tak ani +axiom druhý, èili jsme hotovi: +\fig{01.eps}{2in} +Jestli¾e je otec~$o$ na¹eho vrcholu~$t$ také èervený, budeme øíkat, ¾e do¹lo k~{\I poru¹e} +a budeme se ji sna¾it opravit. Situace musí vypadat následovnì: +\fig{02.eps}{1.5in} +Nyní rozli¹íme následující tøi pøípady: +\itemize\ibull +\:Pokud strýc~$s$ vrcholu~$t$ je èervený, pak pouze pøebarvíme $o$, $d$ a $s$ podle následujícího obrázku. +Nyní $d$ mù¾e být porucha, ov¹em posunutá o 2 hladiny vý¹e, tak¾e pøi nejhor¹ím pokraèujeme +do~koøene a poslední poruchu opravíme pøebarvením koøene na~èerno. +\fig{03.eps}{3.5in} +\:Strýc $s$ je èerný. Pak zále¾í na tom, zda hodnota $t$ le¾í mezi hodnotami $o$ a $d$ nebo ne. Jinými slovy, zda cesta $t-o-d$ obsahuje zatáèku. + \numlist\nalpha + \:Bez zatáèky: Provedeme rotaci a pøebarvíme. Splnìny budou axiomy 1, 2 i 3, tedy máme èervenoèerný strom: + \fig{04.eps}{4in} + \:Se zatáèkou: Provedeme dvojitou (LR) rotaci a pøebarvíme. Opìt získáme korektní èervenoèerný strom: + \fig{05.eps}{4in} + \endlist +\endlist \bye