%%%%%%%%%%%%%%%%%%%%%%
% lecture 04-04-2006 %
%%%%%%%%%%%%%%%%%%%%%%

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

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

\s{Definice:}
Kostru pro nesouvislý graf definujeme jako sjednocení koster komponent grafu.

\s{Definice:}
Nech» $G$ je neorientovaný graf. Váhy (ohodnocení) hran budi¾ zobrazení $w : E \to R$. Pro podgraf $H \subseteq G$ definujeme váhu $w(H)=\sum_{e \in E} {w(e)}$.

\s{Poznámka:}
V dal¹ím textu nebudeme rozli¹ovat mezi podgrafy a podmno¾inami hran. Pro na¹e úèely jde o toté¾. Kostry jednovrcholových komponent nám slo¾itost nepokazí.

\s{Definice:}
Minimální kostra (alias MST) je taková kostra $T$, která má $w(T)$ minimální.

\s{Poznámka:}
Taková definice MST je ne¹ikovná. Vy¾aduje toti¾ existenci sèítání, pøesto¾e postaèuje pouze lineární uspoøádání.

\s{Definice:}
Buï $T \subseteq G$ nìjaká kostra grafu~$G$. Pak 
\itemize\ibull
\:$T[x,y] := $ cesta mezi $x,y$, její¾ hrany le¾í v $T$
\:Hrana $e=(x,y) \in E \setminus T$ je {\I lehká} vzhledem ke~kostøe $ \equiv \exists e' \in T[x,y]:w(e)<w(e')$.

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

\:Hrana je {\I tì¾ká} $\equiv$ není lehká.
\endlist

