From cd19d3241b2cd1dc3355bbf5cab948e01018f410 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 16 Nov 2006 18:46:09 +0100 Subject: [PATCH] Hotova petka. --- 5-mst/5-mst.tex | 179 +++++++++++++++++++++++------------------------- 1 file changed, 86 insertions(+), 93 deletions(-) diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index 5866a77..8dd362f 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -69,21 +69,20 @@ Jsou-li $T$ a $T'$ kostry bez lehk swapù, pøi které váha kostry neklesá. (Od~$T'$ k~$T$ tedy také, tak¾e $w(T)=w(T')$.) \s{Dùkaz:} -Podobnì jako u~pøedchozího lemmatu indukcí podle $\vert T \symdiff T' \vert$. +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}:=\(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]$) +Aby mohla indukce pokraèovat, potøebujeme je¹tì dokázat, ¾e ani k~nové kostøe neexistují +lehké hrany v~$T'\setminus \check{T}$.\foot{Ony nebudou lehké ani ostatní hrany, ale to +pro indukci nepotøebujeme a museli bychom to dokazovat pracnìji.} 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í, -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')$. +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:} @@ -118,136 +117,130 @@ roz \h{Èervenomodrý meta-algoritmus} -\s{Meta-algoritmus:} (pøedpokládáme, ¾e v¹echny váhy jsou rùzné) +V¹echny tradièní algoritmy na~hledání MST lze popsat jako speciální pøípady následujícího +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:} \algo -\:na poèátku v¹echny hrany bezbarvé -\:dokud lze opakujeme: zvol modré nebo èervené pravidlo, proveï pravidlo +\: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 +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 \endalgo -\itemize\ibull %%% pravidla -\:Modré pravidlo - -vezmìme øez v G takový, ¾e jeho nejlehèí hrana není modrá (prevence zacyklení) a obarvíme ji modøe - -\:Èervené pravidlo - -vezmìme kru¾nici v G takovou, ¾e její nejtì¾¹í hrana není èervená (prevence zacyklení) a obarvíme ji èervenì - -\endlist %%%pravidla \s{Vìta:} -Pro Èervenomodrý meta-algoritmus platí: +Pro Èervenomodrý meta-algoritmus spu¹tìný na~libovolném grafu s~hranami lineárnì uspoøádanými +podle vah platí: \algo -\:zastaví se -\:po zastavení jsou v¹echny hrany obarvené -\:modøe obarvené hrany tvoøí kostru +\:V¾dy se zastaví. +\:Po zastavení jsou v¹echny hrany obarvené. +\:Modøe obarvené hrany tvoøí minimální kostru. \endalgo - -\s{Lemma 1:} Modrá hrana $\in$ MST. +\s{Modré lemma:} Je-li hrana~$e$ kdykoliv algoritmem obarvena na~modro, pak $e\in T_{min}$. \s{Dùkaz:} Minimální kostra $T_{min}$ je urèena jednoznaènì (váhy jsou rùzné). -Mìjme øez $C$ a minimální kostru $T_{min}$. Podle modrého pravidla je hrana $e = (x,y)$ nejlehèí v øezu $C$. -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)$. -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. +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. \qed \centerline{\epsfysize=3cm\epsfbox{02.eps}} +\s{Èervené lemma:} Je-li hrana~$e$ kdykoliv algoritmem obarvena na~èerveno, pak $e\not\in T_{min}$. -\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}$. -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á, -¾e $x' \in T_x$ a $y' \in T_y$. Hrana $e$ byla nejtì¾¹í na kruønici, tak¾e $w(e') < w(e)$. -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. +\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 $\(T_{min},e,e')$ nám dá~lehèí kostru, +co¾ je spor. \qed \centerline{\epsfysize=4cm\epsfbox{03.eps}} -\s{Lemma 3:} Po zastavení jsou v¹echny hrany obarvené. +\s{Bezbarvé lemma:} Pokud existuje nìjaká neobarvená hrana, lze je¹tì pou¾ít nìkteré +z~pravidel. -\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: +\s{Dùkaz:} 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 -\:$y \in M_x$ (tj. modrá cesta vede z $x$ a¾ do $y$) - -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. +\:$y \in M$ (tj. existuje modrá cesta z~$x$ do~$y$): Modrá cesta je v~minimální kostøe a k~minimální kostøe +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. \centerline{\epsfysize=3cm\epsfbox{04.eps}} -\:$y \notin M_x$ - -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 -$\Rightarrow$ mù¾u pou¾ít modré pravidlo. +\:$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. \centerline{\epsfysize=3cm\epsfbox{05.eps}} \endlist - -\algo +\qed \s{Dùkaz vìty:} -\:zastaví se - -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). -Máme koneèný poèet hran $\Rightarrow$ koneèný poèet krokù. - -\:po zastavení jsou v¹echny hrany obarvené -viz. lemma 3 - -\:modøe obarvené hrany tvoøí kostru - -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é. -Právì v¹echny modré hrany tvoøí kostru. - -\endalgo - +\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 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. +\endlist \qed \s{Poznámka:} -Dualita èerveného a modrého pravidla. - -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ù. -Pro ka¾dý grafový matroid $\exists$ duální matroid. Kostry $\leftrightarrow$ cykly, kostra $\leftrightarrow$ komplement kostry duálního grafu. +Èervené a modré pravidlo jsou v~jistém smyslu duální. Pro rovinné grafy je na~sebe pøevede obyèejná rovinná +dualita (staèí si uvìdomit, ¾e kostra duálního grafu je komplement duálu kostry primárního grafu), obecnìji +je to dualita mezi matroidy, která prohazuje øezy a cykly. \h{Klasické algoritmy na hledání MST} -\s{Kruskalùv:} (hladový algoritmus). +\s{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.}} -\itemize\ibull -\: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) -\:bereme hrany ve vzestupném poøadí -\: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 -\endlist +\algo +\:Setøídíme hrany podle vah vzestupnì. +\:Zaèneme s~prázdnou kostrou (ka¾dý vrchol je v~samostatné komponentì souvislosti). +\:Bereme hrany ve vzestupném poøadí. +\::Pro ka¾dou hranu $e$ se podíváme, zda spojuje dvì rùzné komponenty -- pokud ano, pøidáme ji do~kostry, + jinak ji zahodíme. +\endalgo -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 -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 -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 -obarvit na èerveno (tj. zahodit). +Èervenomodrý pohled: pìstujeme modrý les. Pokud hrana spojuje dva stromeèky, je~urèitì minimální v~øezu mezi +jedním ze~stromeèkù a zbytkem grafu (ostatní hrany tého¾ øezu jsme je¹tì nezpracovali). Pokud nespojuje, +je maximální na~nìjakém cyklu tvoøeném touto hranou a nìjakými døíve pøidanými. -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 -$\O(m \log{n} + m \alpha(n))$ +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 +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:} -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). +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$ ka¾dou komponentu (resp. její incidentní hrany) si mohu dovolit prohledávat lineárnì. -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á -fáze dobøe paralelizovat. +Poèet stromeèku 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:} -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í, -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. -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})$). +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¹í. -\s{Poznámka:} -pro celoèíselné váhy hran z rozsahu $\{1,\ldots k\}$, se umí algoritmus se slo¾itostí $\O(m k)$. +\s{Cvièení:} +Naleznìte algoritmus pro výpoèet MST v~grafech ohodnocených vahami $\{1,\ldots k\}$ se slo¾itostí $\O(mk)$. \bye -- 2.39.2