12-kostry/12-kostry.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{12}{Problém minimální kostry}{(zapsali K. Ka¹èák a M. Vachna)}
   4
   5 \s{Zadání úlohy:} Pro neorientovaný graf $G$ s~ohodnocením hran {\I váhami} $w: E(G) \rightarrow \bb R$,
   6 chceme najít kostru $T$ s minimálním ohodnocením $w(T)=\sum_{e\in E(T)} w(e)$.
   7
   8 \s{Navíc pøedpokládáme:} (bez újmy na~obecnosti)
   9 \itemize\ibull
  10 \:Graf $G$ je souvislý (jinak ho nejprve rozlo¾íme na komponenty).
  11 \:$\forall e,f \in E(G$) : $e\neq f \Rightarrow w(e)\neq w(f)$.
  12 \endlist
  13
  14 Nyní si uká¾eme tøi algoritmy pro hledání minimální kostry, konkrétnì se jedná
  15 o~Jarníkùv, Borùvkùv a Kruskalùv algoritmus.
  16
  17 \h{Jarníkùv algoritmus}
  18
  19 \s{Algoritmus:}
  20
  21 \algo
  22 \algin Graf~$G$ s~ohodnocením~$w$.
  23 \:Zvolíme libovolný vrchol $v_0\in V(G)$.
  24 \:$T\leftarrow(\left\{v_0\right\},\emptyset)$ (zatím jednovrcholový strom)
  25 \:Dokud $\vert V(T) \vert \neq n$:
  26 \::Vybereme hranu $uv\in E(G) : u\in V(T), v\notin V(T)$ tak, aby $w(uv)$ byla minimálni.
  27 \::$T\leftarrow T+uv$.
  28 \algout Minimální kostra~$T$.
  29 \endalgo
  30
  31 \s{Vìta:} Jarníkùv algoritmus se zastaví po maximálnì $n$ iteracích a vydá minimální kostru grafu $G$.
  32
  33 \proof
  34 Pøi ka¾dé iteraci algoritmus pøidá jeden vrchol do~$T$, a~proto se po~maximálnì $n$ iteracích zastaví.
  35 Vydaný graf je strom, proto¾e se stále pøidává list k ji¾ existujícímu stromu, a~jeliko¾ má $n$~vrcholù,
  36 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:
  37
  38 {\narrower
  39
  40 \s{Definice:} {\I Øez} v~grafu $G=(V,E)$ je mno¾ina hran $F\subseteq E$ taková, ¾e $\exists  U\subset V$ :
  41 $F=\left\{uv\in E:u\in U, v\notin U \right\}$.
  42
  43 \s{Lemma:} Pokud $G$ je graf, $w$ jeho prosté ohodnocení, $F$ je øez v grafu $G$ a $f$ je nejlehèí hrana v øezu
  44 $F$, pak pro ka¾dou minimální kostru $T$ grafu $G$ je $f\in E(T)$.
  45
  46 \proof
  47 Buï $T$ kostra a $f=uv\notin E(T)$. Pak existuje cesta $P\subseteq T$ spojující $u$ a $v$.
  48 Cesta musí øez alespoò jednou pøekroèit. Proto existuje $e\in P \cap F$ a navíc víme, ¾e $w(e) > w(f)$. Uva¾me $T'=T-e+f$.
  49 Tento graf je rovnì¾ kostra grafu $G$, proto¾e odebraním hrany $e$ se graf rozpadne na dvì komponenty a pøidáním
  50 hrany $f$ se tyto komponenty opìt spojí. Navíc $w(T')=w(T)-w(e)+w(f)<w(T)$.
  51 \qed
  52
  53 }
  54
  55 \>V~dùkazu korektnosti Jarníkova algoritmu toto lemma vyu¾ijeme tak, ¾e si v¹imneme, ¾e hrany mezi
  56 vrcholy stromu~$T$ a zbytkem grafu tvoøí øez a algoritmus nejlehèí hranu tohoto øezu pøidá
  57 do~$T$. Podle lemmatu tedy v¹echny hrany~$T$ musí být souèástí ka¾dé minimální kostry a jeliko¾~$T$ je strom,
  58 musí být minimální kostrou.
  59
  60 \qed
  61
  62
  63 \s{Dùsledky:} Graf $G$ s prostým ohodnocením má pravì jednu minimální kostru. Minimální kostra je
  64 jednoznaènì urèená lineárním uspoøádáním hran.
  65
  66 \s{Implementace:}
  67 \itemize\ibull
  68 \:Pøímoèará: pamatujeme si, které vrcholy a hrany jsou v kostøe $T$ a které ne. Èasová slo¾itost je $\O(nm)$.
  69 \:Chytøej¹í: Pro $v\notin V(T)$ si pamatujeme $D(v)=\min\left\{w(uv):u\in T\right\}$. Pøi ka¾dém
  70 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
  71 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ì
  72 zlep¹íme na~$\O(n^2+m)=\O(n^2)$.
  73 \:Také se dá pou¾ít halda pro uchovávání hran nebo hodnot~$D(v)$.
  74 \endlist
  75
  76 \h{Borùvkùv algoritmus}
  77
  78 \s{Algoritmus:}
  79
  80 \algo
  81 \algin Graf~$G$ s~ohodnocením~$w$.
  82 \:$F\leftarrow(V(G),\emptyset)$
  83 \:Dokud $F$ má alespoò dvì komponenty:
  84 \::Pro ka¾dou komponentu $T_i$ grafu $F$ vybereme nejlehèí incidentní hranu $t_i$.
  85 \::V¹echny hrany $t_i$ pøidáme do $F$.
  86 \algout Minimální kostra~$F$.
  87 \endalgo
  88
  89 \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$.
  90
  91 \proof
  92 V¹imnìme si nejprve, ¾e po~$k$ iteracích mají v¹echny komponenty grafu~$F$ minimálnì $2^k$ vrcholù
  93 (na~poèátku jsou v¹echny komponenty jednovrcholové, v~ka¾dé dal¹í iteraci se komponenty sluèují do~vìt¹ích,
  94 ka¾dá s~alespoò jednou sousední, tak¾e se velikosti komponent minimálnì zdvojnásobí).
  95 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
  96 se zastaví.
  97
  98 Hrany mezi ka¾dou komponentou a~zbytkem grafu tvoøí øez, tak¾e podle pøedchozího lemmatu v¹echny
  99 hrany pøidané do~$F$ musí být souèástí (jednoznaènì urèené) minimální kostry. Graf $F\subseteq G$
 100 je tedy v¾dy les a a¾ se algoritmus zastaví, bude roven minimální kostøe.
 101 \qed
 102
 103 \s{Implementace:}
 104 \itemize\ibull
 105 \:Inicializace pøímoèará.
 106 \:Pomocí DFS rozlo¾íme les na komponenty. Pro ka¾dý vrchol si pamatujeme èíslo komponenty.
 107 \:Pro ka¾dou hranu zjistíme, do které komponenty patøí, a pro ka¾dou komponentu
 108 si uchováme nejlehèí hranu.
 109 \endlist
 110
 111 \>Takto doká¾eme ka¾dou iteraci provést v~èase $\O(m)$ a celý algoritmus dobìhne v~$\O(m\log n)$.
 112
 113 \h{Kruskalùv neboli hladový algoritmus}
 114
 115 \s{Algoritmus:}
 116
 117 \algo
 118 \algin Graf~$G$ s~ohodnocením~$w$.
 119 \:Setøídíme v¹echny hrany z $E(G)$ tak, aby: $w(e_1)<...<w(e_m)$.
 120 \:$F\leftarrow (V(G),\emptyset)$.
 121 \:Pro $i=1$ do $m$:
 122 \::Pokud $F+e_i$ je acyklický, provedeme $F\leftarrow F+e_i$.
 123 \algout Minimální kostra~$F$.
 124 \endalgo
 125
 126 \s{Vìta:} Kruskalùv algoritmus se zastaví po~$m$ iteracích a vydá minimální kostru.
 127
 128 \proof
 129 Ka¾dá iterace algoritmu zpracovává jednu hranu, tak¾e iterací je~$m$. Indukcí doká¾eme,
 130 ¾e~$F$ je v¾dy podgrafem minimální kostry: prázdné poèáteèní~$F$ je podgrafem èehokoliv,
 131 ka¾dá hrana, kterou pak pøidáme, je minimální v~øezu oddìlujícím nìjakou
 132 komponentu~$F$ od~zbytku grafu (ostatní hrany tohoto øezu je¹tì nebyly
 133 zpracovány, a~tudí¾ jsou tì¾¹í). Naopak ¾ádná hrana, kterou jsme se rozhodli
 134 do~$F$ nepøidat, nemù¾e být souèástí minimální kostry, jeliko¾ s~hranami,
 135 o~kterých ji¾ víme, ¾e v~minimální kostøe le¾í, tvoøí kru¾nici. \qed
 136
 137 \s{Implementace:}
 138 \itemize\ibull
 139 \:Setøídìní v èase $\O(m\log m)=\O(m\log n)$.
 140 \:Pak potøebujeme udr¾ovat komponenty souvislosti grafu~$F$, abychom umìli rychle
 141   urèit, jestli právì zpracovávaná hrana vytvoøí kru¾nici. Potøebujeme tedy strukturu
 142   pro udr¾ování komponent souvislosti, které se $m$-krát zeptáme, zda dva vrcholy
 143   le¾í v~té¾e komponentì (tomu budeme øíkat operace \<Find>), a~$(n-1)$-krát spojíme
 144   dvì komponenty do jedné (\<Union>).
 145 \endlist
 146
 147 \>Kruskalùv algoritmus tedy pobì¾í v~èase $\O(m\log n + mT_f + nT_u)$, kde~$T_u$ je
 148 èas na~provedení jedné operace \<Union> a $T_f$ na~operaci \<Find>.
 149
 150 \s{Jednoduchá struktura pro komponenty:}
 151 Budeme pamatovat v~poli èísla komponent, ve~kterých le¾í jednotlivé vrcholy. \<Find> zvládneme v~èase $\O(1)$,
 152 ale \<Union> bude stát $\O(n)$. Celý algoritmus pak pobì¾í v~èase $\O(m\log n+ m + n^2) = \O(m\log n+n^2)$.
 153
 154 \s{Chytøej¹í struktura:} Ka¾dou komponentou si ulo¾íme jako strom orientovaný smìrem ke koøeni
 155 -- ka¾dý vrchol si pamatuje svého otce, navíc ka¾dý koøen si pamatuje velikost komponenty.
 156 Operace \<Find> vystoupá z~obou vrcholù ke~koøeni a koøeny porovná. \<Union> rovnì¾ najde
 157 koøeny a pøipojí koøen men¹í komponenty pod koøen té vìt¹í. Obojí zvládneme v~èase lineárním
 158 v~hloubce stromu a jak si uká¾eme, tato hloubka je v¾dy nejvý¹e logaritmická, a proto celý Kruskalùv
 159 algoritmus pobì¾í v~èase $\O(m\log n + m\log n + n\log n) = \O(m\log n)$.\foot{%
 160 Drobnou úpravou bychom mohli dosáhnout daleko efektivnìj¹í struktury, ale tu bychom neupotøebili,
 161 jeliko¾ by nás stejnì brzdilo tøídìní, a analýza slo¾itosti by byla \dots\ inu, slo¾itìj¹í.}
 162
 163 \s{Lemma:} Strom hloubky $h$ má alespoò $2^h$ prvkù.
 164
 165 \proof
 166 Indukcí: Pokud \<Union> spojí strom s~hloubkou $h$ s jiným s~hloubkou men¹í ne¾ $h$, pak hloubka výsledného
 167 stromu zùstává~$h$. Pokud spojuje dva stromy stejné hloubky~$h$, pak má výsledný strom hloubku $h+1$.
 168 Z~indukèního pøedpokladu víme, ¾e strom hloubky $h$ má minimálnì $2^h$ vrcholù,
 169 a~tedy výsledný strom hloubky $h+1$ má alespoò $2^{h+1}$ vrcholù. \qed
 170
 171 \h{Èerveno-èerné stromy}
 172
 173 Ve~zbytku pøedná¹ky se vrátíme k~vyhledávacím stromùm a uká¾eme si je¹tì jeden zpùsob,
 174 jak udr¾et logaritmickou hloubku stromu.
 175
 176 \s{Definice:} {\I Èerveno-èerný strom} je binární vyhledávací strom, jeho¾ vrcholy jsou
 177 obarvené (nìkteré èervenì, zbylé èernì), a ke~kterému byly pøidány externí vrcholy v¹ude
 178 tam, kde pùvodnímu vrcholu chybí nìkterý ze~synù. Listy è-è stromu jsou tedy v¾dy externí.
 179 Navíc platí následující axiomy:
 180
 181 \s{Axiomy:}
 182 \itemize\ibull
 183 \:Koøen a externí vrcholy jsou èerné.
 184 \:Otec èerveného vrcholu je èerný.
 185 \:Na v¹ech cestách z~koøene do~externího vrcholu je stejný poèet èerných vrcholù.
 186 \endlist
 187
 188 \s{Vìta:} Èerveno-èerný strom o~$n$ vrcholech má hloubku $\O(\log n)$.
 189
 190 \proof
 191 Zkomprimujeme v¹echny hrany spojující èerný a èervený vrchol, èím¾ v¹echny èervené
 192 vrcholy \uv{zasuneme} do~jejich èerných otcù. Vznikne $2,4$-strom a ten, jak u¾ víme,
 193 má hloubku $\O(\log n)$. Pùvodní è-è strom má tedy hloubku nejvý¹e $2\log n$, co¾ je
 194 asymptoticky taky $\O(\log n)$.
 195 \qed
 196
 197 \noindent{\sl Alternativní dùkaz:} \foot{\uv{Vy máte protipøíklad? Nevadí, já mám dva dùkazy :)}}
 198 Pøedpokládejme, ¾e $T$ je èerveno-èerný strom, který má na cestì z koøene do listu
 199 $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ý
 200 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 \<hloubka>(T) \leq 2k$.
 201 \qed
 202
 203 Nyní si rozebereme vkládaní do èerveno-èerných stromù.
 204
 205 \s{Insert:}
 206 Vlo¾íme hodnotu do stromu jako do standardního binárního vyhledávacího stromu, tedy jako list,
 207 a obarvíme èervenì. První ani tøetí axiom jsme neporu¹ili a pokud je pøedek èerný, tak ani
 208 axiom druhý, èili jsme hotovi:
 209 \fig{01.eps}{2in}
 210 Jestli¾e je otec~$o$ na¹eho vrcholu~$t$ také èervený, budeme øíkat, ¾e do¹lo k~{\I poru¹e}
 211 a budeme se ji sna¾it opravit. Situace musí vypadat následovnì:
 212
 213 \fig{02.eps}{1.5in}
 214
 215 Nyní rozli¹íme následující tøi pøípady:
 216 \itemize\ibull
 217 \:Pokud strýc~$s$ vrcholu~$t$ je èervený, pak pouze pøebarvíme $o$, $d$ a $s$ podle následujícího obrázku.
 218 Nyní $d$ mù¾e být porucha, ov¹em posunutá o 2 hladiny vý¹e, tak¾e pøi nejhor¹ím pokraèujeme
 219 do~koøene a poslední poruchu opravíme pøebarvením koøene na~èerno.
 220 \fig{03.eps}{3.5in}
 221 \: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.
 222   \numlist\nalpha
 223   \:Bez zatáèky: Provedeme rotaci a pøebarvíme. Splnìny budou axiomy 1, 2 i 3, tedy máme èervenoèerný strom:
 224     \fig{04.eps}{4in}
 225   \:Se zatáèkou: Provedeme dvojitou (LR) rotaci a pøebarvíme. Opìt získáme korektní èervenoèerný strom:
 226     \fig{05.eps}{4in}
 227   \endlist
 228 \endlist
 229
 230 \bye