X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=inline;f=5-mst%2F5-mst.tex;h=5357b7824828af17c22966d4b061dfcda17e4e73;hb=9d8d66dd6ecc97ef9051a0934be7e09b7526e733;hp=44a8e339bd6264ee4f3d89b6d88218a91bb58b2a;hpb=d81fc4332bc40324dbcbc8d6e1059632bde705c4;p=ga.git diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index 44a8e33..5357b78 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -1,15 +1,13 @@ \input ../sgr.tex \prednaska{5}{Minimální kostry}{} -\def\symdiff{\mathop{\Delta}} +\def\Tmin{T_{min}} \>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.} - \h{Minimální kostry a jejich vlastnosti} \s{Definice:} @@ -27,7 +25,7 @@ ka \endlist 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: @@ -38,14 +36,14 @@ Bu Ostatním hranám nele¾ícím v~kostøe budeme øíkat {\I tì¾ké.} \endlist +\figure{mst2.eps}{Kostra $T$, cesta $T[e]$ a výsledek operace $\(T,e,e')$}{\epsfxsize} + \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 $\(T,e,e^\prime) := T-e+e'$. @@ -58,13 +56,15 @@ a vynech Máme-li libovolné kostry $T$ a $T'$, pak lze z~$T$ dostat $T'$ koneèným poètem operací \. \proof -Jeliko¾ $\vert T \vert = \vert T' \vert$, musí existovat $e' \in T'\setminus T$. +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} := \(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 +\figure{mst1.eps}{Jeden krok dùkazu swapovacího lemmatu}{\epsfxsize} + \s{Monotónní lemma o~swapování:} 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á. @@ -86,17 +86,17 @@ ne \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' := \(T,e,e')$ je lehèí ne¾~$T$. \medskip -\:$\Leftarrow$ Pokud k~$T$ neexistuje lehká hrana, je $T$ minimální. +\:K~$T$ neexistuje lehká hrana $\Rightarrow$ $T$ je 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})$. +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 @@ -139,29 +139,31 @@ podle vah plat \: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$. -\proof 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 -$\(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í $\(\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$. \proof 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 $\(T_{min},e,e')$ nám dá~lehèí kostru, -co¾ je spor. +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í $\(\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. @@ -173,22 +175,19 @@ do~nich 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 \s{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 @@ -221,7 +220,7 @@ dob \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 +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. @@ -234,7 +233,7 @@ Mimo to lze ka 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)$.