\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:}
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}
ne¾ jsou grafy rovinné. Tím správným universem jsou minorovì uzavøené tøídy:
\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.}
+Graf $H$ je {\I minorem} grafu $G$ (znaèíme $H \preceq G$), pokud lze $H$ získat z~$G$
+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í:}
+Relace $\preceq$ je èásteèné uspoøádání na tøídì v¹ech grafù
+(reflexivita a tranzitivita plynou pøímo z~definice, pro antisymetrii si staèí
+v¹imnout, ¾e jak mazáním, tak kontrakcemi klesá souèet poètu vrcholù s~poètem hran).
\s{Pozorování:}
-$H \subseteq G \Rightarrow H \preceq G$.
+Pokud je graf~$H$ podgrafem grafu~$G$, pak je také jeho minorem.
+Opaènì to neplatí: napøíklad $C_3$ je minorem libovolné del¹í kru¾nice,
+ale urèitì ne jejím podgrafem.
+
+\s{Definice:}
+Tøída grafù $\cal C$ je {\I minorovì uzavøená,} pokud kdykoliv $G\in {\cal C}$
+a $H\preceq G$, platí také $H \in {\cal C}$.
+
+\s{Pøíklady:}
+Tøída v¹ech grafù a prázdná tøída jsou jistì minorovì uzavøené. Tìm øíkáme {\I triviální}
+tøídy. Mezi ty netriviální patøí tøeba lesy, rovinné grafy, grafy nakreslitelné na dal¹í
+plochy, grafy nakreslitelné do ${\bb R}^3$ tak, ¾e ¾ádná kru¾nice netvoøí uzel.
+
+\def\Forb{{\rm Forb}}
\s{Definice:}
-Tøída grafù $\cal C$ je {\I minorovì uzavøená} $\equiv \forall G,H: G \in {\cal C}, H \preceq G \Rightarrow H \in {\cal C}$.
-
-\s{Vìta:} (Robertson, Seymour)
-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ù.)
-
-\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í,
-druhá dá trochu práce: pokud je $K_{3,3} \preceq G$, najde se v~$G$ podgraf
-isomorfní nìjakému dìlení~$K_{3,3}$; pokud je $K_5 \preceq G$, podgraf isomorfní
-dìlení~$K_5$ se v~$G$ najít nemusí, ale pokud se nenajde, najde se tam podgraf isomorfní
-dìlení $K_{3,3}$. (Zkuste si sami.)
-
-\s{Vìta:} (Robertson, Seymour)
+Pro tøídu grafù ${\cal C}$ definujeme $\Forb({\cal C})$ jako tøídu v¹ech grafù,
+jejich¾ minorem není ¾ádný graf z~${\cal C}$. Pro zjednodu¹ení znaèení budeme pro
+koneèné tøídy psát $\Forb(G_1,\ldots,G_k)$ namísto $\Forb(\{G_1,\ldots,G_k\})$.
+
+\s{Pøíklady:}
+$\Forb(K_1)$ je tøída v¹ech grafù, které neobsahují ¾ádnou hranu.
+$\Forb(C_3)$ je tøída v¹ech lesù.
+$\Forb(K_5,K_{3,3})$ jsou v¹echny rovinné grafy -- to je minorová analogie
+Kuratowského vìty (pokud graf~$G$ obsahuje dìlení grafu~$H$, pak je $H\preceq G$;
+opaènì to obecnì není pravda, ale zrovna pro dvojici $K_5$ a $K_{3,3}$ to funguje;
+zkuste si sami).
+
+Lze ka¾dou minorovì uzavøenou tøídu~${\cal C}$ zapsat jako $\Forb({\cal F})$
+pro nìjakou tøídu~${\cal F}$ zakázaných minorù? Zajisté ano, staèí napøíklad
+zvolit~${\cal F}$ jako doplnìk tøídy~${\cal C}$. Slavná Robertsonova-Seymourova
+vìta \cite{rs:wagner} dokonce zaruèuje existenci {\I koneèné} tøídy 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ù.
+My si vystaèíme s~daleko jednodu¹¹ími prostøedky a zájemce o~hlub¹í studium minorové
+teorie odká¾eme na Diestelovu knihu~\cite{diestel:gt}.
+
+Ve~zbytku této sekce doká¾eme následující vìtu, která je zobecnìním klasického
+tvrzení o~hustotì rovinných grafù na minorovì uzavøené tøídy:
+
+\s{Definice:} {\I Hustotou} neprázdného grafu~$G$ nazveme $\varrho(G) = \vert E(G) \vert
+/ \vert V(G) \vert$. Hustotou tøídy $\varrho(C)$ pak nazveme supremum z~hustot v¹ech
+neprázdných grafù le¾ících v~této tøídì.
+
+\s{Vìta (o hustotì minorovì uzavøených tøíd):}
Pokud je tøída grafù $\cal C$ minorovì uzavøená a netriviální (alespoò jeden graf v~ní le¾í
-a alespoò jeden nele¾í), pak $\exists c > 0: \forall G \in {\cal C}:
-\vert E(G) \vert \leq c\cdot \vert V(G) \vert$.
+a alespoò jeden nele¾í), pak má koneènou hustotu.
\s{Dùsledek:}
-Jeliko¾ v¹echny grafy vygenerované pøedchozím algoritmem jsou minory grafu ze~vstupu,
-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ù.
+Pokud pou¾íváme kontrahující Borùvkùv algoritmus na grafy le¾ící v~nìjaké netriviální
+minorovì uzavøené tøídì, pak v¹echny grafy, které algoritmus v~prùbìhu výpoètu sestrojí,
+le¾í také v~této tøídì, tak¾e na odhad jejich hustoty mù¾eme pou¾ít pøedchozí vìtu.
+Opìt vyjde, ¾e èasová slo¾itost algoritmu je lineární.
+
+\>{\I Dùkaz vìty:}
+Uká¾eme nejprve, ¾e pro ka¾dou tøídu $\cal C$ existuje nìjaké~$k$ takové, ¾e
+${\cal C} \subseteq \Forb(K_k)$.
+
+U¾ víme, ¾e ${\cal C}$ lze zapsat jako $\Forb({\cal F})$ pro nìjakou tøídu~${\cal F}$.
+Oznaème~$F$ graf z~${\cal F}$ s~nejmen¹ím poètem vrcholù; pokud existuje více takových,
+vybereme libovolný. Hledané~$k$ zvolíme jako poèet vrcholù tohoto grafu.
+
+Inkluze tvaru ${\cal A}\subseteq {\cal B}$ je ekvivalentní tomu, ¾e kdykoliv nìjaký graf~$G$
+nele¾í v~${\cal B}$, pak nele¾í ani v~${\cal A}$. Mìjme tedy nìjaký graf $G\not\in\Forb(K_k)$.
+Proto $K_k \preceq G$. Ov¹em triviálnì platí $F\preceq K_k$ a relace \uv{být minorem}
+je tranzitivní, tak¾e $F\preceq G$, a~proto $G\not\in {\cal C}$.
+
+Víme tedy, ¾e ${\cal C} \subseteq \Forb(K_k)$. Proto musí platit $\varrho({\cal C}) \le
+\varrho(\Forb(K_k))$. Tak¾e postaèuje omezit hustotu tøíd s~jedním zakázaným minorem,
+který je úplným grafem, a~to plyne z~následující Maderovy vìty.
+\qed
+
+\s{Vìta (Maderova):}
+Pro ka¾dé~$k\ge 2$ existuje $c(k)$ takové, ¾e kdykoliv má graf hustotu alespoò $c(k)$,
+obsahuje jako podgraf nìjaké dìlení grafu~$K_k$.
-%%%Tomas Gavenciak
+\proof
+Viz Diestel \cite{diestel:gt}.
\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.
-\:Opakuji dokud $H\neq\emptyset$:
-\::$(v,w,w(vw))=\<DeleteMin>(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 $\<DecreaseKey>(u,w(uv))$.
+\:Zaèneme libovolným vrcholem $v_0$, $T\leftarrow \{v_0\}$.
+\:Do~haldy $H$ umístíme v¹echny hrany vedoucí z~$v_0$.
+\:Opakujeme, dokud $H\neq\emptyset$:
+\::$vw\leftarrow \<ExtractMin>(H)$, pøièem¾ $v\not\in T, w\in T$.
+\::$T\leftarrow T\cup\{vw\}$
+\::Pro v¹echny sousedy $u$ vrcholu $v$, kteøí 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 \<DecreaseKey>.
\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
-nanejvý¹ $n$-krát, za~\<DeleteMin> 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
+Slo¾itost tohoto algoritmu bude $\O(m+n\log n)$, nebo» vnìj¹í cyklus se provede
+nanejvý¹ $n$-krát, za~\<ExtractMin> v~nìm tedy zaplatíme celkem $\O(n\log n)$, za~pøidávání
+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 \<DecreaseKey> v~$\the\algcnt.$ za~$\O(1)$).
+(nanejvý¹ $m$-krát provedu porovnání vah a \<DecreaseKey> 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.
\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ò jedou 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í:}
-Pokud algoritmus je¹tì neskonèil, je ka¾dá z~nalezených podkoster v~$T$ incidentní s~alespoò $k$ hranami.
+Pokud algoritmus je¹tì neskonèil, je ka¾dá z~nalezených podkoster v~$T$ incidentní s~alespoò $k$ hranami
+(do toho poèítáme i vnitøní hrany vedoucí mezi vrcholy podkostry).
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<m/n\}$
\itemize\ibull
\:$\O(m\alpha(m,n))$, kde $\alpha(m,n)$ je obdoba inverzní
Ackermannovy funkce definovaná podobnì, jako je $\beta(m,n)$ obdobou $\log^*$.
- [Chazelle 2000]
+ \cite{chazelle:ackermann}, \cite{pettie:ackermann}
\:$\O({\cal T}(m,n))$, kde ${\cal T}(m,n)$ je hloubka optimálního rozhodovacího stromu
pro nalezení minimální kostry v~grafech s~patøièným poètem hran a vrcholù
- [Pettie, Ramachandran 2002].
+ \cite{pettie:optimal}.
Jeliko¾ ka¾dý deterministický algoritmus zalo¾ený na~porovnávání vah lze popsat rozhodovacím stromem,
- je tento algoritmus zaruèenì optimální. Jen bohu¾el nevíme, optimální stromy vypadají, tak¾e
- je stále otevøeno, zda lze MST nalézt v~lineárním èase. Nicménì jeliko¾ tento algoritmus
- pracuje i na~Pointer Machine, víme, ¾e pokud je lineární slo¾itosti mo¾né dosáhnout, není k~tomu
+ je tento algoritmus zaruèenì optimální. Jen bohu¾el nevíme, jak optimální stromy vypadají, tak¾e
+ je stále otevøeno, zda lze MST nalézt v~lineárním èase. Nicménì tento algoritmus
+ pracuje i na~Pointer Machine, proèe¾ víme, ¾e pokud je lineární slo¾itosti mo¾né dosáhnout, není k~tomu
potøeba výpoèetní síla RAMu.\foot{O výpoèetních modelech viz pøí¹tí kapitola.}
-\:$\O(m)$ pro grafy s~celoèíselnými vahami (na~RAMu) [Fredman, Willard 1990] -- uká¾eme v~jedné
+\:$\O(m)$ pro grafy s~celoèíselnými vahami (na~RAMu) \cite{fw90trans} -- uká¾eme v~jedné
z~následujících kapitol.
\:$\O(m)$, pokud u¾ máme hrany setøídìné podle vah: jeliko¾ víme, ¾e zále¾í jen na~uspoøádání,
- mù¾eme váhy pøeèíslovat na~$1\ldots n$ a pou¾ít pøedchozí algoritmus.
-\:$\O(m)$ randomizovanì v~prùmìrném pøípadì [Karger, Klein, Tarjan 1995]
-\:Na~zji¹tìní, zda je zadaná kostra minimální, staèí $\O(m)$ porovnání [Komlós 1984] a dokonce
- lze v~lineárním èase zjistit, která to jsou [King 1995]. Z~toho ostatnì vychází pøedchozí
+ mù¾eme váhy pøeèíslovat na~$1\ldots m$ a pou¾ít pøedchozí algoritmus.
+\:$\O(m)$ prùmìrnì: randomizovaný algoritmus, který pro libovolný vstupní graf dobìhne v~oèekávaném
+ lineárním èase~\cite{karger:randomized}.
+\:Na~zji¹tìní, zda je zadaná kostra minimální, staèí $\O(m)$ porovnání \cite{komlos:verify} a dokonce
+ lze v~lineárním èase zjistit, která to jsou \cite{king:verify}. Z~toho ostatnì vychází pøedchozí
randomizovaný algoritmus.
\endlist
+\references
\bye
projects / ga.git / blobdiff