]> mj.ucw.cz Git - ga.git/blob - 5-mst/5-mst.tex
Merge branch 'master' of git+ssh://git.ucw.cz/home/mj/GIT/ga
[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.epdf}{Kostra $T$, cesta $T[e]$ a výsledek operace $\<swap>(T,e',e)$}{}
54
55 \figure{mst1.epdf}{Jeden krok důkazu swapovacího lemmatu}{}
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.epdf}{Situace v~důkazu Modrého a Červeného lemmatu}{}
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.epdf}{Situace v~důkazu Bezbarvého lemmatu}{}
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ě, kde $\alpha$ je inverzní Ackermannova
219 funkce. Celkově tedy hladový algoritmus 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