\input ../sgr.tex
\prednaska{5}{Minimální kostry}{zapsali Martin Kruli¹ \& Petr Su¹il }

\def\symdiff{\mathop{\Delta}}

\h{Minimální kostry a základní vìty okolo nich}

\todo{Chybí zde obrázky, znaènì by hutný text projasnily.}

\>V~této kapitole se budeme zabývat výhradnì neorientovanými grafy, jejich¾ hrany
budou ohodnoceny vahami $w: E \to {\bb R}$.

\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

\s{Poznámka:}
Toto je sice standardní definice MST, ale jinak je dosti ne¹ikovná, proto¾e vy¾aduje,
aby bylo váhy mo¾né sèítat. Za~chvíli si 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èí (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.

%\centerline{\epsfysize=3cm\epsfbox{01.eps}}

\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.

\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>.

\s{Dùkaz:}
Jeliko¾ $\vert T \vert = \vert T' \vert$, musí existovat $e' \in T'\setminus T$.
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í:}
Jsou-li $T$ a $T'$ kostry bez lehkých hran, pak lze od~$T$ k~$T'$ pøejít posloupností
swapù, pøi které váha kostry neklesá. (Od~$T'$ k~$T$ tedy také, tak¾e $w(T)=w(T')$.)

\s{Dùkaz:}
Podobnì jako u~pøedchozího lemmatu 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)$.

Je¹tì ale potøebujeme dokázat, ¾e ani k~nové kostøe nemohou existovat lehké hrany,
co¾ pøi libovolné volbì~$e'$ nemusí být pravda. Proto si ze~v¹ech mo¾ných hran~$e'$
vybereme tu s~nejmen¹í vahou. Uva¾me nyní hranu~$f$ nele¾ící v~nové kostøe~$\check{T}$.
Cesta $\check{T}[f]$ pokrytá touto hranou 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 staèí zkontrolovat, ¾e $w(f)\ge w(e')$, jeliko¾ $e'$ je nejtì¾¹í hrana na~$C$.

Pokud je $f\in T'$, je to pravda, jeliko¾ jsme si $e'$ vybrali jako nejlehèí.
Pokud $f\not\in T'$, nemù¾e být vzhledem k~$T'$ lehká a $T'[f]$ obsahuje alespoò
jednu hranu~$g'$, která není v~$T$, tak¾e $w(f)\ge w(g')\ge w(e')$.
\qed

\s{Dùkaz vìty:}
\itemize\ibull
\:$\Rightarrow$ Chceme dokázat, ¾e $\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 def. lehké hrany).
Kostra $T' := \<swap>(T,e,e')$ je lehèí ne¾~$T$.

\medskip

\:$\Leftarrow$ Pokud k~$T$ neexistuje lehká hrana, je $T$ minimální.

Uva¾me minimální kostru $T_{min}$. Podle právì dokázané implikace k~ní neexistují lehké hrany,
tak¾e mù¾eme pou¾ít monotónní swapovací lemma na~$T$ a $T_{min}$ a z~nìj plyne $w(T)=w(T_{min})$.

\endlist
\qed

\s{Vìta:}
Jsou-li v¹echny váhy hran navzájem rùzné, je MST urèena jednoznaènì.

\s{Dùkaz:}
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}

\s{Meta-algoritmus:} (pøedpokládáme, ¾e v¹echny váhy jsou rùzné)

\algo
\:na poèátku v¹echny hrany bezbarvé
\:dokud lze opakujeme: zvol modré nebo èervené pravidlo, proveï pravidlo
\endalgo
\itemize\ibull %%% pravidla
\:Modré pravidlo

vezmìme øez v G takový, ¾e jeho nejlehèí hrana není modrá (prevence zacyklení) a obarvíme ji modøe

\:Èervené pravidlo

vezmìme kru¾nici v G takovou, ¾e její nejtì¾¹í hrana není èervená (prevence zacyklení) a obarvíme ji èervenì

\endlist %%%pravidla

\s{Vìta:}
Pro Èervenomodrý meta-algoritmus platí:
\algo
\:zastaví se
\:po zastavení jsou v¹echny hrany obarvené
\:modøe obarvené hrany tvoøí kostru
\endalgo


\s{Lemma 1:} Modrá hrana $\in$ MST.

