\input ../sgr.tex
\prednaska{5}{Minimální kostry}{}

\def\Tmin{T_{min}}

\>Tato kapitola uvede problém minimální kostry, základní věty o~kostrách a klasické
algoritmy na~hledání minimálních koster. Budeme se inspirovat Tarjanovým přístupem
z~knihy~\cite{tarjan:dsna}. Všechny grafy v~této kapitole budou neorientované multigrafy
a jejich hrany budou ohodnoceny vahami $w: E \to {\bb R}$.

\h{Minimální kostry a jejich vlastnosti}

\s{Definice:}
\itemize\ibull
\:{\I Podgrafem} budeme v~této kapitole mínit libovolnou podmnožinu hran, vrcholy
vždy zůstanou zachovány.
\:{\I Přidání a odebrání hrany} budeme značit $T+e:=T\cup \{e\}$, $T-e:=T\setminus \{e\}$.
\:{\I Kostra} (Spanning Tree) souvislého grafu $G$ je libovolný jeho podgraf, který je strom.
Kostru nesouvislého grafu definujeme jako sjednocení koster jednotlivých komponent.
[Alternativně: kostra je minimální podgraf, který má komponenty s~týmiž vrcholy
jako komponenty~$G$.]
\:{\I Váha} podgrafu $F\subseteq E$ je $w(F) := \sum_{e\in F} w(e)$.
\:{\I Minimální kostra} (Minimum Spanning Tree, mezi přáteli též MST) budeme říkat
každé kostře, jejíž váha je mezi všemi kostrami daného grafu minimální.
\endlist

Toto je sice standardní definice MST, ale jinak je dosti nešikovná, protože vyžaduje,
aby bylo váhy možné sčítat. Ukážeme, že to není potřeba.

\s{Definice:}
Buď $T \subseteq G$ nějaká kostra grafu~$G$. Pak:
\itemize\ibull
\:$T[x,y]$ bude značit cestu v~$T$, která spojuje $x$ a $y$. (Cestou opět míníme množinu hran.)
\:$T[e]:=T[x,y]$ pro hranu $e=xy$. Této cestě budeme říkat {\I cesta pokrytá hranou~$e$.}
\:Hrana $e\in E \setminus T$ je {\I lehká vzhledem k~$T$} $\equiv \exists e^\prime \in T[e]: w(e)<w(e^\prime)$.
  Ostatním hranám neležícím v~kostře budeme říkat {\I těžké.}
\endlist

\s{Věta:} Kostra~$T$ je minimální $\Leftrightarrow$ neexistuje hrana lehká vzhledem k~$T$.

Tato věta nám dává pěknou alternativní definici MST, která místo sčítání vah váhy
pouze porovnává, čili jí místo čísel stačí lineární (kvazi)uspořádání na~hranách. Než se dostaneme
k~jejímu důkazu, prozkoumejme nejdříve, jak se dá mezi jednotlivými kostrami přecházet.

\s{Definice:} Pro kostru~$T$ a hrany $e, e'$
zaveďme $\<swap>(T,e,e^\prime) := T-e+e'$.

\s{Pozorování:}
Pokud $e^\prime \not\in T$ a $e\in T[e^\prime]$, je $\<swap>(T,e,e^\prime)$ opět kostra.
Stačí si uvědomit, že přidáním $e^\prime$ do~$T$ vznikne kružnice (konkrétně $T[e^\prime] + e^\prime$)
a vynecháním libovolné hrany z~této kružnice získáme opět kostru.

