2 \prednaska{5}{Minimální kostry}{}
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}$.
11 \h{Minimální kostry a jejich vlastnosti}
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
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í.
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.
31 Buď $T \subseteq G$ nějaká kostra grafu~$G$. Pak:
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é.}
39 \s{Věta:} Kostra~$T$ je minimální $\Leftrightarrow$ neexistuje hrana lehká vzhledem k~$T$.
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.
45 \s{Definice:} Pro kostru~$T$ a hrany $e, e'$
46 zaveďme $\<swap>(T,e,e^\prime) := T-e+e'$.
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.
53 \figure{mst2.epdf}{Kostra $T$, cesta $T[e]$ a výsledek operace $\<swap>(T,e',e)$}{}
55 \figure{mst1.epdf}{Jeden krok důkazu swapovacího lemmatu}{}
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>.
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'$.
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á.
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)$.
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čí
89 \:$\exists$ lehká hrana $\Rightarrow$ $T$ není minimální.
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$.
96 \:K~$T$ neexistuje lehká hrana $\Rightarrow$ $T$ je minimální.
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)$.
104 Jsou-li všechny váhy hran navzájem různé, je MST určena jednoznačně.
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.
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í.
116 \h{Červenomodrý meta-algoritmus}
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é.
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.
134 Pro Červenomodrý meta-algoritmus spuštěný na~libovolném grafu s~hranami lineárně uspořádanými
138 \:Po zastavení jsou všechny hrany obarvené.
139 \:Modře obarvené hrany tvoří minimální kostru.
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$.
146 \s{Modré lemma:} Je-li libovolná hrana~$e$ algoritmem kdykoliv obarvena na~modro, pak $e\in \Tmin$.
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é.
154 \figure{mst-rb.epdf}{Situace v~důkazu Modrého a Červeného lemmatu}{}
156 \s{Červené lemma:} Je-li libovolná hrana~$e$ algoritmem kdykoliv obarvena na~červeno,
157 pak $e\not\in \Tmin$.
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.
167 \s{Bezbarvé lemma:} Pokud existuje nějaká neobarvená hrana, lze ještě použít některé
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:
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.
178 \figure{mst-bez.epdf}{Situace v~důkazu Bezbarvého lemmatu}{}
180 \:$y \notin M$: Tehdy řez $\delta(M)$ neobsahuje žádné modré hrany, takže na~tento řez
181 můžeme použít modré pravidlo.
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.
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.
199 \h{Klasické algoritmy na hledání MST}
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.}}
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,
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.
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))$.
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
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.
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ší.
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)$.