5-mst/5-mst.tex

   1 %%%%%%%%%%%%%%%%%%%%%%
   2 % lecture 04-04-2006 %
   3 %%%%%%%%%%%%%%%%%%%%%%
   4
   5 \input ../sgr.tex
   6 \prednaska{5}{Minimální kostry}{zapsali Martin Kruli¹ \& Petr Su¹il }
   7
   8 \h{Minimální kostry a základní vìty okolo nich}
   9
  10 \s{Definice:}
  11 Kostru pro nesouvislý graf definujeme jako sjednocení koster komponent grafu.
  12
  13 \s{Definice:}
  14 Nech» $G$ je neorientovaný graf. Váhy (ohodnocení) hran budi¾ zobrazení $w : E \to R$. Pro podgraf $H \subseteq G$ definujeme váhu $w(H)=\sum_{e \in E} {w(e)}$.
  15
  16 \s{Poznámka:}
  17 V dal¹ím textu nebudeme rozli¹ovat mezi podgrafy a podmno¾inami hran. Pro na¹e úèely jde o toté¾. Kostry jednovrcholových komponent nám slo¾itost nepokazí.
  18
  19 \s{Definice:}
  20 Minimální kostra (alias MST) je taková kostra $T$, která má $w(T)$ minimální.
  21
  22 \s{Poznámka:}
  23 Taková definice MST je ne¹ikovná. Vy¾aduje toti¾ existenci sèítání, pøesto¾e postaèuje pouze lineární uspoøádání.
  24
  25 \s{Definice:}
  26 Buï $T \subseteq G$ nìjaká kostra grafu~$G$. Pak
  27 \itemize\ibull
  28 \:$T[x,y] := $ cesta mezi $x,y$, její¾ hrany le¾í v $T$
  29 \:Hrana $e=(x,y) \in E \setminus T$ je {\I lehká} vzhledem ke~kostøe $ \equiv \exists e' \in T[x,y]:w(e)<w(e')$.
  30
  31 \centerline{\epsfysize=3cm\epsfbox{01.eps}}
  32
  33 \:Hrana je {\I tì¾ká} $\equiv$ není lehká.
  34 \endlist
  35
  36 \s{Definice:} operace {\sl swap(e,e')}
  37 Nech» $T$ je kostra grafu, $e'=(x,y) \in E \setminus T$ a $T[x,y]$ je cesta mezi $x$ a $y$.
  38 Pro libovolnou hranu $e = (a,b) \in T[x,y]$ dostaneme provedením operace $swap(e,e')$ na $T$ kostru $T' = T \cup \{e'\} \setminus \{e\}$,
  39 pro kterou bude zároveò platit, ¾e $e' = (x,y) \in T'[a,b]$.
  40
  41 \s{Pozorování:}
  42 Mno¾ina hran $T'$, kterou jsme dostali z $T$ operací $swap(e,e')$, je opravdu kostra. $T'$ dostaneme tak, ¾e z $T$ sebereme hranu $e = (a,b)$
  43 a následnì pøidáme hranu $e' = (x,y)$. Sebráním $(a,b)$ se nám kostra rozpadne právì na dvì komponenty. Proto¾e ale hrana $(a,b)$ le¾ela na cestì
  44 mezi $x$ a $y$, budou tyto vrcholy le¾et v rùzných komponentách. Hrana $(x,y)$ pak tyto komponenty opìt spojí a výsledkem bude opìt kostra.
  45
  46 \s{Lemma:}
  47 Máme-li libovolné kostry $T$ a $T'$, pak lze z $T$ dostat $T'$ koneèným poètem operací $swap$.
  48
  49 \s{Dùkaz:}
  50 Oznaème si $D$ mno¾inu hran, které jsou v $T$ a nejsou v $T'$ ($D = T \setminus T'$) a $D'$ mno¾inu hran,
  51 které naopak jsou v $T'$ a nejsou v $T$ ($D' = T' \setminus T$). Lze jednodu¹e nahlédnout, ¾e $\vert D \vert = \vert D' \vert$,
  52 proto¾e i $\vert T \vert = \vert T' \vert$.
  53 Postupnì budeme generovat kostry $T_1$, $T_2$, ... a¾ vygenerujeme $T_n = T'$
  54 V ka¾ém kroku (swapu) odebereme z kostry $T_i$ nìjakou hranu z mno¾iny $D$ a nahradíme ji vhodnou hranou z $D'$ tak, aby $T_{i+1}$ byla opìt kostra.
  55 Pou¾ité hrany z $D$ a $D'$ samozøejmì vylouèíme. Mno¾iny $D$ a $D'$ jsou koneèné, tak¾e budeme potøebovat koneèný poèet swapù.
  56 Zbývá ukázat, ¾e pro libovolnou hranu z $D$ umíme najít hranu v $D'$.
  57 Vezmìme libovolnou hranu $e = (a,b) \in D$. $e$ nele¾í v $T'$, tak¾e $T'[a,b] \cup {e}$ tvoøí cyklus. Celý cyklus nemù¾e le¾et v kostøe a $e \in T$,
  58 tak¾e musí $\exists e' \in T[a,b]$, která zároveò $e' \notin T$ a tedy i $e' \in D'$. Tím jsem na¹el korespondující pár hran $e,e'$ z mno¾in $D,D'$,
  59 které zároveò splòují potøebné pøedpoklady pro swap ($e' \in T[a,b]$).
  60 \qed
  61
  62 \s{Vìta:}
  63 Kostra $T$ je minimální
  64 $\Leftrightarrow$ $\forall e \in E \setminus T$ je $e$ tì¾ká vzhledem k $T$.
  65
  66 \s{Dùkaz:}
  67 %%% proof start
  68 \itemize\ibull
  69 \:$\Rightarrow$ Sna¾íme se dokázat, ¾e $\exists$ lehká hrana $\Rightarrow$ není minimální.
  70
  71 Nech» $\exists e = (x,y)$ lehká. Najdeme $e' \in T[x,y] : w(e) < w(e')$ (ta musí existovat z def. lehké hrany).
  72 Na kostru $T$ provedeme operaci $swap(e,e')$ a dostanu novou kostru $T'$. Proto¾e $w(e) < w(e')$,
  73 musí být i $w(T') < w(T)$ a kostra $T$ tedy nebyla minimální.
  74
  75 \bigskip
  76 \:$\Leftarrow$
  77
  78 Mìjme kostru $T$ bez lehkých hran a minimální kostru $T_{min}$. Doká¾eme, ¾e lze z $T$ dostat $T_{min}$ opakovaným pou¾itím operace $swap$.
  79 Z dùsledku definice operace $swap$ víme, ¾e kostry lze mezi sebou libovolnì pøeswapovat. Zbývá nám dokázat, ¾e $w(T) = w(T_{min})$.
  80 Postupným swapováním budu dostávat vzájemnì rùzné kostry $T$, $T_1$, $T_2$, ... $T_{min}$ tak,
  81 ¾e ka¾dá následující kostra je výsledkem operace $swap$ na pøedchozí. Podíváme se nejprve na $T$ a $T_1$.
  82
  83 Nech» $T_1 = swap(e,e') T$ tj. $e = (a,b) \in T$ a $e' = (x,y) \in T_1$. Hrana $e'$ musí z definice swapu le¾et na $T[a,b]$.
  84 Ke kostøe $T$ neexistují ¾adné lehké hrany, tak¾e $\forall f \in T[a,b]$ je $w(f) \ge w(e)$ tedy i $w(e') \ge w(e)$ a $w(T) \le w(T_1)$.
  85
  86 Analogicky lze postupovat, a¾ dostaneme nerovnost $w(T) \le w(T_1) \le w(T_2) \le ... \le w(T_{min})$.
  87 $T_{min}$ je minimální kostra, tak¾e $w(T) = w(T_{min})$ a $T$ je tedy také minimální.
  88
  89 \endlist
  90 \qed
  91
  92 \s{Poznámka:}
  93 Ji¾ víme, ¾e pro definici minimální kostry nám staèí lineární uspoøádání.
  94 Pokud bude $\forall e,e':e \neq e' \Rightarrow w(e) \neq w(e')$, pak pro $T_1, T_2$ minimální kostry, $T_1$ mù¾u pøeswapovat na $T_2$, proto¾e jsou ale váhy rùzné $\#swapù = 0$.
  95
  96 \s{Poznámka:}
  97 Pokud dostaneme kvaziuspoøádání, mù¾eme douspoøádat ekvivalentní váhy napø. lexikograficky.
  98
  99 \s{Dùsledek:}
 100 Jsou-li v¹echny váhy rùzné, pak je MST urèen jednoznaènì. Tj.
 101 $\forall e_1,e_2 \in E(G)$ $w(e_1) \neq w(e_2)$ $\Rightarrow$ $\exists ! MST(G)$
 102 \s{Dùkaz:}
 103 mám MST $T_1$ a $T_2$ a zkusím mezi nimi pøeswapovat. Pøi pøeswapovávání se ale zmìní váhy, nebo» v¹echny váhy jsou rùzné. Tedy jedna z koster nemù¾e být minimální.
 104
 105
 106 \h{Èervenomodrý meta-algoritmus}
 107
 108 \s{Meta-algoritmus:} (pøedpokládáme, ¾e v¹echny váhy jsou rùzné)
 109
 110 \algo
 111 \:na poèátku v¹echny hrany bezbarvé
 112 \:dokud lze opakujeme: zvol modré nebo èervené pravidlo, proveï pravidlo
 113 \endalgo
 114 \itemize\ibull %%% pravidla
 115 \:Modré pravidlo
 116
 117 vezmìme øez v G takový, ¾e jeho nejlehèí hrana není modrá (prevence zacyklení) a obarvíme ji modøe
 118
 119 \:Èervené pravidlo
 120
 121 vezmìme kru¾nici v G takovou, ¾e její nejtì¾¹í hrana není èervená (prevence zacyklení) a obarvíme ji èervenì
 122
 123 \endlist %%%pravidla
 124
 125 \s{Vìta:}
 126 Pro Èervenomodrý meta-algoritmus platí:
 127 \algo
 128 \:zastaví se
 129 \:po zastavení jsou v¹echny hrany obarvené
 130 \:modøe obarvené hrany tvoøí kostru
 131 \endalgo
 132
 133
 134 \s{Lemma 1:} Modrá hrana $\in$ MST.
 135
 136 \s{Dùkaz:} Minimální kostra $T_{min}$ je urèena jednoznaènì (váhy jsou rùzné).
 137 Mìjme øez $C$ a minimální kostru $T_{min}$. Podle modrého pravidla je hrana $e = (x,y)$ nejlehèí v øezu $C$.
 138 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)$.
 139 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.
 140 \qed
 141
 142 \centerline{\epsfysize=3cm\epsfbox{02.eps}}
 143
 144
 145 \s{Lemma 2:} Èervená hrana $\notin$ MST.
 146
 147 \s{Dùkaz:} Sporem: Pøedpokládejme, ¾e máme kru¾nici a na ní èervenou hranu $e = (x,y) \in T_{min}$.
 148 Odebráním èervené hrany se nam $T_min$ rozpadne na dvì komponenty $T_x$ a $T_y$.
 149 Nìkteré vrcholy z kru¾nice pøipadnou do komponenty $T_x$ a ostatní do $T_y$.
 150 Lze jednodu¹e nahlédnout, ¾e musí existovat hrana $e' = (x',y')$ taková,
 151 ¾e $x' \in T_x$ a $y' \in T_y$. Hrana $e$ byla nejtì¾¹í na kruønici, tak¾e $w(e') < w(e)$.
 152 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.
 153 \qed
 154
 155 \centerline{\epsfysize=4cm\epsfbox{03.eps}}
 156
 157 \s{Lemma 3:} Po zastavení jsou v¹echny hrany obarvené.
 158
 159 \s{Dùkaz:} Opìt sporem: Nech» existuje hrana $e = (x,y)$, která je stále bezbarvá. Oznaèíme si mno¾inu vrcholù
 160 $M_x := \{v \in V \vert \exists$ modrá cesta x $\to$ v $\}$. Nyní mohou nastat dvì mo¾nosti:
 161
 162 \itemize\ibull
 163 \:$y \in M_x$ (tj. modrá cesta vede z $x$ a¾ do $y$)
 164
 165 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.
 166
 167 \centerline{\epsfysize=3cm\epsfbox{04.eps}}
 168
 169 \:$y \notin M_x$
 170
 171 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
 172 $\Rightarrow$ mù¾u pou¾ít modré pravidlo.
 173
 174 \centerline{\epsfysize=3cm\epsfbox{05.eps}}
 175
 176 \endlist
 177
 178 \algo
 179
 180 \s{Dùkaz vìty:}
 181 \:zastaví se
 182
 183 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).
 184 Máme koneèný poèet hran $\Rightarrow$ koneèný poèet krokù.
 185
 186 \:po zastavení jsou v¹echny hrany obarvené
 187 viz. lemma 3
 188
 189 \:modøe obarvené hrany tvoøí kostru
 190
 191 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é.
 192 Právì v¹echny modré hrany tvoøí kostru.
 193
 194 \endalgo
 195
 196 \qed
 197
 198 \s{Poznámka:}
 199 Dualita èerveného a modrého pravidla.
 200
 201 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ù.
 202 Pro ka¾dý grafový matroid $\exists$ duální matroid. Kostry $\leftrightarrow$ cykly, kostra $\leftrightarrow$ komplement kostry duálního grafu.
 203
 204 \h{Klasické algoritmy na hledání MST}
 205
 206 \s{Kruskalùv:} (hladový algoritmus).
 207
 208 \itemize\ibull
 209 \: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)
 210 \:bereme hrany ve vzestupném poøadí
 211 \: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
 212 \endlist
 213
 214 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
 215 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
 216 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
 217 obarvit na èerveno (tj. zahodit).
 218
 219 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
 220 $\O(m \log{n} + m \alpha(n))$
 221
 222 \s{Borùvkùv:}
 223
 224 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
 225 a v¹echny tyto nalezené hrany naráz pøidáme (aplikujeme nìkolik modrých pravidel najednou).
 226
 227 Poèet stromeèku klesá exponenciálnì $\Rightarrow$ ka¾dou komponentu (resp. její incidentní hrany) si mohu dovolit prohledávat lineárnì.
 228 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á
 229 fáze dobøe paralelizovat.
 230
 231 \s{Jarníkùv:}
 232
 233 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í,
 234 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.
 235 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})$).
 236
 237 \s{Poznámka:}
 238 pro celoèíselné váhy hran z rozsahu $\{1,\ldots k\}$, se umí algoritmus se slo¾itostí $\O(m k)$.
 239
 240 \bye