X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=5-mst%2F5-mst.tex;h=fc83c80cf974d53d5cb8176ce93c52e38ec407d2;hb=fa9f48fabb54016de6f8830bc4c9f0d8020c1c38;hp=b93fa4c682d870307f5ac59ddc3b8817c0f2abb2;hpb=25a443302cc80bd24f4571ab33fb5ad3633f12b9;p=ga.git diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index b93fa4c..fc83c80 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -25,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. Pojïme ukázat, ¾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: @@ -36,8 +36,6 @@ 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 @@ -52,19 +50,21 @@ Pokud $e^\prime \not\in T$ a $e\in T[e^\prime]$, je $\(T,e,e^\prime)$ op 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 $\(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í \. \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 +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á. @@ -79,7 +79,7 @@ Aby mohla indukce pokra 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 @@ -177,12 +177,12 @@ a mohu na ni pou \figure{mst-bez.eps}{Situace v~dùkazu Bezbarvého lemmatu}{\epsfxsize} -\:$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. +\:$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:} +\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. Ka¾dým krokem pøibude alespoò jedna obarvená hrana, tak¾e se algoritmus po~nejvý¹e $m$~krocích zastaví. @@ -198,7 +198,7 @@ je to dualita mezi matroidy, kter \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 @@ -214,21 +214,21 @@ jedn 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í \ a $n$ operací \. Nejlep¹í známá implementace +(Union-Find Problem), se~kterou provedeme $m$~operací \ a $n$ operací \. 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 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); @@ -236,7 +236,8 @@ hrany vedouc 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