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