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