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 Pro zaèátek si definujme, co budeme dìlat, v jakých grafech budeme minimální kostru hledat.
   6
   7 \s{Zadání úlohy:} Pro neorientovaný graf $G$ s ohodnocením hran $w: E(G) \rightarrow \bb R$,
   8 chceme najít kostru $T$ s minimálním ohodnocením $w(T)=\sum_{e\in E(T)} w(e)$.
   9
  10 \s{Pøedpoklady úlohy:}
  11 \itemize\ibull
  12 \:BÚNO graf $G$ je souvislý
  13 \:$\forall e,f \in E(G$) : $e\neq f \Rightarrow w(e)\neq w(f)$
  14 \endlist
  15
  16 Nyní si uká¾eme tøi algoritmy øe¹ící zadanou úlohu, konkrétnì se jedná o Jarníkùv, Borùvkùv a Kruskalùv
  17 algoritmus.
  18
  19 \s{Algoritmus:} (Jarníkùv)
  20
  21 \def\concat{\mathop{\hbox{.}}}
  22
  23 \algo
  24 \:Zvolíme libovolný vrchol $v_0\in V(G)$, $T\leftarrow(\left\{v_0\right\},\emptyset)$.
  25 \:Dokud $\vert V(T) \vert \neq n$:
  26 \::Vybereme hranu $uv\in E(G) : u\in V(T), v\notin V(T)$, aby $w(uv)$ bylo minimálni.
  27 \::$T\leftarrow T+uv$
  28 \endalgo
  29
  30 \s{Vìta:} Jarníkùv algoritmus se zastaví po maximálnì $n$ iteracích a vydá minimální kostru grafu $G$.
  31
  32 \proof
  33 Koneènost - pøi ka¾dé iteraci se pøidá jeden vrchol $\Rightarrow$ po maximálnì $n$ iteracích se zastaví.
  34 Vydaný graf je strom, proto¾e se stále pøidává list k ji¾ existujícímu stromu. Vydaný graf má $n$
  35 vrcholù $\Rightarrow$ vydaný graf je kostra. Zbývá nám u¾ jen dokázat, ¾e kostra je minimální. To
  36 udìláme pomocí následujícího lemmatu.
  37
  38 Proto aby jsme byli schopni zformulovat i dokázat lemma, je nutné je¹tì vysvìtlit pojem øez v grafu.
  39
  40 \s{Definice:} Ø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$ taková, ¾e $w(e) > w(f)$. Uva¾me $T'=T-e+f$.
  49 $T'$ 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 opìt spojí. Navíc $w(T')=w(T)-w(e)+w(f)<w(T)$.
  51 \qed
  52
  53 Kdy¾ nahlédneme do dùkazu minimálnosti vydané kostry grafu pomocí lemmatu, mù¾eme po ka¾dé iteraci rozdìlit graf na èást, v které jsou v¹echny vrcholy v zatím vytvoøené kostøe, a na èást, v které je¹tì ¾ádny z vrcholù není v kostøe obsa¾en. Hrany spojujíci títo èásty tvoøí øez v grafu. Z tìchto hran vybíra algoritmus tu nejlehèí hranu a lemma øíka, ¾e táto hrana urèitì patøí do minimálni kostry, tedy výsledná kostra je urèitì minimálni.
  54 \qed
  55
  56
  57 \s{Dùsledky:} Graf $G$ s prostým ohodnocením má pravì jednu minimální kostru. Minimální kostra je
  58 jednoznaènì urèená lineárním uspoøádáním hran.
  59
  60 \s{Implementace:}
  61 \itemize\ibull
  62 \:Pøímoèará: pamatujeme si, které vrcholy a hrany jsou v kostøe $T$ a které ne. Èasová slo¾itost je $\O(nm)$.
  63 \:Pro $v\notin V(T)$ si pamatujeme $D(v)=$min$\left\{w(uv):u\in T\right\}$. Èasová slo¾itost je $\O(n^2+m)=\O(n^2)$.
  64 \endlist
  65
  66 \s{Algoritmus:} (Borùvkùv)
  67
  68 \def\concat{\mathop{\hbox{.}}}
  69
  70 \algo
  71 \:Les $F\leftarrow(V(G),\emptyset)$.
  72 \:Dokud $F$ má alespoò dvì komponenty:
  73 \::Pro ka¾dou komponentu $T_i$ lesa $F$ vybereme nejlehèí incidentní hranu $t_i$.
  74 \::V¹echny hrany $t_i$ pøidáme do $F$.
  75 \endalgo
  76
  77 \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$.
  78
  79 \proof
  80 Po $k$ iteracích mají v¹echny stromy minimálnì $2^k$ vrcholù, $\forall i : \vert T_i\vert \geq 2^k$.
  81 Indukcí podle $k$: ka¾dá incidentní hrana vede z $T_i$ do $T_j$. Po $k$ iteracích pøidáním incidentní hrany
  82 spojíme 2 stromy s alespoò $2^k$ vrcholy, tím vznikne strom s alespoò $2^{k+1}$ vrcholy.
  83 Algoritmus vydá kostru, staèí nahlédnout, zda je minimální. To se lehce uká¾e u¾itím pøedchozího lemmatu.
  84 V¾dy pøidáváme hranu, která je minimální v øezu mezi $T$ a ostatními vrcholy grafu $G$.
  85 \qed
  86
  87 \s{Implementace:}
  88 \itemize\ibull
  89 \:Inicializace pøímoèará.
  90 \:Pomocí DFS rozlo¾íme les na komponenty. Pro ka¾dý vrchol si pamatujeme èíslo komponenty.
  91 \:Pro ka¾dou hranu zjistíme, do které komponenty patøí, a pro ka¾dou komponentu
  92 si uchováme nejlehèí hranu.
  93
  94 Rozlo¾ení lesa a zji¹tìní, do jaké komponenty patøí která hrana má èasovou slo¾itost $\O(m)$.
  95 \endlist
  96
  97 Výsledná èasová slo¾itost je $\O(m\log n)$.
  98
  99 \s{Algoritmus:} (Kruskalùv èili \uv{hladový})
 100
 101 \def\concat{\mathop{\hbox{.}}}
 102
 103 \algo
 104 \:Setøídíme v¹echny hrany z $E(G)$ tak, aby: $w(e_1)<...<w(e_m)$.
 105 \:$F\leftarrow (V(G),\emptyset)$.
 106 \:Pro $i=1$ do $m$:
 107 \::pokud $F+e_i$ je acyklický:
 108 \::$F\leftarrow F+e_i$.
 109 \endalgo
 110
 111 \s{Vìta:} Kruskalùv algoritmus se zastaví po $m$ iteracích a vydá minimální kostru grafu $G$.
 112
 113 \proof
 114 Podle lemmatu strom, který je výstupem algoritmu, je minimální kostra. Indukcí snadno doká¾eme, ¾e
 115 stále platí $F\subseteq$ $minimálni$ $kostry$ a v¾dy do $F$ pøidáváme hranu $f$, která je minimální v øezu
 116 a spojuje dvì komponenty. Kdy¾ hranu do kostry nepøidáme, znamená to, ¾e v grafu by vznikla kru¾nice. Tuto hranu mù¾eme zahodit, preto¾e ak by mnìla být súèastí minimálni kostry, znamenalo by to, ¾e by jsme mnìli zahodit nìkterou hranu s kru¾nice, ale tá hrana je urèitì lehèí jako právì pøidávaná hrana a kostra by ji¾ nebyla minimálni.
 117 \qed
 118
 119 \s{Implementace:}
 120 \itemize\ibull
 121 \:Setøídìní v èase $\O(m\log m)=\O(m\log n)$.
 122 \:Kdy¾ si pamatuji vrcholy v poli:
 123 Find(u,v) zjistí zda vrcholy $u$ a $v$ le¾í v stejné komponentì. Jedna operace má èasovou slo¾itost $\O(1)$. Find
 124 se provede $m$-krát, proto je èasová slo¾itost celkem $\O(m)$.
 125 Union(u,v) pøidá hranu a tím spojí dvì komponenty. Jedna operace má èasovou slo¾itost $\O(n)$. Union se provede
 126 $n$-krát, proto je èasová slo¾itost celkem $\O(n^2)$.
 127 Výslední èasová slo¾itost je $\O(m\log n+m+n^2)=$\O$(n^2+m\log n)$
 128
 129 \:Jinak: Ka¾dá komponenta je strom orientovaný smìrem ke koøenu. Ka¾dý vrchol si pamatuje
 130 svého otce, ka¾dý koøen si pamatuje velikost komponenty.
 131 Find(u,v) najde koøeny a porovná je. Èasová slo¾itost je $\O(hloubka$ $komponenty)$.
 132 Union(u,v) najde koøeny komponent, do kterých patøí vrcholy $u$ a $v$ a pøipojí komponentu s men¹í hloubkou ke koøeni komponenty s vìt¹í hloubkou. Hloubky obou komponent i výsledné spojené komponenty jsou maximálnì logaritmické. Èasová slo¾itost je $\O(hloubka$ $komponenty)$. Find a Union mají tedy èasovou slo¾itost $\O(\log n)$. Výsledná èasová slo¾itost je $\O(m\log n)$.
 133 \endlist
 134
 135 \s{Lemma:} Strom hloubky $h$ má alespoò $2^h$ prvkù.
 136
 137 \proof
 138 Pokud Union spojí strom s hloubkou $h$ s jiným s hloubkou men¹í ne¾ $h$, pak hloubka výsledného
 139 stromu zùstává $h$. Pokud spojuje dva stromy hloubky $h$, pak výsledný strom má hloubku $h+1$. Jak ji¾
 140 víme, strom hloubky $h$ má minimálnì $2^h$ vrcholù, proto výsledný strom hloubky $h+1$ má alespoò $2^{h+1}$ vrcholù.
 141 \qed
 142
 143 \h{Èerveno-èerné stromy}
 144
 145 \s{Definice:} Èerveno-èerný strom je binární vyhledávací strom s barevnými(èervenými a èernými) a
 146 externími vrcholy. Externí vrchol je takový pseudovrchol, ktorý pøidávame ka¾dímu vrcholu, kterému
 147 chybí jeden nebo dva syny. Externí vrchol je tedy pøipojen na místo neexistujíciho syna.
 148
 149
 150 \s{Axiomy:}
 151 \itemize\ibull
 152 \:Koøen a externí vrcholy jsou èerné.
 153 \:Otec èerveného vrcholu je èerný.
 154 \:Na v¹ech cestách z koøene do externího vrcholu je stejný poèet èerných vrcholù.
 155 \endlist
 156
 157 \s{Vìta:} Èerveno-èerný strom na $n$ vrcholech má hloubku $\O(\log n)$.
 158
 159 K této vìtì nabízíme dva dùkazy.
 160
 161 \proof
 162 1. Zkomprimujeme hrany èerný-èervený a èerné vrcholy, které mají dva èervené syny, na vrchol.
 163 Vznikne $2,4$-strom, který má hloubku $\O(\log n)$, a tedy èerveno-èerný strom má hlouku maximálnì
 164 $2\log n$, co¾ je asymptoticky taky $\O(\log n)$.
 165 \qed
 166
 167 \proof
 168 2. Pøedpokládejme, ¾e $T$ je èerveno-èerný strom, který má na cestì z koøene do listu
 169 $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ý
 170 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$.
 171 \qed
 172
 173 Nyní si uká¾eme a rozebereme vkládaní do èerveno-èerných stromù.
 174
 175 \s{Insert:} (v èerveno-èerném stromì)
 176 BÚNO nový uzel $t$ bude èervený.
 177 Vlo¾íme uzel do stromu jako do standardního binárního vyhledávacího stromu.
 178 Jestli¾e je pøedek èerný, jsme hotovi (viz obr. 1).
 179 \figure{01.eps}{obr. 1}{2in}
 180 Jestli¾e nikoliv, mohou nastat tøi následující pøípady:
 181 \itemize\ibull
 182 \:Je-li vrchol $t$ èervený a jeho otec je také èervený, pak øekneme, ¾e $t$ je porucha. Je-li $t$ porucha,
 183 pak ji musíme nìjak opravit. Situace je na obrázku 2 $-$ nejprve zále¾í na tom, jakou barvu má $s$, strýc vrcholu $t$:
 184 \figure{02.eps}{obr. 2}{1.5in}
 185 \algo
 186 \:$s$ je èervený. Pak pouze pøebarvíme $o$, $d$ a $s$ podle obrázku 3.
 187 Nyní $d$ mù¾e být porucha, ov¹em posunutá o 2 hladiny vý¹e.
 188 \figure{03.eps}{obr. 3}{3.5in}
 189 Pro splnìní poslední podmínky je je je¹tì nutné pøebarvit koøen $d$ na èerno.
 190
 191 \:$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.
 192 (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:
 193 \figure{04.eps}{obr. 4}{4in}
 194 (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.
 195 \figure{05.eps}{obr. 5}{4in}
 196 \endalgo
 197 \endlist
 198
 199 \bye