\input ../sgr.tex
-\prednaska{6}{Rychlej¹í algoritmy na minimální kostry}{}
+\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.
+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}
+\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 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.
+Vyjdeme z myšlenky, že můžeme po každém kroku původního Borůvkova algoritmu vzniklé komponenty
+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à Ä\8dasové 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)$. 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{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)$. 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} \cite{mm:mst}
+\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 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 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$.
+\:Ke každému vrcholu najdeme nejlevnÄ\9bjÅ¡Ã incidentnà hranu -- dostaneme množinu hran $F \subseteq E$.
+\: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 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:}
-Oznaème si $n_i$ a $m_i$ poèet vrcholù a hran na~poèátku $i$-té iterace.
-Ka¾dý z~krokù 1--7 trvá $\O(m_i)$, proto i celý cyklus algoritmu trvá $\O(m_i)$.
-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 dob trvání
-v¹ech cyklù: $\O(\sum_i m_i) = \O(\sum_i n_i) = \O(n)$.
+\s{Ä\8casová složitost:}
+Označme si $n_i$ a $m_i$ počet vrcholů a hran na~počátku $i$-té iterace.
+Každý z~kroků 1--7 trvá $\O(m_i)$, proto i celý cyklus algoritmu trvá $\O(m_i)$.
+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 dob trvání
+všech cyklů: $\O(\sum_i m_i) = \O(\sum_i n_i) = \O(n)$.
-\h{Minorovì uzavøené tøídy}
+\h{Minorově uzavřené třídy}
-Pøedchozí algoritmus ve~skuteènosti funguje v~lineárním èase i pro obecnìj¹í tøídy grafù,
-ne¾ jsou grafy rovinné. Tím správným universem jsou minorovì uzavøené tøídy:
+Předchozí algoritmus ve~skutečnosti funguje v~lineárním čase i pro obecnější třídy grafů,
+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$), 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).
+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í:}
+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í:}
-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{Pozorování:}
+Pokud je graf~$H$ podgrafem grafu~$G$, pak je také jeho minorem.
+OpaÄ\8dnÄ\9b to neplatÃ: napÅ\99Ã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}$.
+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.
+\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:}
-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_2)$ 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;
+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_2)$ 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({\cal 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 má koneènou hustotu.
-
-\s{Dùsledek:}
-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
+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({\cal 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 má konečnou hustotu.
+
+\s{Důsledek:}
+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Å\99Ãdu $\cal C$ existuje nÄ\9bjaké~$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.
+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}$.
+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.
+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$.
+\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$.
\proof
Viz Diestel \cite{diestel:gt}.
-\h{Jarníkùv algoritmus s Fibonacciho haldou}
+\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 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.
+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 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 \cite{ft:fibonacci})}
+\s{Algoritmus: Jarníkův algoritmus~\#2 (Fredman, Tarjan \cite{ft:fibonacci})}
\algo
-\:Zaèneme libovolným vrcholem $v_0$, $T\leftarrow \{v_0\}$.
-\:Do~haldy $H$ umístíme v¹echny hrany vedoucí z~$v_0$.
+\: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$.
+\::$vw\leftarrow \<ExtractMin>(H)$, pÅ\99iÄ\8demž $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
+\::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.
+\>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» 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~kroku~\the\algcnt\ za~$\O(1)$).
+\s{Ä\8casová složitost:}
+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Ä\9bjÅ¡Ã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Ä\9b rovnÄ\9bž pouze $\O(m)$
+(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.
+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.
-\h{Kombinace Jarníkova a Borùvkova algoritmu}
+\h{Kombinace Jarníkova a Borůvkova algoritmu}
-K~dal¹ímu zlep¹ení dojde, kdy¾ pøed pøedchozím algoritmem spustíme $\log\log n$ cyklù Borùvkova
-algoritmu s~kontrahováním vrcholù, èím¾ graf zahustíme.
+K~dalšímu zlepšení dojde, když před předchozím algoritmem spustíme $\log\log n$ cyklů Borůvkova
+algoritmu s~kontrahováním vrcholů, čímž graf zahustíme.
-\s{Algoritmus: Jarníkùv algoritmus~\#3 (pùvod neznámý)}
+\s{Algoritmus: Jarníkův algoritmus~\#3 (původ neznámý)}
\algo
-\:Provedeme $\log\log n$ cyklù upraveného Borùvkova algoritmu s~kontrahováním hran popsaného vý¹e.
-\:Pokraèujeme Jarníkovým algoritmem~\#2.
+\:Provedeme $\log\log n$ cyklů upraveného Borůvkova algoritmu s~kontrahováním hran popsaného výše.
+\:Pokračujeme Jarníkovým algoritmem~\#2.
\endalgo
-\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')=\O(m)$.
+\s{Ä\8casová 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')=\O(m)$.
-\h{Jarníkùv algoritmus s~omezením velikosti haldy}
+\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, 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.
+Ještě většího zrychlení dosáhneme, omezíme-li Jarníkovu algoritmu \#2 vhodně
+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 \cite{ft:fibonacci})}
+\s{Algoritmus: Jarníkův algoritmus~\#4 (Fredman, Tarjan \cite{ft:fibonacci})}
\algo
-\:Opakujeme, dokud máme netriviální $G$ (s alespoò jednou hranou):
+\: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).
+\::Zvolíme $k\leftarrow 2^{2m/t}$ (velikost haldy).
\::$T\leftarrow\emptyset$.
-\::Opakujeme, dokud existují vrcholy mimo $T$:
+\::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:
+\:::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$ 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$.
+\::::$\vert H\vert\geq k$ (byla překročena velikost haldy) nebo
+\::::$H=\emptyset$ (došli sousedé) nebo
+\::::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
-(do toho poèítáme i vnitøní hrany vedoucí mezi vrcholy podkostry).
-Jak to vypadá pro jednotlivá ukonèení:
+\s{Pozorování:}
+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$ 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.
+\:$\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
-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í.
-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)$.
+\s{Ä\8casová 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Ä\9bž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í.
+PÅ\99itom jeden vnÄ\9bjÅ¡Ã 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\}$
-a èasovou slo¾itost odhadnout jako $\O(m\beta(m,n))$. To nám dává lineární algoritmus
-pro grafy s~$m\geq n\log^{(k)}n$ pro libovolnou konstantu $k$, jeliko¾ $\beta(m,n)$ tehdy vyjde
-omezená konstantou.
+I~odhad $\log^* n$ je ale pÅ\99ÃliÅ¡ hrubý, protože nezaÄ\8dÃ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\}$
+a časovou složitost odhadnout jako $\O(m\beta(m,n))$. To nám dává lineární algoritmus
+pro grafy s~$m\geq n\log^{(k)}n$ pro libovolnou konstantu $k$, jelikož $\beta(m,n)$ tehdy vyjde
+omezená konstantou.
-\h{Dal¹í výsledky}
+\h{Další výsledky}
\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^*$.
+\:$\O(m\alpha(m,n))$, kde $\alpha(m,n)$ je obdoba inverzní
+ Ackermannovy funkce definovaná podobně, jako je $\beta(m,n)$ obdobou $\log^*$.
\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ù
+\:$\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ů
\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, 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) \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 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.
+ Jelikož každý deterministický algoritmus založený na~porovnávání vah lze popsat rozhodovacím stromem,
+ je tento algoritmus zaruÄ\8denÄ\9b 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) \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 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
projects / ga.git / blobdiff