12-kostry/12-kostry.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{10}{Problém minimálni 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álni kostru hledat.
   6
   7 \s{Zadání úlohy:} Pro neorientovaný graf $G$ s ohodnocením hran $w: E(G) \rightarrow R$,
   8 chceme najít kostru $T$ s minimálnim 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¹íci zadanú úlohu, konkrétne 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=(\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)$, min $w(uv)$
  27 \:              $T\leftarrow T+uv$
  28 \endalgo
  29
  30 \s{Vìta:} Jarníkùv algorimtus se zastaví po maximálne $n$ iteracích a vydá minimálni kostru grafu $G$.
  31
  32 \proof
  33 Koneènost - pøi ka¾dé iteraci se pøidá jeden vrchol $\Rightarrow$ po maximálne $n$ iteracích se zastaví.
  34 Vydaný graf je strom, proto¾e se stále pøidáva list k ji¾ existujícimu stromu. Vydaný graf má $n$
  35 vrcholù $\Rightarrow$ vydaný graf je kostra. Ostáva nám u¾ jen dokázat, ¾e kostra je minimálni. To
  36 dokazuje nesledujíci Lemma.
  37 \qed
  38
  39 Proto aby jsme byli schopni sformulovat i dokázat Lemma, je nutná je¹tì vysvìtlit pojem øez v grafu.
  40
  41 \s{Definice:} Øez v grafu $G=(V,E)$ je mno¾ina hran $F\subseteq E$ taková, ¾e $\exists  U\subset V$ :
  42 $F=\left\{uv\in E \vert u\in U, v\notin U \right\}$.
  43
  44 \s{Lemma:} Pokud $G$ je graf, $w$ jeho prosté ohodnocení, $F$ je øez v grafu $G$ a $f$ je nejlehèí hrana v øezu
  45 $F$, pak pro ka¾dou minimálni kostru $G$ je $f\in E(T)$.
  46
  47 \proof
  48 Buï $T$ kostra a $f\notin E(T)$, pak $\exists$ cesta $P\subseteq T$ spojujíci $u$ a $v$ (vrcholy hrany $f$).
  49 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$.
  50 $T'$ je rovne¾ kostra grafu $G$, proto¾e odebraním hrany $e$ se graf rozpadne na dvì komponenty a pøidáním
  51 hrany $f$ se opìt spojí. $w(T')=w(T)-w(e)+w(f)<w(T)$
  52 \qed
  53
  54 \s{Dùsledky:} Graf $G$ s prostým ohodnocením ma pravì 1 minimálni kostru. Minimálni kostra je
  55 jednoznaène urèená lineárnim uspoøádaním hran.
  56
  57 \s{Implementace:}
  58 \itemize\ibull
  59 \:Pøímoèaøá - pamatujeme si, které vrcholy a hrany jsou v kostøe $T$ a které ne. Èasová slo¾itost je $\O(nm)$
  60 \: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)$
  61 \endlist
  62
  63 \s{Algoritmus:} (Borùvkùv)
  64
  65 \def\concat{\mathop{\hbox{.}}}
  66
  67 \algo
  68 \:Les $F=(V(G),\emptyset)$.
  69 \:Dokud $F$ má alespoò dvì komponenty :
  70 \:              $\forall$ komponentu $T_i$ vybereme nejlehèí incidentní hranu $t_i$.
  71 \:              V¹echny hrany $t_i$ pøidáme do $F$.
  72 \endalgo
  73
  74 \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$.
  75
  76 \proof
  77 Po $k$ iteracích mají v¹echny stromy minimálne $2^k$ vrcholù, $\forall$ i : $\vert T_i\vert \geq 2^k$.
  78 Indukcí podle $k$: ka¾dá incidentní hrana vede z $T_i$ do $T_j$. Po $k$ iteracích pøidáním incidentní hrany
  79 spojíme 2 stromy s alespoò $2^k$ vrcholama, tím vznikne strom s $2^{k+1}$ vrcholama.
  80 Algoritmus vydá kostru, staèí nahlédnout, zda je minimálni. To se lehce uká¾e u¾itím pøedchozí Lemmy.
  81 V¾dy pøidávame hranu, která je minimálni mezi $T$ a ostatními vrcholy grafu $G$.
  82 \qed
  83
  84 \s{Implemntace:}
  85 \itemize\ibull
  86 \:Inicializace pøímoèaøá.
  87 \:Pomocí DFS rozlo¾íme les na komponenty. $\forall$ vrchol si pamatujeme èíslo komponenty.
  88 \:Pro $\forall$ hranu zjistíme, do které komponenty patøí a pro ka¾dou komponentu
  89 jsi uchováme nejlehèí hranu.
  90
  91 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)$
  92 \endlist
  93
  94 \s{Algoritmus:} (Kruskalùv èili `hladový`)
  95
  96 \def\concat{\mathop{\hbox{.}}}
  97
  98 \algo
  99 \:Zetøídime v¹echny hrany z $E$ : $w(e_1)<...<w(e_m)$.
 100 \:$F\leftarrow (V(G),\emptyset)$.
 101 \:Pro $i=1$ do $m$ :
 102 \:              pokud $F+e_i$ je acyklický :
 103 \:              $F\leftarrow F+e_i$
 104 \endalgo
 105
 106 \s{Vìta:} Kruskalùv `hladový` algorimtus se zastaví po $m$ iteracích a vydá minimálni kostru grafu $G$.
 107
 108 \proof
 109 Podle Lemmy strom, který je výstupem algorimtu, je minimálni kostra. Indukcí snadno doká¾eme, ¾e
 110 stále platí $F\subseteq$ $minimálni$ $kostry$ a v¾dy do $F$ pøidávame hranu $f$, která je minimálni v øezu
 111 a spojuje dvì komponenty.
 112 \qed
 113
 114 \s{Implemntace:}
 115 \itemize\ibull
 116 \:Zotøídení $\O(m\log n)$.
 117 \:Kdy¾ si pamatuji vrcholy $v$ poli:
 118 Find(u,v) zistí zda vrcholy $u$ a $v$ le¾í v stejné komponente. Jedna operace má èasovou slo¾itost $\O(1)$. Find
 119 se provede $m-$krát, proto je èasová slo¾itost celkem $\O(m)$.
 120 Union(u,v) pøidá hranu a tím spojí dvì komponenty. Jedna operace má èasovou slo¾itost $\O(n)$. Union se provede
 121 $n-$krát, proto je èasová slo¾itost celkem $\O(n^2)$.
 122 Výslední èasová slo¾itost je $\O(m\log n+m+n^2)=$\O$(n^2+m\log n)$
 123
 124 \:Jinak: $\forall$ komponenta je strom orientovaný smìrem ke koøenu. $\forall$ vrchol si pamatuje
 125 svého otce, $\forall$ koøen si pamatuje velikost komponenty.
 126 Find(u,v) najde koøeny a porovná je. Èasová slo¾itost je $\O(hloubka$ $komponenty)$.
 127 Union(u,v) najde koøeny a pøipojí men¹í komponentu pod vìt¹í (logaritmická hloubka). Èasová slo¾itost je $\O(hloubka$ $komponenty)$.
 128 Find a Union mají teda èasovou slo¾itost $\O(\log n)$. Výslední èasová slo¾itost je $\O(m\log n)$.
 129 \endlist
 130
 131 \s{Lemma:} Strom hloubky $h$ má alespoò $2^h$ prvkù.
 132
 133 \proof
 134 Pokud Union spojí stromy jeden s hloubkou $h$ a druhý s hloubkou men¹í ne¾ $h$, pak hloubka výsledního
 135 stromu zústava $h$. Pokud spojuje dva stromy hloubky $h$, pak vyslední strom má hloubku $h+1$. Jak ji¾
 136 víme, strom hloubky $h$ má minimálne $2^h$, proto výslednej strom hloubky $h+1$ má $2^{h+1}$ vrcholù.
 137 \qed
 138
 139 \h{Èerveno-èerné stromy}
 140
 141 \s{Definice:} Èerveno-èerný strom je binárny vyhledávaci strom s barevnými(èervenými a èernými) vrcholy a
 142 externými vrcholy. Kdy¾ vrchol nemá nìkterého ze synú, na jeho míste je externý vrchol.
 143
 144 \s{Axiomy:}
 145 \itemize\ibull
 146 \:Koøen a externé vrcholy sú èerné.
 147 \:Otec èerveného vrcholu je èerný.
 148 \:Na v¹ech cestách z koøene do externího vrcholu je stejný poèet èerných vrcholù.
 149 \endlist
 150
 151 \s{Vìta:} Èerveno-èerný strom na $n$ vrcholech má hloubku $\O(\log n)$.
 152
 153 K této vìtì nabízime dva dùkazy.
 154
 155 \proof
 156 1. Skomprimujeme hrany èerný-èervený a èerné vrcholy, které májí dva èervené syny, na vrchol.
 157 Vznikne $2,4-$strom, který ma hloubku $\log n$, a proto je èerveno-èerný strom maximálne
 158 2x vìt¹í.
 159 \qed
 160
 161 \proof
 162 2. Pøedpokladejme, ¾e $T$ je èerveno-èerný strom, který má na cestì z koøene do listu
 163 $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ý
 164 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$.
 165 \qed
 166
 167 Niní si uká¾eme a rozebereme vkládaní do èerveno-èerných stromù.
 168
 169 \s{Insert:} (v èerveno-èernom strome)
 170 BÚNO nový uzel $t$ bude èervený.
 171 Vlo¾íme uzel do stromu jako do standartního binárního vyhledávacího stromu.
 172 Jestli¾e je pøedek èerný, jsme hotovi (viï obr. 1).
 173 \figure{01.eps}{obr. 1}{2in}
 174 Jestli¾e nikoliv, mù¾u nastat tøi nasledujíci pøípady:
 175 \itemize\ibull
 176 \:Je-li vrchol $t$ èervený a jeho otec je také èervený, pak øekneme, ¾e $t$ je porucha. Je-li $t$ porucha,
 177 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$:
 178 \figure{02.eps}{obr. 2}{1.5in}
 179 \algo
 180 \:$s$ je èervený. Pak pouze pøebarvíme $o$, $d$ a $s$ podle obrázku 3.
 181 Nyní $d$ mù¾e být porucha, ov¹em posunutá o 2 hladiny vý¹e.
 182 \figure{03.eps}{obr. 3}{3.5in}
 183 Pro splnìní poslední podmínky je je je¹tì nutné pøebarvit koøen $d$ na èerno.
 184
 185 \:$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.
 186 (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:
 187 \figure{04.eps}{obr. 4}{4in}
 188 (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.
 189 \figure{05.eps}{obr. 5}{4in}
 190 \endalgo
 191 \endlist
 192
 193
 194
 195 \bye