-%%%%%%%%%%%%%%%%%%%%%%
-% lecture 04-04-2006 %
-%%%%%%%%%%%%%%%%%%%%%%
-
\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}
-\s{Definice:}
-Kostru pro nesouvislý graf definujeme jako sjednocení koster komponent grafu.
+\todo{Chybí zde obrázky, znaènì by hutný text projasnily.}
-\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í.
+\>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:}
-Minimální kostra (alias MST) je taková kostra $T$, která má $w(T)$ minimální.
+\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:}
-Taková definice MST je ne¹ikovná. Vy¾aduje toti¾ existenci sèítání, pøesto¾e postaèuje pouze lineární uspoøádání.
+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
+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')$.
+\:$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
-\centerline{\epsfysize=3cm\epsfbox{01.eps}}
+\s{Vìta:} Kostra~$T$ je minimální $\Leftrightarrow$ neexistuje hrana lehká vzhledem k~$T$.
-\:Hrana je {\I tì¾ká} $\equiv$ není lehká.
-\endlist
+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.
-\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]$.
+%\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í:}
-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.
+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:}
-Máme-li libovolné kostry $T$ a $T'$, pak lze z $T$ dostat $T'$ koneèným poètem operací $swap$.
+\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:}
-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]$).
+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{Vìta:}
-Kostra $T$ je minimální
-$\Leftrightarrow$ $\forall e \in E \setminus T$ je $e$ tì¾ká vzhledem k $T$.
+\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:}
-%%% proof start
-\itemize\ibull
-\:$\Rightarrow$ Sna¾íme se dokázat, ¾e $\exists$ lehká hrana $\Rightarrow$ není minimální.
+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}$.\foot{Ony nebudou lehké ani ostatní hrany, ale to
+pro indukci nepotøebujeme a museli bychom to dokazovat pracnìji.} 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
-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í.
+\s{Dùkaz vìty:}
+\itemize\ibull
+\:$\Rightarrow$ Chceme dokázat, ¾e $\exists$ lehká hrana $\Rightarrow$ $T$ není minimální.
-\bigskip
-\:$\Leftarrow$
+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$.
-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$.
+\medskip
-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)$.
+\:$\Leftarrow$ Pokud k~$T$ neexistuje lehká hrana, je $T$ minimální.
-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í.
+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{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{Vìta:}
+Jsou-li v¹echny váhy hran navzájem rùzné, je MST urèena jednoznaènì.
-\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í.
+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é)
+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 v¹echny hrany bezbarvé
-\:dokud lze opakujeme: zvol modré nebo èervené pravidlo, proveï pravidlo
+\:Na poèátku jsou v¹echny hrany bezbarvé.
+\:Dokud to lze, pou¾ijeme jedno z~následujících pravidel:
+\itemize\relax
+\:{\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.
+\endlist
\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í:
+Pro Èervenomodrý meta-algoritmus spu¹tìný na~libovolném grafu s~hranami lineárnì uspoøádanými
+podle vah platí:
\algo
-\:zastaví se
-\:po zastavení jsou v¹echny hrany obarvené
-\:modøe obarvené hrany tvoøí kostru
+\:V¾dy se zastaví.
+\:Po zastavení jsou v¹echny hrany obarvené.
+\:Modøe obarvené hrany tvoøí minimální kostru.
\endalgo
-
-\s{Lemma 1:} Modrá hrana $\in$ MST.
+\s{Modré lemma:} Je-li hrana~$e$ kdykoliv algoritmem obarvena na~modro, pak $e\in T_{min}$.
\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.
+Hrana~$e$ byla omodøena jako nejlehèí hrana nìjakého øezu~$C$.
+Pokud by existovala nìjaká jiná $e' \in C \cap T_{min}[e]$, mù¾eme provést
+$\<swap>(T_{min},e',e)$ a tím z~$T_{min}$ vytvoøit je¹tì lehèí kostru,
+co¾ je spor.
\qed
\centerline{\epsfysize=3cm\epsfbox{02.eps}}
+\s{Èervené lemma:} Je-li hrana~$e$ kdykoliv algoritmem obarvena na~èerveno, pak $e\not\in T_{min}$.
-\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.
+\s{Dùkaz:} Opìt sporem: Pøedpokládejme, ¾e~$e$ byla obarvena èervenì jako nejtì¾¹í na~nìjaké kru¾nici~$C$
+a ¾e $e\in T_{min}$. Odebráním~$e$ se nam $T_min$ rozpadne na dvì komponenty $T_x$ a $T_y$.
+Nìkteré vrcholy kru¾nice pøipadnou do komponenty $T_x$, ostatní do $T_y$.
+Lze jednodu¹e nahlédnout, ¾e musí existovat hrana $e'\ne e$ taková, ¾e $x' \in T_x$ a $y' \in T_y$.
+Hrana~$e$ byla nejtì¾¹í na~kru¾nici, tak¾e $w(e') < w(e)$ a $\<swap>(T_{min},e,e')$ nám dá~lehèí kostru,
+co¾ je spor.
\qed
\centerline{\epsfysize=4cm\epsfbox{03.eps}}
-\s{Lemma 3:} Po zastavení jsou v¹echny hrany obarvené.
+\s{Bezbarvé lemma:} Pokud existuje nìjaká neobarvená hrana, lze je¹tì pou¾ít nìkteré
+z~pravidel.
-\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:
+\s{Dùkaz:} 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_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.
+\:$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.
\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.
+\:$y \notin M$: Tehdy øez $\delta(M)$ neobsahuje ¾ádné modré hrany a alespoò jednu, která není
+èervená (konkrétnì hranu~$e$), tak¾e na~tento øez mù¾eme pou¾ít modré pravidlo.
\centerline{\epsfysize=3cm\epsfbox{05.eps}}
\endlist
-
-\algo
+\qed
\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
-
+\itemize\ibull
+\:{\I Zastaví se:} Z~èerveného a modrého lemmatu plyne, ¾e ¾ádnou hranu nikdy nepøebarvíme, pøibude ka¾dým krokem
+ alespoò jedna obarvená hrana, tak¾e se algoritmus 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~$T_{min}$ právì modré hrany.
+\endlist
\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.
+È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}
-\s{Kruskalùv:} (hladový algoritmus).
+\s{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.}}
-\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
+\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
-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).
+È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.
-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))$
+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))$.
\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).
+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è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.
+Poèet stromeèku 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.
\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})$).
+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 má èasovou slo¾itost $\O(m\log n)$, v~pøí¹tí kapitole uká¾eme implementaci je¹tì ¹ikovnìj¹í.
-\s{Poznámka:}
-pro celoèíselné váhy hran z rozsahu $\{1,\ldots k\}$, se umí algoritmus se slo¾itostí $\O(m k)$.
+\s{Cvièení:}
+Naleznìte algoritmus pro výpoèet MST v~grafech ohodnocených vahami $\{1,\ldots k\}$ se slo¾itostí $\O(mk)$.
\bye