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 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 Je¹tì ale potøebujeme dokázat, ¾e ani k~nové kostøe nemohou existovat lehké hrany,
  78 co¾ pøi libovolné volbì~$e'$ nemusí být pravda. Proto si ze~v¹ech mo¾ných hran~$e'$
  79 vybereme tu s~nejmen¹í vahou. Uva¾me nyní hranu~$f$ nele¾ící v~nové kostøe~$\check{T}$.
  80 Cesta $\check{T}[f]$ pokrytá touto hranou je buïto pùvodní $T[f]$ (to pokud $e\not\in T[f]$)
  81 nebo $T[f] \symdiff C$, kde $C$ je kru¾nice $T[e']+e$. První pøípad je triviální,
  82 ve~druhém staèí zkontrolovat, ¾e $w(f)\ge w(e')$, jeliko¾ $e'$ je nejtì¾¹í hrana na~$C$.
  83
  84 Pokud je $f\in T'$, je to pravda, jeliko¾ jsme si $e'$ vybrali jako nejlehèí.
  85 Pokud $f\not\in T'$, nemù¾e být vzhledem k~$T'$ lehká a $T'[f]$ obsahuje alespoò
  86 jednu hranu~$g'$, která není v~$T$, tak¾e $w(f)\ge w(g')\ge w(e')$.
  87 \qed
  88
  89 \s{Dùkaz vìty:}
  90 \itemize\ibull
  91 \:$\Rightarrow$ Chceme dokázat, ¾e $\exists$ lehká hrana $\Rightarrow$ $T$ není minimální.
  92
  93 Nech» $\exists e$ lehká. Najdeme $e' \in T[e] : w(e) < w(e')$ (ta musí existovat z def. lehké hrany).
  94 Kostra $T' := \<swap>(T,e,e')$ je lehèí ne¾~$T$.
  95
  96 \medskip
  97
  98 \:$\Leftarrow$ Pokud k~$T$ neexistuje lehká hrana, je $T$ minimální.
  99
 100 Uva¾me minimální kostru $T_{min}$. Podle právì dokázané implikace k~ní neexistují lehké hrany,
 101 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})$.
 102
 103 \endlist
 104 \qed
 105
 106 \s{Vìta:}
 107 Jsou-li v¹echny váhy hran navzájem rùzné, je MST urèena jednoznaènì.
 108
 109 \s{Dùkaz:}
 110 Máme-li dvì MST $T_1$ a $T_2$, neobsahují podle pøedchozí vìty lehké hrany, tak¾e podle monotónního
 111 lemmatu mezi nimi lze pøeswapovat bez poklesu váhy. Pokud jsou ale váhy rùzné, musí ka¾dé swapnutí
 112 ostøe zvý¹it váhu, a~proto k~¾ádnému nemohlo dojít.
 113 \qed
 114
 115 \s{Poznámka:} Èasto se nám bude hodit, aby kostra, kterou hledáme, byla urèena jednoznaènì.
 116 Tehdy mù¾eme vyu¾ít pøedchozí vìty a váhy zmìnit o~vhodné epsilony, respektive kvaziuspoøádání
 117 roz¹íøit na~lineární uspoøádání.
 118
 119 \h{Èervenomodrý meta-algoritmus}
 120
 121 \s{Meta-algoritmus:} (pøedpokládáme, ¾e v¹echny váhy jsou rùzné)
 122
 123 \algo
 124 \:na poèátku v¹echny hrany bezbarvé
 125 \:dokud lze opakujeme: zvol modré nebo èervené pravidlo, proveï pravidlo
 126 \endalgo
 127 \itemize\ibull %%% pravidla
 128 \:Modré pravidlo
 129
 130 vezmìme øez v G takový, ¾e jeho nejlehèí hrana není modrá (prevence zacyklení) a obarvíme ji modøe
 131
 132 \:Èervené pravidlo
 133
 134 vezmìme kru¾nici v G takovou, ¾e její nejtì¾¹í hrana není èervená (prevence zacyklení) a obarvíme ji èervenì
 135
 136 \endlist %%%pravidla
 137
 138 \s{Vìta:}
 139 Pro Èervenomodrý meta-algoritmus platí:
 140 \algo
 141 \:zastaví se
 142 \:po zastavení jsou v¹echny hrany obarvené
 143 \:modøe obarvené hrany tvoøí kostru
 144 \endalgo
 145
 146
 147 \s{Lemma 1:} Modrá hrana $\in$ MST.
 148
 149 \s{Dùkaz:} Minimální kostra $T_{min}$ je urèena jednoznaènì (váhy jsou rùzné).
 150 Mìjme øez $C$ a minimální kostru $T_{min}$. Podle modrého pravidla je hrana $e = (x,y)$ nejlehèí v øezu $C$.
 151 Pokud $\exists e' \ne e \in C \cap T_{min}[x,y]$ (tj. jiná hrana z øezu $C$ patøí do min. kostry) mù¾eme provést $swap(e',e)$.
 152 Hrana $e$ byla nejlehèí, tak¾e $w(e) < w(e')$. Tím jsme si sní¾ili váhu kostry a $T_{min}$ nemohla být minimální $\Rightarrow$ spor.
 153 \qed
 154
 155 \centerline{\epsfysize=3cm\epsfbox{02.eps}}
 156
 157
 158 \s{Lemma 2:} Èervená hrana $\notin$ MST.
 159
 160 \s{Dùkaz:} Sporem: Pøedpokládejme, ¾e máme kru¾nici a na ní èervenou hranu $e = (x,y) \in T_{min}$.
 161 Odebráním èervené hrany se nam $T_min$ rozpadne na dvì komponenty $T_x$ a $T_y$.
 162 Nìkteré vrcholy z kru¾nice pøipadnou do komponenty $T_x$ a ostatní do $T_y$.
 163 Lze jednodu¹e nahlédnout, ¾e musí existovat hrana $e' = (x',y')$ taková,
 164 ¾e $x' \in T_x$ a $y' \in T_y$. Hrana $e$ byla nejtì¾¹í na kruønici, tak¾e $w(e') < w(e)$.
 165 Z toho vyplývá, ¾e provedením $swap(e,e')$ na $T_{min}$ dostaneme lehèí kostru a $T_{min}$ tedy není minimální $\Rightarrow$ spor.
 166 \qed
 167
 168 \centerline{\epsfysize=4cm\epsfbox{03.eps}}
 169
 170 \s{Lemma 3:} Po zastavení jsou v¹echny hrany obarvené.
 171
 172 \s{Dùkaz:} Opìt sporem: Nech» existuje hrana $e = (x,y)$, která je stále bezbarvá. Oznaèíme si mno¾inu vrcholù
 173 $M_x := \{v \in V \vert \exists$ modrá cesta x $\to$ v $\}$. Nyní mohou nastat dvì mo¾nosti:
 174
 175 \itemize\ibull
 176 \:$y \in M_x$ (tj. modrá cesta vede z $x$ a¾ do $y$)
 177
 178 Modrá cesta je v minimální kostøe a minimální kostra nemá ¾ádné lehké hrany $\Rightarrow$ hrana $e$ je tì¾ká a mù¾u na ní pou¾ít èervené pravidlo.
 179
 180 \centerline{\epsfysize=3cm\epsfbox{04.eps}}
 181
 182 \:$y \notin M_x$
 183
 184 V tom pøípadì existuje øez $\delta(M_x)$, takový, ¾e hrana $e$ patøí do øezu a zároveò $\delta(M_x)$ neobsahuje modré hrany
 185 $\Rightarrow$ mù¾u pou¾ít modré pravidlo.
 186
 187 \centerline{\epsfysize=3cm\epsfbox{05.eps}}
 188
 189 \endlist
 190
 191 \algo
 192
 193 \s{Dùkaz vìty:}
 194 \:zastaví se
 195
 196 V algoritmu nikdy nepøebarvujeme a v ka¾dém kroku obarvíme právì jednu hranu (a» u¾ èerveným, nebo modrým pravidlem).
 197 Máme koneèný poèet hran $\Rightarrow$ koneèný poèet krokù.
 198
 199 \:po zastavení jsou v¹echny hrany obarvené
 200 viz. lemma 3
 201
 202 \:modøe obarvené hrany tvoøí kostru
 203
 204 Lemma 1 a 2 øíká, ¾e modré hrany le¾í na kostøe a èervené naopak le¾í mimo kostru. Dále pak z lemmatu 3 víme, ¾e v¹echny hrany jsou obarvené.
 205 Právì v¹echny modré hrany tvoøí kostru.
 206
 207 \endalgo
 208
 209 \qed
 210
 211 \s{Poznámka:}
 212 Dualita èerveného a modrého pravidla.
 213
 214 Mezi èervenými a modrými hranami existuje dualita obdobnì jako u rovinných grafù existuje stìnovì-vrcholová dualita nebo jako existuje dualita u grafových matroidù.
 215 Pro ka¾dý grafový matroid $\exists$ duální matroid. Kostry $\leftrightarrow$ cykly, kostra $\leftrightarrow$ komplement kostry duálního grafu.
 216
 217 \h{Klasické algoritmy na hledání MST}
 218
 219 \s{Kruskalùv:} (hladový algoritmus).
 220
 221 \itemize\ibull
 222 \:setøídíme hrany podle vah (i zde nám staèí uspoøádání na hranách), kostra je na zaèátku prázdná (ka¾dý vrchol je v samostatné komponentì souvislosti)
 223 \:bereme hrany ve vzestupném poøadí
 224 \:pro ka¾dou hranu $e$ se podíváme jaké komponenty spojuje - spojuje-li rùzné komponenty, zaøadím hranu do stromu a obì komponenty slouèíme, jinak hranu zahodíme
 225 \endlist
 226
 227 Z hlediska na¹eho Èervenomodrého meta-algoritmu se lze na Kruskala dívat tak, ¾e si pìstujeme modrý les, a pokud hrana spojuje dva stromeèky, omodøím ji a
 228 nechám stromeèky srùst. Naopak spojuje-li hrana $e = (x,y)$ stejné komponenty, znamená to, ¾e mezi $x$ a $y$ vede modrá cesta $T[x,y]$ a $e$ tedy uzavírá cyklus
 229 na kterém jsou v¹echny hrany modré. Díky pøedchozímu uspoøádání víme, ¾e $e$ bude urèitì tì¾¹í, ne¾ v¹echny hrany na modré cestì a tak ji mù¾eme s klidným svìdomím
 230 obarvit na èerveno (tj. zahodit).
 231
 232 Tì¾i¹tì implementace Kruskala spoèívá v efektivním sluèování komponent (tzv. Union-find problem). Pøi efektivní implementaci lze dosáhnou èasové slo¾itosti
 233 $\O(m \log{n} + m \alpha(n))$
 234
 235 \s{Borùvkùv:}
 236
 237 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
 238 a v¹echny tyto nalezené hrany naráz pøidáme (aplikujeme nìkolik modrých pravidel najednou).
 239
 240 Poèet stromeèku klesá exponenciálnì $\Rightarrow$ ka¾dou komponentu (resp. její incidentní hrany) si mohu dovolit prohledávat lineárnì.
 241 Pokud na udr¾ování incidentních hran pou¾ijeme binomiální haldy, dostaneme èasouvou slo¾itost $\O(m \log{n})$. Vzhledem k povaze algoritmu pùjde ka¾dá
 242 fáze dobøe paralelizovat.
 243
 244 \s{Jarníkùv:}
 245
 246 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. To co se v Borùvkovi nazývalo celou fází,
 247 bude zde obyèejný krok. V ka¾dém kroku vyhledáme nejlevnìj¹í incidentní hranu a pøidáme ji do stromu. Kroky opakujeme, dokud se strom nerozroste pøes v¹echny vrcholy.
 248 Jarník se sice nedá rozumnì paralelizovat, av¹ak pøi ¹ikovné implementaci slibuje stejnou èasovou slo¾itost jako Borùvka ($\O(m \log{n})$).
 249
 250 \s{Poznámka:}
 251 pro celoèíselné váhy hran z rozsahu $\{1,\ldots k\}$, se umí algoritmus se slo¾itostí $\O(m k)$.
 252
 253 \bye