6 \prednaska{5}{Minimální kostry}{zapsali Martin Kruli¹ \& Petr Su¹il }
8 \h{Minimální kostry a základní vìty okolo nich}
11 Kostru pro nesouvislý graf definujeme jako sjednocení koster komponent grafu.
14 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)}$.
17 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í.
20 Minimální kostra (alias MST) je taková kostra $T$, která má $w(T)$ minimální.
23 Taková definice MST je ne¹ikovná. Vy¾aduje toti¾ existenci sèítání, pøesto¾e postaèuje pouze lineární uspoøádání.
26 Buï $T \subseteq G$ nìjaká kostra grafu~$G$. Pak
28 \:$T[x,y] := $ cesta mezi $x,y$, její¾ hrany le¾í v $T$
29 \: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')$.
31 \centerline{\epsfysize=3cm\epsfbox{01.eps}}
33 \:Hrana je {\I tì¾ká} $\equiv$ není lehká.
36 \s{Definice:} operace {\sl swap(e,e')}
37 Nech» $T$ je kostra grafu, $e'=(x,y) \in E \setminus T$ a $T[x,y]$ je cesta mezi $x$ a $y$.
38 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\}$,
39 pro kterou bude zároveò platit, ¾e $e' = (x,y) \in T'[a,b]$.
42 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)$
43 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ì
44 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.
47 Máme-li libovolné kostry $T$ a $T'$, pak lze z $T$ dostat $T'$ koneèným poètem operací $swap$.
50 Oznaème si $D$ mno¾inu hran, které jsou v $T$ a nejsou v $T'$ ($D = T \setminus T'$) a $D'$ mno¾inu hran,
51 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$,
52 proto¾e i $\vert T \vert = \vert T' \vert$.
53 Postupnì budeme generovat kostry $T_1$, $T_2$, ... a¾ vygenerujeme $T_n = T'$
54 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.
55 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ù.
56 Zbývá ukázat, ¾e pro libovolnou hranu z $D$ umíme najít hranu v $D'$.
57 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$,
58 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'$,
59 které zároveò splòují potøebné pøedpoklady pro swap ($e' \in T[a,b]$).
63 Kostra $T$ je minimální
64 $\Leftrightarrow$ $\forall e \in E \setminus T$ je $e$ tì¾ká vzhledem k $T$.
69 \:$\Rightarrow$ Sna¾íme se dokázat, ¾e $\exists$ lehká hrana $\Rightarrow$ není minimální.
71 Nech» $\exists e = (x,y)$ lehká. Najdeme $e' \in T[x,y] : w(e) < w(e')$ (ta musí existovat z def. lehké hrany).
72 Na kostru $T$ provedeme operaci $swap(e,e')$ a dostanu novou kostru $T'$. Proto¾e $w(e) < w(e')$,
73 musí být i $w(T') < w(T)$ a kostra $T$ tedy nebyla minimální.
78 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$.
79 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})$.
80 Postupným swapováním budu dostávat vzájemnì rùzné kostry $T$, $T_1$, $T_2$, ... $T_{min}$ tak,
81 ¾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$.
83 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]$.
84 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)$.
86 Analogicky lze postupovat, a¾ dostaneme nerovnost $w(T) \le w(T_1) \le w(T_2) \le ... \le w(T_{min})$.
87 $T_{min}$ je minimální kostra, tak¾e $w(T) = w(T_{min})$ a $T$ je tedy také minimální.
93 Ji¾ víme, ¾e pro definici minimální kostry nám staèí lineární uspoøádání.
94 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$.
97 Pokud dostaneme kvaziuspoøádání, mù¾eme douspoøádat ekvivalentní váhy napø. lexikograficky.
100 Jsou-li v¹echny váhy rùzné, pak je MST urèen jednoznaènì. Tj.
101 $\forall e_1,e_2 \in E(G)$ $w(e_1) \neq w(e_2)$ $\Rightarrow$ $\exists ! MST(G)$
104 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í.
107 \h{Èervenomodrý meta-algoritmus}
109 \s{Meta-algoritmus:} (pøedpokládáme, ¾e v¹echny váhy jsou rùzné)
112 \:na poèátku v¹echny hrany bezbarvé
113 \:dokud lze opakujeme: zvol modré nebo èervené pravidlo, proveï pravidlo
115 \itemize\ibull %%% pravidla
118 vezmìme øez v G takový, ¾e jeho nejlehèí hrana není modrá (prevence zacyklení) a obarvíme ji modøe
122 vezmìme kru¾nici v G takovou, ¾e její nejtì¾¹í hrana není èervená (prevence zacyklení) a obarvíme ji èervenì
127 Pro Èervenomodrý meta-algoritmus platí:
130 \:po zastavení jsou v¹echny hrany obarvené
131 \:modøe obarvené hrany tvoøí kostru
135 \s{Lemma 1:} Modrá hrana $\in$ MST.
137 \s{Dùkaz:} Minimální kostra $T_{min}$ je urèena jednoznaènì (váhy jsou rùzné).
138 Mìjme øez $C$ a minimální kostru $T_{min}$. Podle modrého pravidla je hrana $e = (x,y)$ nejlehèí v øezu $C$.
139 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)$.
140 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.
143 \centerline{\epsfysize=3cm\epsfbox{02.eps}}
146 \s{Lemma 2:} Èervená hrana $\notin$ MST.
148 \s{Dùkaz:} Sporem: Pøedpokládejme, ¾e máme kru¾nici a na ní èervenou hranu $e = (x,y) \in T_{min}$.
149 Odebráním èervené hrany se nam $T_min$ rozpadne na dvì komponenty $T_x$ a $T_y$.
150 Nìkteré vrcholy z kru¾nice pøipadnou do komponenty $T_x$ a ostatní do $T_y$.
151 Lze jednodu¹e nahlédnout, ¾e musí existovat hrana $e' = (x',y')$ taková,
152 ¾e $x' \in T_x$ a $y' \in T_y$. Hrana $e$ byla nejtì¾¹í na kruønici, tak¾e $w(e') < w(e)$.
153 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.
156 \centerline{\epsfysize=4cm\epsfbox{03.eps}}
158 \s{Lemma 3:} Po zastavení jsou v¹echny hrany obarvené.
160 \s{Dùkaz:} Opìt sporem: Nech» existuje hrana $e = (x,y)$, která je stále bezbarvá. Oznaèíme si mno¾inu vrcholù
161 $M_x := \{v \in V \vert \exists$ modrá cesta x $\to$ v $\}$. Nyní mohou nastat dvì mo¾nosti:
164 \:$y \in M_x$ (tj. modrá cesta vede z $x$ a¾ do $y$)
166 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.
168 \centerline{\epsfysize=3cm\epsfbox{04.eps}}
172 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
173 $\Rightarrow$ mù¾u pou¾ít modré pravidlo.
175 \centerline{\epsfysize=3cm\epsfbox{05.eps}}
184 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).
185 Máme koneèný poèet hran $\Rightarrow$ koneèný poèet krokù.
187 \:po zastavení jsou v¹echny hrany obarvené
190 \:modøe obarvené hrany tvoøí kostru
192 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é.
193 Právì v¹echny modré hrany tvoøí kostru.
200 Dualita èerveného a modrého pravidla.
202 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ù.
203 Pro ka¾dý grafový matroid $\exists$ duální matroid. Kostry $\leftrightarrow$ cykly, kostra $\leftrightarrow$ komplement kostry duálního grafu.
205 \h{Klasické algoritmy na hledání MST}
207 \s{Kruskalùv:} (hladový algoritmus).
210 \: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)
211 \:bereme hrany ve vzestupném poøadí
212 \: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
215 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
216 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
217 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
218 obarvit na èerveno (tj. zahodit).
220 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
221 $\O(m \log{n} + m \alpha(n))$
225 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
226 a v¹echny tyto nalezené hrany naráz pøidáme (aplikujeme nìkolik modrých pravidel najednou).
228 Poèet stromeèku klesá exponenciálnì $\Rightarrow$ ka¾dou komponentu (resp. její incidentní hrany) si mohu dovolit prohledávat lineárnì.
229 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á
230 fáze dobøe paralelizovat.
234 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í,
235 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.
236 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})$).
239 pro celoèíselné váhy hran z rozsahu $\{1,\ldots k\}$, se umí algoritmus se slo¾itostí $\O(m k)$.