\figure{mst2.epdf}{Kostra $T$, cesta $T[e]$ a výsledek operace $\<swap>(T,e',e)$}{\epsfxsize}

\figure{mst1.epdf}{Jeden krok důkazu swapovacího lemmatu}{\epsfxsize}

\s{Lemma o~swapování:}
Máme-li libovolné kostry $T$ a $T'$, pak lze z~$T$ dostat $T'$ konečným počtem operací \<swap>.

\proof
Pokud $T \ne T'$, musí existovat hrana $e' \in T'\setminus T$, protože $\vert T \vert = \vert T' \vert$.
Kružnice $T[e']+e'$ nemůže být celá obsažena v~$T'$, takže existuje hrana
$e\in T[e']\setminus T'$ a $\check{T} := \<swap>(T,e,e')$ je kostra,
pro kterou $\vert \check{T} \symdiff T' \vert = \vert T \symdiff T' \vert -2$.
Po~konečném počtu těchto kroků tedy musíme dojít k~$T'$.
\qed

\s{Monotónní lemma o~swapování:}
Je-li $T$ kostra, k~níž neexistují žádné lehké hrany, a~$T'$ libovolná kostra,
pak lze od~$T$ k~$T'$ přejít posloupností swapů, při které váha kostry neklesá.

\proof
Podobně jako u~předchozího lemmatu budeme postupovat indukcí podle $\vert T \symdiff T' \vert$.
Pokud zvolíme libovolně hranu $e'\in T'\setminus T$ a k~ní $e\in T[e']\setminus T'$, musí
$\check{T}:=\<swap>(T,e,e')$ být kostra bližší k~$T'$ a $w(\check{T})\ge w(T)$,
jelikož $e'$ nemůže být lehká vzhledem k~$T$, takže speciálně $w(e')\ge w(e)$.

Aby mohla indukce pokračovat, potřebujeme ještě dokázat, že ani k~nové kostře neexistují
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.
Uvažme nyní hranu~$f\in T'\setminus \check{T}$.
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]$)
nebo $T[f] \symdiff C$, kde $C$ je kružnice $T[e']+e'$. První případ je triviální,
ve~druhém si stačí uvědomit, že $w(f)\ge w(e')$ a ostatní hrany na~$C$ jsou lehčí
než~$e'$.
\qed

\s{Důkaz věty:}
\itemize\ibull
\:$\exists$ lehká hrana $\Rightarrow$ $T$ není minimální.

Nechť $\exists e$ lehká. Najdeme $e' \in T[e] : w(e) < w(e')$ (ta musí existovat z~definice lehké hrany).
Kostra $T' := \<swap>(T,e,e')$ je lehčí než~$T$.

\medskip

\:K~$T$ neexistuje lehká hrana $\Rightarrow$ $T$ je minimální.

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)$,
a~tedy $w(T)=w(\Tmin)$.
\qeditem
\endlist

\s{Věta:}
Jsou-li všechny váhy hran navzájem různé, je MST určena jednoznačně.

\proof
Máme-li dvě MST $T_1$ a $T_2$, neobsahují podle předchozí věty lehké hrany, takže podle monotónního
lemmatu mezi nimi lze přeswapovat bez poklesu váhy. Pokud jsou ale váhy různé, musí každé swapnutí
ostře zvýšit váhu, a~proto k~žádnému nemohlo dojít.
\qed

\s{Poznámka:} Často se nám bude hodit, aby kostra, kterou hledáme, byla určena jednoznačně.
Tehdy můžeme využít předchozí věty a váhy změnit o~vhodné epsilony, respektive kvaziuspořádání
rozšířit na~lineární uspořádání.

\h{Červenomodrý meta-algoritmus}

Všechny tradiční algoritmy na~hledání MST lze popsat jako speciální případy následujícího
meta-algoritmu. Rozeberme si tedy rovnou ten. Formulujeme ho pro případ, kdy jsou všechny
váhy hran navzájem různé.

\s{Meta-algoritmus:}

\algo
\:Na počátku jsou všechny hrany bezbarvé.
\:Dokud to lze, použijeme jedno z~následujících pravidel:
\::{\I Modré pravidlo:} Vyber řez takový, že jeho nejlehčí hrana není modrá,\foot{Za
touto podmínkou nehledejte žádná kouzla, je tu pouze proto, aby se algoritmus nemohl
zacyklit neustálým prováděním pravidel, která nic nezmění.} a obarvi ji na~modro.
\::{\I Červené pravidlo:} Vyber cyklus takový, že jeho nejtěžší hrana není červená, a obarvi ji na~červeno.
\endalgo

\s{Věta:}
Pro Červenomodrý meta-algoritmus spuštěný na~libovolném grafu s~hranami lineárně uspořádanými
podle vah platí:
\algo
\:Vždy se zastaví.
\:Po zastavení jsou všechny hrany obarvené.
\:Modře obarvené hrany tvoří minimální kostru.
\endalgo

\proof
Nejdříve si dokážeme několik lemmat. Jelikož hrany mají navzájem různé váhy,
můžeme předpokládat, že algoritmus má sestrojit jednu konkrétní minimální kostru~$\Tmin$.

\s{Modré lemma:} Je-li libovolná hrana~$e$ algoritmem kdykoliv obarvena na~modro, pak $e\in \Tmin$.

\proof Sporem: Hrana~$e$ byla omodřena jako nejlehčí hrana nějakého řezu~$C$.
Pokud $e\not\in \Tmin$, musí cesta $\Tmin[e]$ obsahovat nějakou jinou
hranu~$e'$ řezu~$C$. Jenže $e'$ je těžší než~$e$, takže operací $\<swap>(\Tmin,e',e)$
získáme ještě lehčí kostru, což není možné.
\qed

\figure{mst-rb.epdf}{Situace v~důkazu Modrého a Červeného lemmatu}{\epsfxsize}

\s{Červené lemma:} Je-li libovolná hrana~$e$ algoritmem kdykoliv obarvena na~červeno,
pak $e\not\in \Tmin$.

\proof Opět sporem: Předpokládejme, že~$e$ byla obarvena červeně jako nejtěžší na~nějaké kružnici~$C$
a že $e\in \Tmin$. Odebráním~$e$ se nám $\Tmin$ rozpadne na~dvě komponenty $T_x$ a $T_y$.
Některé vrcholy kružnice připadnou do komponenty $T_x$, ostatní do~$T_y$. Na~$C$ ale musí
existovat nějaká hrana $e'\ne e$, jejíž krajní vrcholy leží v~různých komponentách,
a~jelikož hrana~$e$ byla na~kružnici nejtěžší, je $w(e') < w(e)$. Pomocí $\<swap>(\Tmin,e,e')$
proto získáme lehčí kostru, a~to je spor.
\qed

\s{Bezbarvé lemma:} Pokud existuje nějaká neobarvená hrana, lze ještě použít některé
z~pravidel.

\proof Nechť existuje hrana~$e=xy$, která je stále bezbarvá. Označíme si $M$ množinu vrcholů,
do~nichž se lze z~$x$ dostat po~modrých hranách. Nyní mohou nastat dvě možnosti:

\itemize\ibull
\:$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
neexistují žádné lehké hrany, takže hrana $e$ je nejdražší na~cyklu tvořeném modrou cestou a~touto hranou
a mohu na ni použít červené pravidlo.

\figure{mst-bez.epdf}{Situace v~důkazu Bezbarvého lemmatu}{\epsfxsize}

\:$y \notin M$: Tehdy řez $\delta(M)$ neobsahuje žádné modré hrany, takže na~tento řez
můžeme použít modré pravidlo.
\qeditem
\endlist

\ss{Důkaz věty:}
\itemize\ibull
\:{\I Zastaví se:} Z~červeného a modrého lemmatu plyne, že žádnou hranu nikdy nepřebarvíme. Každým krokem přibude
  alespoň jedna obarvená hrana, takže se algoritmus po~nejvýše $m$~krocích zastaví.
\:{\I Obarví vše:} Pokud existuje alespoň jedna neobarvená hrana, pak podle bezbarvého lemmatu algoritmus pokračuje.
\:{\I Najde modrou MST:} Podle červeného a modrého lemmatu leží v~$\Tmin$ právě modré hrany.
\qeditem
\endlist

\s{Poznámka:}
Červené a modré pravidlo jsou v~jistém smyslu duální. Pro rovinné grafy je na~sebe převede obyčejná rovinná
dualita (stačí si uvědomit, že kostra duálního grafu je komplement duálu kostry primárního grafu), obecněji
je to dualita mezi matroidy, která prohazuje řezy a cykly.

\h{Klasické algoritmy na hledání MST}

\ss{Kruskalův neboli Hladový:\foot{\rm Možná hladový s~malým `h', ale tento algoritmus je pradědečkem
všech ostatních hladových algoritmů, tak mu tu čest přejme.}}

\algo
\:Setřídíme hrany podle vah vzestupně.
\:Začneme s~prázdnou kostrou (každý vrchol je v~samostatné komponentě souvislosti).
\:Bereme hrany ve vzestupném pořadí.
\::Pro každou hranu $e$ se podíváme, zda spojuje dvě různé komponenty -- pokud ano, přidáme ji do~kostry,
   jinak ji zahodíme.
\endalgo

Červenomodrý pohled: pěstujeme modrý les. Pokud hrana spojuje dva stromečky, je~určitě minimální v~řezu mezi
jedním ze~stromečků a zbytkem grafu (ostatní hrany téhož řezu jsme ještě nezpracovali). Pokud nespojuje,
je maximální na~nějakém cyklu tvořeném touto hranou a nějakými dříve přidanými.

Potřebujeme čas $\O(m \log n)$ na~setřídění hran a dále datovou strukturu pro udržování komponent souvislosti
(Union-Find Problem), se~kterou provedeme $m$~operací \<Find> a $n$ operací \<Union>. Nejlepší známá implementace
této struktury dává složitost obou operací $\O(\alpha(n))$ amortizovaně, takže celkově hladový algoritmus
doběhne v~čase $\O(m \log n + m \alpha(n))$.

\ss{Borůvkův:}

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
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
tím nevznikne.

Počet stromečků klesá exponenciálně $\Rightarrow$ fází je celkem $\log n$. Pokud každou fázi
implementujeme lineárním průchodem celého grafu, dostaneme složitost $\O(m\log n)$.
Mimo to lze každou fázi výtečně paralelizovat.

\ss{Jarníkův:}

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
okamžiku nalezneme nejlevnější hranu vedoucí mezi stromem a zbytkem grafu a přidáme ji ke~stromu (modré pravidlo);
hrany vedoucí uvnitř stromu průběžně zahazujeme (červené pravidlo). Kroky opakujeme, dokud se strom nerozroste přes všechny vrcholy.
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ší.

\s{Cvičení:}
Nalezněte jednoduchý algoritmus pro výpočet MST v~grafech ohodnocených vahami $\{1,\ldots k\}$ se složitostí $\O(mk)$
nebo dokonce~$\O(m+nk)$.

\references
\bye
