5-mst/5-mst.tex

   1 \input ../sgr.tex
   2 \prednaska{5}{Minimální kostry}{zapsali Martin Kruli¹ \& Petr Su¹il }
   3
   4 \def\symdiff{\mathop{\Delta}}
   5
   6 \h{Minimální kostry a základní vìty okolo nich}
   7
   8 \todo{Chybí zde obrázky, znaènì by hutný text projasnily.}
   9
  10 \>V~této kapitole se budeme zabývat výhradnì neorientovanými grafy, jejich¾ hrany
  11 budou ohodnoceny vahami $w: E \to {\bb R}$.
  12
  13 \s{Definice:}
  14 \itemize\ibull
  15 \:{\I Podgrafem} budeme v~této kapitole mínit libovolnou podmno¾inu hran, vrcholy
  16 v¾dy zùstanou zachovány.
  17 \:{\I Pøidání a odebrání hrany} budeme znaèit $T+e:=T\cup \{e\}$, $T-e:=T\setminus \{e\}$.
  18 \:{\I Kostra} (Spanning Tree) souvislého grafu $G$ je libovolný jeho podgraf, který je strom.
  19 Kostru nesouvislého grafu definujeme jako sjednocení koster jednotlivých komponent.
  20 [Alternativnì: kostra je minimální podgraf, který má komponenty s~tými¾ vrcholy
  21 jako komponenty~$G$.]
  22 \:{\I Váha} podgrafu $F\subseteq E$ je $w(F) := \sum_{e\in F} w(e)$.
  23 \:{\I Minimální kostra} (Minimum Spanning Tree, mezi pøáteli té¾ MST) budeme øíkat
  24 ka¾dé kostøe, její¾ váha je mezi v¹emi kostrami daného grafu minimální.
  25 \endlist
  26
  27 \s{Poznámka:}
  28 Toto je sice standardní definice MST, ale jinak je dosti ne¹ikovná, proto¾e vy¾aduje,
  29 aby bylo váhy mo¾né sèítat. Za~chvíli si uká¾eme, ¾e to není potøeba.
  30
  31 \s{Definice:}
  32 Buï $T \subseteq G$ nìjaká kostra grafu~$G$. Pak:
  33 \itemize\ibull
  34 \:$T[x,y]$ bude znaèit cestu v~$T$, která spojuje $x$ a $y$. (Cestou opìt míníme mno¾inu hran.)
  35 \:$T[e]:=T[x,y]$ pro hranu $e=xy$. Této cestì budeme øíkat {\I cesta pokrytá hranou~$e$.}
  36 \:Hrana $e\in E \setminus T$ je {\I lehká vzhledem k~$T$} $\equiv \exists e^\prime \in T[e]: w(e)<w(e^\prime)$.
  37   Ostatním hranám nele¾ícím v~kostøe budeme øíkat {\I tì¾ké.}
  38 \endlist
  39
  40 \s{Vìta:} Kostra~$T$ je minimální $\Leftrightarrow$ neexistuje hrana lehká vzhledem k~$T$.
  41
  42 Tato vìta nám dává pìknou alternativní definici MST, která místo sèítání vah váhy
  43 pouze porovnává, èili jí místo èísel staèí (kvazi)uspoøádání na~hranách. Ne¾ se dostaneme
  44 k~jejímu dùkazu, prozkoumejme nejdøíve, jak se dá mezi jednotlivými kostrami pøecházet.
  45
  46 %\centerline{\epsfysize=3cm\epsfbox{01.eps}}
  47
  48 \s{Definice:} Pro kostru~$T$ a hrany $e, e'$
  49 zaveïme $\<swap>(T,e,e^\prime) := T-e+e'$.
  50
  51 \s{Pozorování:}
  52 Pokud $e^\prime \not\in T$ a $e\in T[e^\prime]$, je $\<swap>(T,e,e^\prime)$ opìt kostra.
  53 Staèí si uvìdomit, ¾e pøidáním $e^\prime$ do~$T$ vznikne kru¾nice (konkrétnì $T[e^\prime] + e^\prime$)
  54 a vynecháním libovolné hrany z~této kru¾nice získáme opìt kostru.
  55
  56 \s{Lemma o~swapování:}
  57 Máme-li libovolné kostry $T$ a $T'$, pak lze z~$T$ dostat $T'$ koneèným poètem operací \<swap>.
  58
  59 \s{Dùkaz:}
  60 Jeliko¾ $\vert T \vert = \vert T' \vert$, musí existovat $e' \in T'\setminus T$.
  61 Kru¾nice $T[e']+e'$ nemù¾e být celá obsa¾ena v~$T$, tak¾e existuje hrana
  62 $e\in T[e']\setminus T'$ a $\check{T} := \<swap>(T,e,e')$ je kostra,
  63 pro kterou $\vert \check{T} \symdiff T' \vert = \vert T \symdiff T' \vert -2$.
  64 Po~koneèném poètu tìchto krokù tedy musíme dojít k~$T'$.
  65 \qed
  66
  67 \s{Monotónní lemma o~swapování:}
  68 Jsou-li $T$ a $T'$ kostry bez lehkých hran, pak lze od~$T$ k~$T'$ pøejít posloupností
  69 swapù, pøi které váha kostry neklesá. (Od~$T'$ k~$T$ tedy také, tak¾e $w(T)=w(T')$.)
  70
  71 \s{Dùkaz:}
  72 Podobnì jako u~pøedchozího lemmatu budeme postupovat indukcí podle $\vert T \symdiff T' \vert$.
  73 Pokud zvolíme libovolnì hranu $e'\in T'\setminus T$ a k~ní $e\in T[e]\setminus T'$, musí
  74 $\check{T}:=\<swap>(T,e,e')$ být kostra bli¾¹í k~$T'$ a $w(\check{T})\ge w(T)$,
  75 jeliko¾ $e'$ nemù¾e být lehká vzhledem k~$T$, tak¾e speciálnì $w(e')\ge w(e)$.
  76
  77 Aby mohla indukce pokraèovat, potøebujeme je¹tì dokázat, ¾e ani k~nové kostøe neexistují
  78 lehké hrany  v~$T'\setminus \check{T}$.\foot{Ony nebudou lehké ani ostatní hrany, ale to
  79 pro indukci nepotøebujeme a museli bychom to dokazovat pracnìji.} K~tomu nám pomù¾e
  80 zvolit si ze~v¹ech mo¾ných hran~$e'$ tu s~nejmen¹í vahou.
  81 Uva¾me nyní hranu~$f\in T'\setminus \check{T}$.
  82 Cesta $\check{T}[f]$ pokrytá touto hranou v~nové kostøe je buïto pùvodní $T[f]$ (to pokud $e\not\in T[f]$)
  83 nebo $T[f] \symdiff C$, kde $C$ je kru¾nice $T[e']+e$. První pøípad je triviální,
  84 ve~druhém si staèí uvìdomit, ¾e $w(f)\ge w(e')$ a ostatní hrany na~$C$ jsou lehèí
  85 ne¾~$e'$.
  86 \qed
  87
  88 \s{Dùkaz vìty:}
  89 \itemize\ibull
  90 \:$\Rightarrow$ Chceme dokázat, ¾e $\exists$ lehká hrana $\Rightarrow$ $T$ není minimální.
  91
  92 Nech» $\exists e$ lehká. Najdeme $e' \in T[e] : w(e) < w(e')$ (ta musí existovat z def. lehké hrany).
  93 Kostra $T' := \<swap>(T,e,e')$ je lehèí ne¾~$T$.
  94
  95 \medskip
  96
  97 \:$\Leftarrow$ Pokud k~$T$ neexistuje lehká hrana, je $T$ minimální.
  98
  99 Uva¾me minimální kostru $T_{min}$. Podle právì dokázané implikace k~ní neexistují lehké hrany,
 100 tak¾e mù¾eme pou¾ít monotónní swapovací lemma na~$T$ a $T_{min}$ a z~nìj plyne $w(T)=w(T_{min})$.
 101
 102 \endlist
 103 \qed
 104
 105 \s{Vìta:}
 106 Jsou-li v¹echny váhy hran navzájem rùzné, je MST urèena jednoznaènì.
 107
 108 \s{Dùkaz:}
 109 Máme-li dvì MST $T_1$ a $T_2$, neobsahují podle pøedchozí vìty lehké hrany, tak¾e podle monotónního
 110 lemmatu mezi nimi lze pøeswapovat bez poklesu váhy. Pokud jsou ale váhy rùzné, musí ka¾dé swapnutí
 111 ostøe zvý¹it váhu, a~proto k~¾ádnému nemohlo dojít.
 112 \qed
 113
 114 \s{Poznámka:} Èasto se nám bude hodit, aby kostra, kterou hledáme, byla urèena jednoznaènì.
 115 Tehdy mù¾eme vyu¾ít pøedchozí vìty a váhy zmìnit o~vhodné epsilony, respektive kvaziuspoøádání
 116 roz¹íøit na~lineární uspoøádání.
 117
 118 \h{Èervenomodrý meta-algoritmus}
 119
 120 V¹echny tradièní algoritmy na~hledání MST lze popsat jako speciální pøípady následujícího
 121 meta-algoritmu. Rozeberme si tedy rovnou ten. Formulujeme ho pro pøípad, kdy jsou v¹echny
 122 váhy hran navzájem rùzné.
 123
 124 \s{Meta-algoritmus:}
 125
 126 \algo
 127 \:Na poèátku jsou v¹echny hrany bezbarvé.
 128 \:Dokud to lze, pou¾ijeme jedno z~následujících pravidel:
 129 \itemize\relax
 130 \:{\I Modré pravidlo:} Vyber øez takový, ¾e jeho nejlehèí hrana není modrá,\foot{Za
 131 touto podmínkou nehledejte ¾ádná kouzla, je tu pouze proto, aby se algoritmus nemohl
 132 zacyklit neustálým provádìním pravidel, která nic nezmìní.} a obarvi ji na~modro.
 133 \:{\I Èervené pravidlo:} Vyber cyklus takový, ¾e jeho nejtì¾¹í hrana není èervená, a obarvi ji na~èerveno.
 134 \endlist
 135 \endalgo
 136
 137 \s{Vìta:}
 138 Pro Èervenomodrý meta-algoritmus spu¹tìný na~libovolném grafu s~hranami lineárnì uspoøádanými
 139 podle vah platí:
 140 \algo
 141 \:V¾dy se zastaví.
 142 \:Po zastavení jsou v¹echny hrany obarvené.
 143 \:Modøe obarvené hrany tvoøí minimální kostru.
 144 \endalgo
 145
 146 \s{Modré lemma:} Je-li hrana~$e$ kdykoliv algoritmem obarvena na~modro, pak $e\in T_{min}$.
 147
 148 \s{Dùkaz:} Minimální kostra $T_{min}$ je urèena jednoznaènì (váhy jsou rùzné).
 149 Hrana~$e$ byla omodøena jako nejlehèí hrana nìjakého øezu~$C$.
 150 Pokud by existovala nìjaká jiná $e' \in C \cap T_{min}[e]$, mù¾eme provést
 151 $\<swap>(T_{min},e',e)$ a tím z~$T_{min}$ vytvoøit je¹tì lehèí kostru,
 152 co¾ je spor.
 153 \qed
 154
 155 \centerline{\epsfysize=3cm\epsfbox{02.eps}}
 156
 157 \s{Èervené lemma:} Je-li hrana~$e$ kdykoliv algoritmem obarvena na~èerveno, pak $e\not\in T_{min}$.
 158
 159 \s{Dùkaz:} Opìt sporem: Pøedpokládejme, ¾e~$e$ byla obarvena èervenì jako nejtì¾¹í na~nìjaké kru¾nici~$C$
 160 a ¾e $e\in T_{min}$. Odebráním~$e$ se nam $T_min$ rozpadne na dvì komponenty $T_x$ a $T_y$.
 161 Nìkteré vrcholy kru¾nice pøipadnou do komponenty $T_x$, ostatní do $T_y$.
 162 Lze jednodu¹e nahlédnout, ¾e musí existovat hrana $e'\ne e$ taková, ¾e $x' \in T_x$ a $y' \in T_y$.
 163 Hrana~$e$ byla nejtì¾¹í na~kru¾nici, tak¾e $w(e') < w(e)$ a $\<swap>(T_{min},e,e')$ nám dá~lehèí kostru,
 164 co¾ je spor.
 165 \qed
 166
 167 \centerline{\epsfysize=4cm\epsfbox{03.eps}}
 168
 169 \s{Bezbarvé lemma:} Pokud existuje nìjaká neobarvená hrana, lze je¹tì pou¾ít nìkteré
 170 z~pravidel.
 171
 172 \s{Dùkaz:} Nech» existuje hrana~$e=xy$, která je stále bezbarvá. Oznaèíme si $M$ mno¾inu vrcholù,
 173 do~nich¾ se lze z~$x$ dostat po~modrých hranách. Nyní mohou nastat dvì mo¾nosti:
 174
 175 \itemize\ibull
 176 \:$y \in M$ (tj. existuje modrá cesta z~$x$ do~$y$): Modrá cesta je v~minimální kostøe a k~minimální kostøe
 177 neexistují ¾ádné lehké hrany, tak¾e hrana $e$ je nejdra¾¹í na~cyklu tvoøeném modrou cestou a~touto hranou
 178 a mohu na ni pou¾ít èervené pravidlo.
 179
 180 \centerline{\epsfysize=3cm\epsfbox{04.eps}}
 181
 182 \:$y \notin M$: Tehdy øez $\delta(M)$ neobsahuje ¾ádné modré hrany a alespoò jednu, která není
 183 èervená (konkrétnì hranu~$e$), tak¾e na~tento øez mù¾eme pou¾ít modré pravidlo.
 184
 185 \centerline{\epsfysize=3cm\epsfbox{05.eps}}
 186
 187 \endlist
 188 \qed
 189
 190 \s{Dùkaz vìty:}
 191 \itemize\ibull
 192 \:{\I Zastaví se:} Z~èerveného a modrého lemmatu plyne, ¾e ¾ádnou hranu nikdy nepøebarvíme, pøibude ka¾dým krokem
 193   alespoò jedna obarvená hrana, tak¾e se algoritmus zastaví.
 194 \:{\I Obarví v¹e:} Pokud existuje alespoò jedna neobarvená hrana, pak podle bezbarvého lemmatu algoritmus pokraèuje.
 195 \:{\I Najde modrou MST:} Podle èerveného a modrého lemmatu le¾í v~$T_{min}$ právì modré hrany.
 196 \endlist
 197 \qed
 198
 199 \s{Poznámka:}
 200 Èervené a modré pravidlo jsou v~jistém smyslu duální. Pro rovinné grafy je na~sebe pøevede obyèejná rovinná
 201 dualita (staèí si uvìdomit, ¾e kostra duálního grafu je komplement duálu kostry primárního grafu), obecnìji
 202 je to dualita mezi matroidy, která prohazuje øezy a cykly.
 203
 204 \h{Klasické algoritmy na hledání MST}
 205
 206 \s{Kruskalùv neboli Hladový:\foot{\rm Mo¾ná hladový s~malým `h', ale tento algoritmus je pradìdeèkem
 207 v¹ech ostatních hladových algoritmù, tak mu tu èest pøejme.}}
 208
 209 \algo
 210 \:Setøídíme hrany podle vah vzestupnì.
 211 \:Zaèneme s~prázdnou kostrou (ka¾dý vrchol je v~samostatné komponentì souvislosti).
 212 \:Bereme hrany ve vzestupném poøadí.
 213 \::Pro ka¾dou hranu $e$ se podíváme, zda spojuje dvì rùzné komponenty -- pokud ano, pøidáme ji do~kostry,
 214    jinak ji zahodíme.
 215 \endalgo
 216
 217 Èervenomodrý pohled: pìstujeme modrý les. Pokud hrana spojuje dva stromeèky, je~urèitì minimální v~øezu mezi
 218 jedním ze~stromeèkù a zbytkem grafu (ostatní hrany tého¾ øezu jsme je¹tì nezpracovali). Pokud nespojuje,
 219 je maximální na~nìjakém cyklu tvoøeném touto hranou a nìjakými døíve pøidanými.
 220
 221 Potøebujeme èas $\O(m \log n)$ na~setøídìní hran a dále datovou strukturu pro udr¾ování komponent souvislosti
 222 (Union-Find Problem), se~kterou provedeme $m$ operací \<Find> a $n$ operací \<Union>. Nejlep¹í známá implementace
 223 této struktury dává slo¾itost obou operací $\O(\alpha(n))$ amortizovanì, tak¾e celkovì hladový algoritmus
 224 dobìhne v~èase $\O(m \log n + m \alpha(n))$.
 225
 226 \s{Borùvkùv:}
 227
 228 Opìt si budeme pìstovat modrý les, av¹ak tentokrát jej budeme roz¹iøovat ve fázích. V~jedné fázi nalezneme ke ka¾dému stromeèku nejlevnìj¹í incidentní hranu
 229 a v¹echny tyto nalezené hrany naráz pøidáme (aplikujeme nìkolik modrých pravidel najednou). Pokud jsou v¹echny váhy rùzné, cyklus
 230 tím nevznikne.
 231
 232 Poèet stromeèku klesá exponenciálnì $\Rightarrow$ fází je celkem $\log n$. Pokud ka¾dou fázi
 233 implementujeme lineárním prùchodem celého grafu, dostaneme slo¾itost $\O(m\log n)$.
 234 Mimo to lze ka¾dou fázi výteènì paralelizovat.
 235
 236 \s{Jarníkùv:}
 237
 238 Jarníkùv algoritmus je podobný Borùvkovi, ale s tím rozdílem, ¾e nenecháme rùst celý les, ale jen jeden modrý strom. V~ka¾dém
 239 okam¾iku nalezneme nejlevnìj¹í hranu vedoucí mezi stromem a zbytkem grafu a pøidáme ji ke~stromu (modré pravidlo);
 240 hrany vedoucí uvnitø stromu prùbì¾nì zahazujeme (èervené pravidlo). Kroky opakujeme, dokud se strom nerozroste pøes v¹echny vrcholy.
 241 Pøi ¹ikovné implementaci pomocí haldy má èasovou slo¾itost $\O(m\log n)$, v~pøí¹tí kapitole uká¾eme implementaci je¹tì ¹ikovnìj¹í.
 242
 243 \s{Cvièení:}
 244 Naleznìte algoritmus pro výpoèet MST v~grafech ohodnocených vahami $\{1,\ldots k\}$ se slo¾itostí $\O(mk)$.
 245
 246 \bye