\input ../sgr.tex
\prednaska{5}{Minimální kostry}{}
-\def\symdiff{\mathop{\Delta}}
+\def\Tmin{T_{min}}
-\h{Minimální kostry a základní vìty okolo nich}
+\>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}$.
-\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}$.
+\h{Minimální kostry a jejich vlastnosti}
\s{Definice:}
\itemize\ibull
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.
+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:
Ostatním hranám nele¾ícím v~kostøe budeme øíkat {\I tì¾ké.}
\endlist
-\s{Vìta:} (Tarjan \cite{tarjan:dsna}) Kostra~$T$ je minimální $\Leftrightarrow$ neexistuje hrana lehká vzhledem k~$T$.
+\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
+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.
-%\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'$.
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.eps}{Kostra $T$, cesta $T[e]$ a výsledek operace $\<swap>(T,e,e')$}{\epsfxsize}
+
+\figure{mst1.eps}{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>.
-\s{Dùkaz:}
-Jeliko¾ $\vert T \vert = \vert T' \vert$, musí existovat $e' \in T'\setminus T$.
+\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$.
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á.
-\s{Dùkaz:}
+\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)$,
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í,
+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
-\:$\Rightarrow$ Chceme dokázat, ¾e $\exists$ lehká hrana $\Rightarrow$ $T$ není minimální.
+\:$\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).
+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
-\:$\Leftarrow$ Pokud k~$T$ neexistuje lehká hrana, je $T$ minimální.
-
-Uva¾me nìjakou minimální kostru $T_{min}$ a pou¾ijme monotónní swapovací lemma na~$T$ a $T_{min}$. Z~nìj plyne $w(T)\le w(T_{min})$,
-a~tedy $w(T)=w(T_{min})$.
+\: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
-\qed
\s{Vìta:}
Jsou-li v¹echny váhy hran navzájem rùzné, je MST urèena jednoznaènì.
-\s{Dùkaz:}
+\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.
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:} (Tarjan \cite{tarjan:dsna})
+\s{Meta-algoritmus:}
\algo
\: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
+\::{\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
+\::{\I Èervené pravidlo:} Vyber cyklus takový, ¾e jeho nejtì¾¹í hrana není èervená, a obarvi ji na~èerveno.
\endalgo
\s{Vìta:}
\:Modøe obarvené hrany tvoøí minimální kostru.
\endalgo
-\s{Modré lemma:} Je-li hrana~$e$ kdykoliv algoritmem obarvena na~modro, pak $e\in T_{min}$.
+\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{Dùkaz:} Minimální kostra $T_{min}$ je urèena jednoznaènì (váhy jsou rùzné).
-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.
+\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
-\fig{02.eps}{3cm}
+\figure{mst-rb.eps}{Situace v~dùkazu Modrého a Èerveného lemmatu}{\epsfxsize}
-\s{Èervené lemma:} Je-li hrana~$e$ kdykoliv algoritmem obarvena na~èerveno, pak $e\not\in T_{min}$.
+\s{Èervené lemma:} Je-li libovolná hrana~$e$ algoritmem kdykoliv obarvena na~èerveno,
+pak $e\not\in \Tmin$.
-\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.
+\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
-\fig{03.eps}{4cm}
-
\s{Bezbarvé lemma:} Pokud existuje nìjaká neobarvená hrana, lze je¹tì pou¾ít nìkteré
z~pravidel.
-\s{Dùkaz:} Nech» existuje hrana~$e=xy$, která je stále bezbarvá. Oznaèíme si $M$ mno¾inu vrcholù,
+\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
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.
-\fig{04.eps}{3cm}
-
-\:$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.
-
-\fig{05.eps}{3cm}
+\figure{mst-bez.eps}{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
-\qed
-\s{Dùkaz vìty:}
+\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, pøibude ka¾dým krokem
- alespoò jedna obarvená hrana, tak¾e se algoritmus zastaví.
+\:{\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~$T_{min}$ právì modré hrany.
+\:{\I Najde modrou MST:} Podle èerveného a modrého lemmatu le¾í v~$\Tmin$ právì modré hrany.
+\qeditem
\endlist
-\qed
\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á
\h{Klasické algoritmy na hledání MST}
-\s{Kruskalùv neboli Hladový:\foot{\rm Mo¾ná hladový s~malým `h', ale tento algoritmus je pradìdeèkem
+\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
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
+(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:}
+\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
+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$ fází je celkem $\log n$. Pokud ka¾dou fázi
+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.
-\s{Jarníkùv:}
+\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 má èasovou slo¾itost $\O(m\log n)$, v~pøí¹tí kapitole uká¾eme implementaci je¹tì ¹ikovnìj¹í.
+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 algoritmus pro výpoèet MST v~grafech ohodnocených vahami $\{1,\ldots k\}$ se slo¾itostí $\O(mk)$.
+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
projects / ga.git / blobdiff