X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=6-borjar%2F6-borjar.tex;h=1c4e63edb7580ed3bd6ec556934fc4158d72ed90;hb=83329800368162b7bfd7b921cda7039b0af41e5c;hp=ca7b4ee18844d77ad4f69c50ff1de90179bf3685;hpb=c6bb260798e74256edff74a536b5c24642243270;p=ga.git diff --git a/6-borjar/6-borjar.tex b/6-borjar/6-borjar.tex index ca7b4ee..1c4e63e 100644 --- a/6-borjar/6-borjar.tex +++ b/6-borjar/6-borjar.tex @@ -1,30 +1,36 @@ \input ../sgr.tex -\prednaska{6}{Rychlej¹í algoritmy na~minimální kostry}{zapsali Petr ©koda a Tomá¹ Gavenèiak} +\prednaska{6}{Rychlej¹í algoritmy na minimální kostry}{} + +V~této kapitole popí¹eme nìkolik pokroèilej¹ích algoritmù pro problém minimální +kostry. Vesmìs to budou rùzná vylep¹ení klasických algoritmù z~minulé kapitoly. \h{Upravená verze Borùvkova algoritmu pro rovinné grafy} Vyjdeme z my¹lenky, ¾e mù¾eme po ka¾dém kroku pùvodního Borùvkova algoritmu vzniklé komponenty -souvislosti grafu zkontrahovat do jednoho vrcholu a tím získat men¹í graf, který mù¾eme +souvislosti grafu kontrahovat do jednoho vrcholu a tím získat men¹í graf, který mù¾eme znovu rekurzivnì zmen¹ovat. To funguje obecnì, ale uká¾eme, ¾e pro rovinné grafy tak dosáhneme lineární èasové slo¾itosti. \s{Pozorování:} Pokud $F \subseteq {\rm MST}(G)$ (kde ${\rm MST}(G)$ je minimální kostra grafu~$G$), $G'$~je graf vzniklý z~$G$ kontrakcí podél hran z~$F$, pak kostra grafu~$G$, která vznikne z~${\rm MST}(G')$ zpìtným -expandováním kontrahovaných vrcholù, je ${\rm MST}(G)$. +expandováním kontrahovaných vrcholù, je ${\rm MST}(G)$. Pokud kontrakcí vzniknou +smyèky, mù¾eme je ihned odstraòovat; pokud paralelní hrany, ponecháme z~nich v¾dy tu nejlehèí. To nás vede k následujícímu algoritmu: -\s{Algoritmus: MST v rovinných grafech} +\s{Algoritmus: MST v rovinných grafech} \cite{mm:mst} \algo \:Ke ka¾dému vrcholu najdeme nejlevnìj¹í incidentní hranu -- dostaneme mno¾inu hran $F \subseteq E$. -\:Graf zkontrahujeme podle $F$ následovnì: -\::Prohledáme do ¹íøky graf $(V(G), F)$ a pøiøadíme vrcholùm èíslo komponenty, ve které jsou. +\:Graf kontrahujeme podle $F$ následovnì: +\::Prohledáme do ¹íøky graf $(V, F)$ a pøiøadíme ka¾dému vrcholu èíslo komponenty, v~ní¾ se nachází. \::Pøeèíslujeme hrany v~$G$ podle èísel komponent. \:Odstraníme násobné hrany: -\::Setøídíme hrany lexikograficky pomocí pøihrádkového tøídìní (násobné hrany jsou nyní pospolu). +\::Setøídíme hrany lexikograficky pøihrádkovým tøídìním (násobné hrany jsou nyní pospolu). \::Projdeme posloupnost hran a z~ka¾dého úseku multihran odstraníme v¹echny a¾ na nejlevnìj¹í hranu. +Také odstraníme smyèky. \:Pokud stále máme netriviální graf, opakujeme pøedchozí kroky. +\:Vrátíme jako MST v¹echny hrany, které se v~prùbìhu algoritmu dostaly do~$F$. \endalgo \s{Èasová slo¾itost:} @@ -33,7 +39,7 @@ Ka Poèet vrcholù grafu klesá s~ka¾dým cyklem exponenciálnì: $n_i \leq n / 2^i$. Na~zaèátku ka¾dého cyklu je graf rovinný (kontrakcí hrany v~rovinném grafu se rovinnost zachovává) a není to multigraf, tak¾e poèet jeho hran je lineární v poètu vrcholù: -$m_i < 3n_i$. Celkovou èasovou slo¾itost dostaneme jako souèet doby trvání +$m_i < 3n_i$. Celkovou èasovou slo¾itost dostaneme jako souèet dob trvání v¹ech cyklù: $\O(\sum_i m_i) = \O(\sum_i n_i) = \O(n)$. \h{Minorovì uzavøené tøídy} @@ -43,8 +49,7 @@ ne \s{Definice:} Graf $H$ je {\I minorem} grafu $G$ (znaèíme $H \preceq G$) $\equiv$ $H$ lze z $G$ získat -mazáním vrcholù èi hran a kontrahováním hran. -\foot{Zde myslíme kontrakci s~odstranìním násobných hran.} +mazáním vrcholù èi hran a kontrahováním hran (s~odstranìním smyèek a násobných hran). \s{Pozorování:} $H \subseteq G \Rightarrow H \preceq G$. @@ -56,8 +61,10 @@ T Pokud je $\cal C$ minorovì uzavøená tøída grafù, existuje koneèná mno¾ina grafù $Z$ taková, ¾e pro ka¾dý graf $G$ platí: $$G \not\in {\cal C} \iff \exists H \in Z: H \preceq G.$$ -(Èili ka¾dou minorovì uzavøenou tøídu lze charakterizovat {\I koneèným} poètem zakázaných minorù. -To není samo sebou, dokazuje se to dosti pracnì, ale plyne z~toho spousta zajímavých dùsledkù.) +Jinými slovy, ka¾dou minorovì uzavøenou tøídu lze charakterizovat {\I koneèným} poètem zakázaných minorù. +To není samo sebou, dokazuje se to dosti obtí¾nì (a~je to jedna z~nejslavnìj¹ích kombinatorických +vìt za~posledních mnoho let), ale plyne z~toho spousta zajímavých dùsledkù. +Pìkné shrnutí této teorie najdete napøíklad v~Diestelove knize~\cite{diestel:gt}. \s{Pozorování:} Napøíklad pro rovinné grafy jsou tìmi zakázanými minory právì $K_{3,3}$ a $K_5$. To plyne z~Kuratowského vìty: jedna implikace je triviální, @@ -76,38 +83,36 @@ Jeliko mù¾eme pro odhad jejich hustoty pou¾ít pøedchozí vìtu a dostaneme lineární èasovou slo¾itost dokonce pro ka¾dou netriviální minorovì uzavøenou tøídu grafù. -%%%Tomas Gavenciak - \h{Jarníkùv algoritmus s Fibonacciho haldou} Pùvodní Jarníkùv algoritmus s~haldou má díky ní slo¾itost $\O(m\log n)$, to zlep¹íme pou¾itím -Fibonacciho haldy $H$, do~které si budeme ukládat trojice $(v,w,w(vw))$ vrcholù $v$ sousedících -s~dosavadní podkostrou $T$ pøes hranu $vw$, $w\in T$, která bude navíc nejlevnìj¹í mo¾ná. -Tyto trojice bude halda udr¾ovat uspoøádané podle vah. +Fibonacciho haldy $H$, do~které si pro ka¾dý vrchol sousedící se zatím vybudovaným stromem~$T$ +ulo¾íme nejlevnìj¹í z~hran vedoucích mezi tímto vrcholem a stromem~$T$. Tyto hrany bude halda +udr¾ovat uspoøádané podle vah. \newcount\algcnt -\s{Algoritmus: Jarníkùv algoritmus~\#2 (Fredman, Tarjan)} +\s{Algoritmus: Jarníkùv algoritmus~\#2 (Fredman, Tarjan \cite{ft:fibonacci})} \algo -\:Zaèneme libovolným vrcholem $v_0$: $T=\{v_0\}$. -\:Do~haldy $H$ umístíme v¹echny sousedy $v_0$ spolu s pøíslu¹nými hranami. +\:Zaèneme libovolným vrcholem $v_0$, $T\leftarrow \{v_0\}$. +\:Do~haldy $H$ umístíme v¹echny hrany vedoucí z~$v_0$. \:Opakuji dokud $H\neq\emptyset$: -\::$(v,w,w(vw))=\(H)$ -\::$T:=T\cup\{vw\}$ -\::Pro v¹echny sousedy $u\in E\backslash T$ vrcholu $v$ upravím haldu: -\:::Pokud je $u$ v~$H$ nový, pøidáme jej spolu s~nejlevnìj¹í hranou vedoucí z~$u$ do~$T$. -\:::Pokud u¾ $u$ v~$H$ je a $uv$ je levnìj¹í ne¾ pùvodní nejlevnìj¹í hrana z~$u$ -do~$T$, nahradím jeho záznam v~$H$ za~$(u,v,w(uv))$ a provedu $\(u,w(uv))$. +\::$vw\leftarrow \(H)$, pøièem¾ $v\not\in T, w\in T$. +\::$T\leftarrow T\cup\{vw\}$ +\::Pro v¹echny sousedy $u$ vrcholu $v$, které dosud nejsou v~$T$, upravíme haldu: +\:::Pokud je¹tì v~$H$ není hrana incidentní s~$u$, pøidáme hranu~$uv$. +\:::Pokud u¾ tam nìjaká taková hrana je a je-li tì¾¹í ne¾ $uv$, nahradíme ji +hranou~$uv$ a provedeme \. \global\algcnt=\itemcount \endalgo \>Správnost algoritmu pøímo plyne ze~správnosti Jarníkova algoritmu. \s{Èasová slo¾itost:} -Slo¾itost tohoto algoritmu bude $\O(m+n\log n)$, nebo» vnitøní cyklus se provede +Slo¾itost tohoto algoritmu bude $\O(m+n\log n)$, nebo» vnìj¹í cyklus se provede nanejvý¹ $n$-krát, za~\ v~nìm tedy zaplatíme celkem $\O(n\log n)$, za~pøidávání -vrcholù do~$H$ a~nalezání nejlevnìj¹ích hran zaplatíme celkem $\O(m)$ (na~ka¾dou hranu takto +vrcholù do~$H$ a~nalézání nejlevnìj¹ích hran zaplatíme celkem $\O(m)$ (na~ka¾dou hranu takto sáhneme nanejvý¹ dvakrát), za~sni¾ování vah vrcholù v~haldì rovnì¾ pouze $\O(m)$ -(nanejvý¹ $m$-krát provedu porovnání vah a \ v~$\the\algcnt.$ za~$\O(1)$). +(nanejvý¹ $m$-krát provedu porovnání vah a \ v~kroku~\the\algcnt\ za~$\O(1)$). Toto zlep¹ení je dùle¾itìj¹í, ne¾ by se mohlo zdát, proto¾e nám pro grafy s~mnoha hranami (konkrétnì pro grafy s~$m=\Omega(n\log n)$) dává lineární algoritmus. @@ -126,30 +131,30 @@ algoritmu s~kontrahov \s{Èasová slo¾itost:} Slo¾itost první èásti je $\O(m\log\log n)$. Poèet vrcholù se po~první èásti algoritmu sní¾í na~$n'\leq n/\log n$ a slo¾itost druhé èásti bude -tedy nanejvý¹ $\O(m+n\log n'/\log n)=\O(m)$. +tedy nanejvý¹ $\O(m+n'\log n'/\log n)=\O(m)$. \h{Jarníkùv algoritmus s~omezením velikosti haldy} Je¹tì vìt¹ího zrychlení dosáhneme, omezíme-li Jarníkovu algoritmu \#2 vhodnì -velikost haldy a takto budeme bìhem jednoho Jarníkova algoritmu skládat pouze -jednotlivé podkostøièky zastavené v rùstu pøeteèením haldy, podle kterých -graf následnì zkontrahujeme a budeme pokraèovat s mnohem men¹ím grafem. +velikost haldy, tak¾e nám nalezne jednotlivé podkostøièky zastavené v~rùstu +pøeteèením haldy. Podle tìchto podkostøièek graf následnì skontrahujeme +a budeme pokraèovat s~mnohem men¹ím grafem. -\s{Algoritmus: Jarníkùv algoritmus~\#4 (Fredman, Tarjan)} +\s{Algoritmus: Jarníkùv algoritmus~\#4 (Fredman, Tarjan \cite{ft:fibonacci})} \algo -\:Opakuji, dokud mám netriviální $G$ (s alespoò jednou hranou): -\::$t=\vert V_G\vert$. -\::Zvolím $k=2^{2m/t}$ podle aktuálního $t$. -\::$T=\emptyset$ -\::Opakuji, dokud existují vrcholy mimo $T$: -\:::Najdu vrchol $v_0$ mimo $T$. -\:::Spustím Jarníkùv alg. \#2 pro celý graf od $v_0$. Zastavím ho, pokud: +\:Opakujeme, dokud máme netriviální $G$ (s alespoò jednou hranou): +\::$t\leftarrow\vert V(G)\vert$. +\::Zvolíme $k\leftarrow 2^{2m/t}$ (velikost haldy). +\::$T\leftarrow\emptyset$. +\::Opakujeme, dokud existují vrcholy mimo $T$: +\:::Najdeme vrchol $v_0$ mimo $T$. +\:::Spustíme Jarníkùv alg. \#2 pro celý graf od $v_0$. Zastavíme ho, pokud: \global\algcnt=\itemcount \::::$\vert H\vert\geq k$ (byla pøekroèena velikost haldy) nebo \::::$H=\emptyset$ (do¹li sousedé) nebo -\::::do $T$ jsem pøidal hranu oboustrannì incidentní s~hranami v~$T$ (pøipojil -jsem novou podkostru k~nìjaké u¾ nalezené). -\::Zkontrahuji $G$ podle podkoster nalezených v~$T$. +\::::do $T$ jsme pøidali hranu oboustrannì incidentní s~hranami v~$T$ (pøipojili +jsme novou podkostru k~nìjaké u¾ nalezené). +\::Kontrahujeme $G$ podle podkoster nalezených v~$T$. \endalgo \s{Pozorování:} @@ -157,19 +162,19 @@ Pokud algoritmus je Jak to vypadá pro jednotlivá ukonèení: \numlist\ndotted \itemcount=\algcnt -\:$\vert H\vert\geq k$ -- v¹echny hrany v~haldì jsou incidentní s~$T$, tak¾e incidentních je dost. +\:$\vert H\vert\geq k$ -- v¹echny hrany v~haldì jsou incidentní s~$T$ a navzájem rùzné, tak¾e incidentních je dost. \:$H=\emptyset$ -- nemù¾e nastat, algoritmus by skonèil. \:Pøipojím se k~u¾ existující podkostøe -- jen ji zvìt¹ím. \endlist \s{Èasová slo¾itost:} Dùsledkem pøedchozího pozorování je, ¾e poèet podkoster v~jednom prùchodu je nanejvý¹ -$2m/k$. Pro $t'$ a $k'$ v následujícím kroku potom platí $t'\leq 2m/k$ a $k'=2^{2m/t'}\geq 2^k$, -prùchodù bude tedy nanejvý¹ $\log^* n$\foot{$\log^* n$ je inverzní funkce k~\uv{vì¾i +$2m/k$. Pro $t'$ a $k'$ v následujícím kroku potom platí $t'\leq 2m/k$ a $k'=2^{2m/t'}\geq 2^k$. +Prùchodù bude tedy nanejvý¹ $\log^* n$\foot{$\log^* n$ je inverzní funkce k~\uv{vì¾i z~mocnin}, èili $\min\{i:\log^{(i)} n<1 \}$, kde $\log^{(i)} n$ je $i$-krát iterovaný logaritmus.}, proto¾e prùchod s~$k>n$ bude u¾ urèitì poslední. -Jeden vnìj¹í prùchod trvá $\O(m+t\log k)$, zvolím-li tedy $k=2^{2m/t}$, potom bude mít -jeden prùchod slo¾itost $\O(m)$. Celková slo¾itost bude $\O(m\log^{*}n)$. +Pøitom jeden vnìj¹í prùchod trvá $\O(m+t\log k)$, co¾ je pro $k=2^{2m/t}$ +rovno $\O(m)$. Celkovì tedy algoritmus pobì¾í v~èase $\O(m\log^{*}n)$. I~odhad $\log^* n$ je ale pøíli¹ hrubý, proto¾e nezaèínáme s~haldou velikosti~1, nýbr¾ $2^{2m/n}$. Mù¾eme tedy poèet prùchodù pøesnìji omezit funkcí $\beta(m,n)=\min\{i:\log^{(i)}n