\s{Definice:} operace {\sl swap(e,e')}
Nech» $T$ je kostra grafu, $e'=(x,y) \in E \setminus T$ a $T[x,y]$ je cesta mezi $x$ a $y$.
Pro libovolnou hranu $e = (a,b) \in T[x,y]$ dostaneme provedením operace $swap(e,e')$ na $T$ kostru $T' = T \cup \{e'\} \setminus \{e\}$,
pro kterou bude zároveò platit, ¾e $e' = (x,y) \in T'[a,b]$.

\s{Pozorování:}
Mno¾ina hran $T'$, kterou jsme dostali z $T$ operací $swap(e,e')$, je opravdu kostra. $T'$ dostaneme tak, ¾e z $T$ sebereme hranu $e = (a,b)$
a následnì pøidáme hranu $e' = (x,y)$. Sebráním $(a,b)$ se nám kostra rozpadne právì na dvì komponenty. Proto¾e ale hrana $(a,b)$ le¾ela na cestì
mezi $x$ a $y$, budou tyto vrcholy le¾et v rùzných komponentách. Hrana $(x,y)$ pak tyto komponenty opìt spojí a výsledkem bude opìt kostra.

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

\s{Dùkaz:}
Oznaème si $D$ mno¾inu hran, které jsou v $T$ a nejsou v $T'$ ($D = T \setminus T'$) a $D'$ mno¾inu hran,
které naopak jsou v $T'$ a nejsou v $T$ ($D' = T' \setminus T$). Lze jednodu¹e nahlédnout, ¾e $\vert D \vert = \vert D' \vert$,
proto¾e i $\vert T \vert = \vert T' \vert$.
Postupnì budeme generovat kostry $T_1$, $T_2$, ... a¾ vygenerujeme $T_n = T'$
V ka¾ém kroku (swapu) odebereme z kostry $T_i$ nìjakou hranu z mno¾iny $D$ a nahradíme ji vhodnou hranou z $D'$ tak, aby $T_{i+1}$ byla opìt kostra.
Pou¾ité hrany z $D$ a $D'$ samozøejmì vylouèíme. Mno¾iny $D$ a $D'$ jsou koneèné, tak¾e budeme potøebovat koneèný poèet swapù.
Zbývá ukázat, ¾e pro libovolnou hranu z $D$ umíme najít hranu v $D'$.
Vezmìme libovolnou hranu $e = (a,b) \in D$. $e$ nele¾í v $T'$, tak¾e $T'[a,b] \cup {e}$ tvoøí cyklus. Celý cyklus nemù¾e le¾et v kostøe a $e \in T$,
tak¾e musí $\exists e' \in T[a,b]$, která zároveò $e' \notin T$ a tedy i $e' \in D'$. Tím jsem na¹el korespondující pár hran $e,e'$ z mno¾in $D,D'$,
které zároveò splòují potøebné pøedpoklady pro swap ($e' \in T[a,b]$).
\qed

\s{Vìta:}
Kostra $T$ je minimální 
$\Leftrightarrow$ $\forall e \in E \setminus T$ je $e$ tì¾ká vzhledem k $T$.

\s{Dùkaz:}
%%% proof start
\itemize\ibull
\:$\Rightarrow$ Sna¾íme se dokázat, ¾e $\exists$ lehká hrana $\Rightarrow$ není minimální.

Nech» $\exists e = (x,y)$ lehká. Najdeme $e' \in T[x,y] : w(e) < w(e')$ (ta musí existovat z def. lehké hrany).
Na kostru $T$ provedeme operaci $swap(e,e')$ a dostanu novou kostru $T'$. Proto¾e $w(e) < w(e')$, 
musí být i $w(T') < w(T)$ a kostra $T$ tedy nebyla minimální.

\bigskip
\:$\Leftarrow$

Mìjme kostru $T$ bez lehkých hran a minimální kostru $T_{min}$. Doká¾eme, ¾e lze z $T$ dostat $T_{min}$ opakovaným pou¾itím operace $swap$.
Z dùsledku definice operace $swap$ víme, ¾e kostry lze mezi sebou libovolnì pøeswapovat. Zbývá nám dokázat, ¾e $w(T) = w(T_{min})$.
Postupným swapováním budu dostávat vzájemnì rùzné kostry $T$, $T_1$, $T_2$, ... $T_{min}$ tak,
¾e ka¾dá následující kostra je výsledkem operace $swap$ na pøedchozí. Podíváme se nejprve na $T$ a $T_1$.

Nech» $T_1 = swap(e,e') T$ tj. $e = (a,b) \in T$ a $e' = (x,y) \in T_1$. Hrana $e'$ musí z definice swapu le¾et na $T[a,b]$.
Ke kostøe $T$ neexistují ¾adné lehké hrany, tak¾e $\forall f \in T[a,b]$ je $w(f) \ge w(e)$ tedy i $w(e') \ge w(e)$ a $w(T) \le w(T_1)$.

Analogicky lze postupovat, a¾ dostaneme nerovnost $w(T) \le w(T_1) \le w(T_2) \le ... \le w(T_{min})$.
$T_{min}$ je minimální kostra, tak¾e $w(T) = w(T_{min})$ a $T$ je tedy také minimální.

\endlist
\qed

\s{Poznámka:}
Ji¾ víme, ¾e pro definici minimální kostry nám staèí lineární uspoøádání.
Pokud bude $\forall e,e':e \neq e' \Rightarrow w(e) \neq w(e')$, pak pro $T_1, T_2$ minimální kostry, $T_1$ mù¾u pøeswapovat na $T_2$, proto¾e jsou ale váhy rùzné $\#swapù = 0$.

\s{Poznámka:}
Pokud dostaneme kvaziuspoøádání, mù¾eme douspoøádat ekvivalentní váhy napø. lexikograficky.

\s{Dùsledek:}
Jsou-li v¹echny váhy rùzné, pak je MST urèen jednoznaènì. Tj.
$\forall e_1,e_2 \in E(G)$ $w(e_1) \neq w(e_2)$ $\Rightarrow$ $\exists ! MST(G)$
\vfill\eject
\s{Dùkaz:}
mám MST $T_1$ a $T_2$ a zkusím mezi nimi pøeswapovat. Pøi pøeswapovávání se ale zmìní váhy, nebo» v¹echny váhy jsou rùzné. Tedy jedna z koster nemù¾e být minimální. 


\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
