From 1659b8b5c93a65801157e4a869e2be53dfe8723f Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 16 Nov 2006 00:21:13 +0100 Subject: [PATCH] Kostry uvedeny na pravou miru. --- 5-mst/5-mst.tex | 151 ++++++++++++++++++++++++++---------------------- 1 file changed, 82 insertions(+), 69 deletions(-) diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index 15b00b1..5866a77 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -1,107 +1,120 @@ -%%%%%%%%%%%%%%%%%%%%%% -% 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} +\def\symdiff{\mathop{\Delta}} -\s{Definice:} -Kostru pro nesouvislý graf definujeme jako sjednocení koster komponent grafu. +\h{Minimální kostry a základní vìty okolo nich} -\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)}$. +\todo{Chybí zde obrázky, znaènì by hutný text projasnily.} -\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)(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 $\(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í \. \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} := \(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 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}:=\(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 -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' := \(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)$ \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} @@ -144,7 +157,7 @@ Hrana $e$ byla nejleh \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}$. +\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á, @@ -156,7 +169,7 @@ Z toho vypl \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ù +\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 -- 2.39.2