\s{Dùkaz:} Minimální kostra $T_{min}$ je urèena jednoznaènì (váhy jsou rùzné).
Mìjme øez $C$ a minimální kostru $T_{min}$. Podle modrého pravidla je hrana $e = (x,y)$ nejlehèí v øezu $C$.
Pokud $\exists e' \ne e \in C \cap T_{min}[x,y]$ (tj. jiná hrana z øezu $C$ patøí do min. kostry) mù¾eme provést $swap(e',e)$.
Hrana $e$ byla nejlehèí, tak¾e $w(e) < w(e')$. Tím jsme si sní¾ili váhu kostry a $T_{min}$ nemohla být minimální $\Rightarrow$ spor.
\qed

\centerline{\epsfysize=3cm\epsfbox{02.eps}}


\s{Lemma 2:} Èervená hrana $\notin$ MST.

\s{Dùkaz:} Sporem: Pøedpokládejme, ¾e máme kru¾nici a na ní èervenou hranu $e = (x,y) \in T_{min}$.
Odebráním èervené hrany se nam $T_min$ rozpadne na dvì komponenty $T_x$ a $T_y$.
Nìkteré vrcholy z kru¾nice pøipadnou do komponenty $T_x$ a ostatní do $T_y$.
Lze jednodu¹e nahlédnout, ¾e musí existovat hrana $e' = (x',y')$ taková,
¾e $x' \in T_x$ a $y' \in T_y$. Hrana $e$ byla nejtì¾¹í na kruønici, tak¾e $w(e') < w(e)$.
Z toho vyplývá, ¾e provedením $swap(e,e')$ na $T_{min}$ dostaneme lehèí kostru a $T_{min}$ tedy není minimální $\Rightarrow$ spor.
\qed

\centerline{\epsfysize=4cm\epsfbox{03.eps}}

\s{Lemma 3:} Po zastavení jsou v¹echny hrany obarvené.

\s{Dùkaz:} Opìt sporem: Nech» existuje hrana $e = (x,y)$, která je stále bezbarvá. Oznaèíme si mno¾inu vrcholù
$M_x := \{v \in V \vert \exists$ modrá cesta x $\to$ v $\}$. Nyní mohou nastat dvì mo¾nosti:

\itemize\ibull
\:$y \in M_x$ (tj. modrá cesta vede z $x$ a¾ do $y$)

Modrá cesta je v minimální kostøe a minimální kostra nemá ¾ádné lehké hrany $\Rightarrow$ hrana $e$ je tì¾ká a mù¾u na ní pou¾ít èervené pravidlo.

\centerline{\epsfysize=3cm\epsfbox{04.eps}}

\:$y \notin M_x$

V tom pøípadì existuje øez $\delta(M_x)$, takový, ¾e hrana $e$ patøí do øezu a zároveò $\delta(M_x)$ neobsahuje modré hrany
$\Rightarrow$ mù¾u pou¾ít modré pravidlo.

\centerline{\epsfysize=3cm\epsfbox{05.eps}}

\endlist

\algo

\s{Dùkaz vìty:}
\:zastaví se

V algoritmu nikdy nepøebarvujeme a v ka¾dém kroku obarvíme právì jednu hranu (a» u¾ èerveným, nebo modrým pravidlem).
Máme koneèný poèet hran $\Rightarrow$ koneèný poèet krokù.

\:po zastavení jsou v¹echny hrany obarvené
viz. lemma 3

\:modøe obarvené hrany tvoøí kostru

Lemma 1 a 2 øíká, ¾e modré hrany le¾í na kostøe a èervené naopak le¾í mimo kostru. Dále pak z lemmatu 3 víme, ¾e v¹echny hrany jsou obarvené.
Právì v¹echny modré hrany tvoøí kostru.

\endalgo

\qed

\s{Poznámka:}
Dualita èerveného a modrého pravidla.

Mezi èervenými a modrými hranami existuje dualita obdobnì jako u rovinných grafù existuje stìnovì-vrcholová dualita nebo jako existuje dualita u grafových matroidù.
Pro ka¾dý grafový matroid $\exists$ duální matroid. Kostry $\leftrightarrow$ cykly, kostra $\leftrightarrow$ komplement kostry duálního grafu.

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

\s{Kruskalùv:} (hladový algoritmus).

\itemize\ibull
\:setøídíme hrany podle vah (i zde nám staèí uspoøádání na hranách), kostra je na zaèátku prázdná (ka¾dý vrchol je v samostatné komponentì souvislosti)
\:bereme hrany ve vzestupném poøadí
\:pro ka¾dou hranu $e$ se podíváme jaké komponenty spojuje - spojuje-li rùzné komponenty, zaøadím hranu do stromu a obì komponenty slouèíme, jinak hranu zahodíme
\endlist

Z hlediska na¹eho Èervenomodrého meta-algoritmu se lze na Kruskala dívat tak, ¾e si pìstujeme modrý les, a pokud hrana spojuje dva stromeèky, omodøím ji a
nechám stromeèky srùst. Naopak spojuje-li hrana $e = (x,y)$ stejné komponenty, znamená to, ¾e mezi $x$ a $y$ vede modrá cesta $T[x,y]$ a $e$ tedy uzavírá cyklus
na kterém jsou v¹echny hrany modré. Díky pøedchozímu uspoøádání víme, ¾e $e$ bude urèitì tì¾¹í, ne¾ v¹echny hrany na modré cestì a tak ji mù¾eme s klidným svìdomím
obarvit na èerveno (tj. zahodit).

Tì¾i¹tì implementace Kruskala spoèívá v efektivním sluèování komponent (tzv. Union-find problem). Pøi efektivní implementaci lze dosáhnou èasové slo¾itosti
$\O(m \log{n} + m \alpha(n))$

\s{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).

Poèet stromeèku klesá exponenciálnì $\Rightarrow$ ka¾dou komponentu (resp. její incidentní hrany) si mohu dovolit prohledávat lineárnì.
Pokud na udr¾ování incidentních hran pou¾ijeme binomiální haldy, dostaneme èasouvou slo¾itost $\O(m \log{n})$. Vzhledem k povaze algoritmu pùjde ka¾dá
fáze dobøe paralelizovat.

\s{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. To co se v Borùvkovi nazývalo celou fází,
bude zde obyèejný krok. V ka¾dém kroku vyhledáme nejlevnìj¹í incidentní hranu a pøidáme ji do stromu. Kroky opakujeme, dokud se strom nerozroste pøes v¹echny vrcholy.
Jarník se sice nedá rozumnì paralelizovat, av¹ak pøi ¹ikovné implementaci slibuje stejnou èasovou slo¾itost jako Borùvka ($\O(m \log{n})$).

\s{Poznámka:}
pro celoèíselné váhy hran z rozsahu $\{1,\ldots k\}$, se umí algoritmus se slo¾itostí $\O(m k)$.

\bye
