6-borjar/6-borjar.tex

   1 \input ../sgr.tex
   2
   3 \prednaska{6}{Rychlej¹í algoritmy na minimální kostry}{}
   4
   5 V~této kapitole popí¹eme nìkolik pokroèilej¹ích algoritmù pro problém minimální
   6 kostry. Vesmìs to budou rùzná vylep¹ení klasických algoritmù z~minulé kapitoly.
   7
   8 \h{Upravená verze Borùvkova algoritmu pro rovinné grafy}
   9
  10 Vyjdeme z my¹lenky, ¾e mù¾eme po ka¾dém kroku pùvodního Borùvkova algoritmu vzniklé komponenty
  11 souvislosti grafu kontrahovat do jednoho vrcholu a tím získat men¹í graf, který mù¾eme
  12 znovu rekurzivnì zmen¹ovat. To funguje obecnì, ale uká¾eme, ¾e pro rovinné grafy tak dosáhneme
  13 lineární èasové slo¾itosti.
  14
  15 \s{Pozorování:}
  16 Pokud $F \subseteq {\rm MST}(G)$ (kde ${\rm MST}(G)$ je minimální kostra grafu~$G$), $G'$~je graf vzniklý
  17 z~$G$ kontrakcí podél hran z~$F$, pak kostra grafu~$G$, která vznikne z~${\rm MST}(G')$ zpìtným
  18 expandováním kontrahovaných vrcholù, je ${\rm MST}(G)$. Pokud kontrakcí vzniknou
  19 smyèky, mù¾eme je ihned odstraòovat; pokud paralelní hrany, ponecháme z~nich v¾dy tu nejlehèí.
  20 To nás vede k následujícímu algoritmu:
  21
  22 \s{Algoritmus: MST v rovinných grafech} \cite{mm:mst}
  23 \algo
  24 \:Ke ka¾dému vrcholu najdeme nejlevnìj¹í incidentní hranu -- dostaneme mno¾inu hran $F \subseteq E$.
  25 \:Graf kontrahujeme podle $F$ následovnì:
  26 \::Prohledáme do ¹íøky graf $(V, F)$ a pøiøadíme ka¾dému vrcholu èíslo komponenty, v~ní¾ se nachází.
  27 \::Pøeèíslujeme hrany v~$G$ podle èísel komponent.
  28 \:Odstraníme násobné hrany:
  29 \::Setøídíme hrany lexikograficky pøihrádkovým tøídìním (násobné hrany jsou nyní pospolu).
  30 \::Projdeme posloupnost hran a z~ka¾dého úseku multihran odstraníme v¹echny a¾ na nejlevnìj¹í hranu.
  31 Také odstraníme smyèky.
  32 \:Pokud stále máme netriviální graf, opakujeme pøedchozí kroky.
  33 \:Vrátíme jako MST v¹echny hrany, které se v~prùbìhu algoritmu dostaly do~$F$.
  34 \endalgo
  35
  36 \s{Èasová slo¾itost:}
  37 Oznaème si $n_i$ a $m_i$ poèet vrcholù a hran na~poèátku $i$-té iterace.
  38 Ka¾dý z~krokù 1--7 trvá $\O(m_i)$, proto i celý cyklus algoritmu trvá $\O(m_i)$.
  39 Poèet vrcholù grafu klesá s~ka¾dým cyklem exponenciálnì: $n_i \leq n / 2^i$.
  40 Na~zaèátku ka¾dého cyklu je graf rovinný (kontrakcí hrany v~rovinném grafu se rovinnost
  41 zachovává) a není to multigraf, tak¾e poèet jeho hran je lineární v poètu vrcholù:
  42 $m_i < 3n_i$. Celkovou èasovou slo¾itost dostaneme jako souèet dob trvání
  43 v¹ech cyklù: $\O(\sum_i m_i) = \O(\sum_i n_i) = \O(n)$.
  44
  45 \h{Minorovì uzavøené tøídy}
  46
  47 Pøedchozí algoritmus ve~skuteènosti funguje v~lineárním èase i pro obecnìj¹í tøídy grafù,
  48 ne¾ jsou grafy rovinné. Tím správným universem jsou minorovì uzavøené tøídy:
  49
  50 \s{Definice:}
  51 Graf $H$ je {\I minorem} grafu $G$ (znaèíme $H \preceq G$), pokud lze $H$ získat z~$G$
  52 mazáním vrcholù èi hran a kontrahováním hran (s~odstranìním smyèek a násobných hran).
  53
  54 \s{Pozorování:}
  55 Relace $\preceq$ je èásteèné uspoøádání na tøídì v¹ech grafù
  56 (reflexivita a tranzitivita plynou pøímo z~definice, pro antisymetrii si staèí
  57 v¹imnout, ¾e jak mazáním, tak kontrakcemi klesá souèet poètu vrcholù s~poètem hran).
  58
  59 \s{Pozorování:}
  60 Pokud je graf~$H$ podgrafem grafu~$G$, pak je také jeho minorem.
  61 Opaènì to neplatí: napøíklad $C_3$ je minorem libovolné del¹í kru¾nice,
  62 ale urèitì ne jejím podgrafem.
  63
  64 \s{Definice:}
  65 Tøída grafù $\cal C$ je {\I minorovì uzavøená,} pokud kdykoliv $G\in {\cal C}$
  66 a $H\preceq G$, platí také $H \in {\cal C}$.
  67
  68 \s{Pøíklady:}
  69 Tøída v¹ech grafù a prázdná tøída jsou jistì minorovì uzavøené. Tìm øíkáme {\I triviální}
  70 tøídy. Mezi ty netriviální patøí tøeba lesy, rovinné grafy, grafy nakreslitelné na dal¹í
  71 plochy, grafy nakreslitelné do ${\bb R}^3$ tak, ¾e ¾ádná kru¾nice netvoøí uzel.
  72
  73 \def\Forb{{\rm Forb}}
  74
  75 \s{Definice:}
  76 Pro tøídu grafù ${\cal C}$ definujeme $\Forb({\cal C})$ jako tøídu v¹ech grafù,
  77 jejich¾ minorem není ¾ádný graf z~${\cal C}$. Pro zjednodu¹ení znaèení budeme pro
  78 koneèné tøídy psát $\Forb(G_1,\ldots,G_k)$ namísto $\Forb(\{G_1,\ldots,G_k\})$.
  79
  80 \s{Pøíklady:}
  81 $\Forb(K_1)$ je tøída v¹ech grafù, které neobsahují ¾ádnou hranu.
  82 $\Forb(C_3)$ je tøída v¹ech lesù.
  83 $\Forb(K_5,K_{3,3})$ jsou v¹echny rovinné grafy -- to je minorová analogie
  84 Kuratowského vìty (pokud graf~$G$ obsahuje dìlení grafu~$H$, pak je $H\preceq G$;
  85 opaènì to obecnì není pravda, ale zrovna pro dvojici $K_5$ a $K_{3,3}$ to funguje;
  86 zkuste si sami).
  87
  88 Lze ka¾dou minorovì uzavøenou tøídu~${\cal C}$ zapsat jako $\Forb({\cal F})$
  89 pro nìjakou tøídu~${\cal F}$ zakázaných minorù? Zajisté ano, staèí napøíklad
  90 zvolit~${\cal F}$ jako doplnìk tøídy~${\cal C}$. Slavná Robertsonova-Seymourova
  91 vìta \cite{rs:wagner} dokonce zaruèuje existenci {\I koneèné} tøídy zakázaných minorù.
  92 To není samo sebou, dokazuje se to dosti obtí¾nì (a~je to jedna z~nejslavnìj¹ích kombinatorických
  93 vìt za~posledních mnoho let), ale plyne z~toho spousta zajímavých dùsledkù.
  94 My si vystaèíme s~daleko jednodu¹¹ími prostøedky a zájemce o~hlub¹í studium minorové
  95 teorie odká¾eme na Diestelovu knihu~\cite{diestel:gt}.
  96
  97 Ve~zbytku této sekce doká¾eme následující vìtu, která je zobecnìním klasického
  98 tvrzení o~hustotì rovinných grafù na minorovì uzavøené tøídy:
  99
 100 \s{Definice:} {\I Hustotou} neprázdného grafu~$G$ nazveme $\varrho(G) = \vert E(G) \vert
 101 / \vert V(G) \vert$. Hustotou tøídy $\varrho({\cal C})$ pak nazveme supremum z~hustot v¹ech
 102 neprázdných grafù le¾ících v~této tøídì.
 103
 104 \s{Vìta (o hustotì minorovì uzavøených tøíd):}
 105 Pokud je tøída grafù $\cal C$ minorovì uzavøená a netriviální (alespoò jeden graf v~ní le¾í
 106 a alespoò jeden nele¾í), pak má koneènou hustotu.
 107
 108 \s{Dùsledek:}
 109 Pokud pou¾íváme kontrahující Borùvkùv algoritmus na grafy le¾ící v~nìjaké netriviální
 110 minorovì uzavøené tøídì, pak v¹echny grafy, které algoritmus v~prùbìhu výpoètu sestrojí,
 111 le¾í také v~této tøídì, tak¾e na odhad jejich hustoty mù¾eme pou¾ít pøedchozí vìtu.
 112 Opìt vyjde, ¾e èasová slo¾itost algoritmu je lineární.
 113
 114 \>{\I Dùkaz vìty:}
 115 Uká¾eme nejprve, ¾e pro ka¾dou tøídu $\cal C$ existuje nìjaké~$k$ takové, ¾e
 116 ${\cal C} \subseteq \Forb(K_k)$.
 117
 118 U¾ víme, ¾e ${\cal C}$ lze zapsat jako $\Forb({\cal F})$ pro nìjakou tøídu~${\cal F}$.
 119 Oznaème~$F$ graf z~${\cal F}$ s~nejmen¹ím poètem vrcholù; pokud existuje více takových,
 120 vybereme libovolný. Hledané~$k$ zvolíme jako poèet vrcholù tohoto grafu.
 121
 122 Inkluze tvaru ${\cal A}\subseteq {\cal B}$ je ekvivalentní tomu, ¾e kdykoliv nìjaký graf~$G$
 123 nele¾í v~${\cal B}$, pak nele¾í ani v~${\cal A}$. Mìjme tedy nìjaký graf $G\not\in\Forb(K_k)$.
 124 Proto $K_k \preceq G$. Ov¹em triviálnì platí $F\preceq K_k$ a relace \uv{být minorem}
 125 je tranzitivní, tak¾e $F\preceq G$, a~proto $G\not\in {\cal C}$.
 126
 127 Víme tedy, ¾e ${\cal C} \subseteq \Forb(K_k)$. Proto musí platit $\varrho({\cal C}) \le
 128 \varrho(\Forb(K_k))$. Tak¾e postaèuje omezit hustotu tøíd s~jedním zakázaným minorem,
 129 který je úplným grafem, a~to plyne z~následující Maderovy vìty.
 130 \qed
 131
 132 \s{Vìta (Maderova):}
 133 Pro ka¾dé~$k\ge 2$ existuje $c(k)$ takové, ¾e kdykoliv má graf hustotu alespoò $c(k)$,
 134 obsahuje jako podgraf nìjaké dìlení grafu~$K_k$.
 135
 136 \proof
 137 Viz Diestel \cite{diestel:gt}.
 138
 139 \h{Jarníkùv algoritmus s Fibonacciho haldou}
 140
 141 Pùvodní Jarníkùv algoritmus s~haldou má díky ní slo¾itost $\O(m\log n)$, to zlep¹íme pou¾itím
 142 Fibonacciho haldy $H$, do~které si pro ka¾dý vrchol sousedící se zatím vybudovaným stromem~$T$
 143 ulo¾íme nejlevnìj¹í z~hran vedoucích mezi tímto vrcholem a stromem~$T$. Tyto hrany bude halda
 144 udr¾ovat uspoøádané podle vah.
 145
 146 \newcount\algcnt
 147 \s{Algoritmus: Jarníkùv algoritmus~\#2 (Fredman, Tarjan \cite{ft:fibonacci})}
 148 \algo
 149 \:Zaèneme libovolným vrcholem $v_0$, $T\leftarrow \{v_0\}$.
 150 \:Do~haldy $H$ umístíme v¹echny hrany vedoucí z~$v_0$.
 151 \:Opakujeme, dokud $H\neq\emptyset$:
 152 \::$vw\leftarrow \<ExtractMin>(H)$, pøièem¾ $v\not\in T, w\in T$.
 153 \::$T\leftarrow T\cup\{vw\}$
 154 \::Pro v¹echny sousedy $u$ vrcholu $v$, kteøí dosud nejsou v~$T$, upravíme haldu:
 155 \:::Pokud je¹tì v~$H$ není hrana incidentní s~$u$, pøidáme hranu~$uv$.
 156 \:::Pokud u¾ tam nìjaká taková hrana je a je-li tì¾¹í ne¾ $uv$, nahradíme ji
 157 hranou~$uv$ a provedeme \<DecreaseKey>.
 158 \global\algcnt=\itemcount
 159 \endalgo
 160
 161 \>Správnost algoritmu pøímo plyne ze~správnosti Jarníkova algoritmu.
 162
 163 \s{Èasová slo¾itost:}
 164 Slo¾itost tohoto algoritmu bude $\O(m+n\log n)$, nebo» vnìj¹í cyklus se provede
 165 nanejvý¹ $n$-krát, za~\<ExtractMin> v~nìm tedy zaplatíme celkem $\O(n\log n)$, za~pøidávání
 166 vrcholù do~$H$ a~nalézání nejlevnìj¹ích hran zaplatíme celkem $\O(m)$ (na~ka¾dou hranu takto
 167 sáhneme nanejvý¹ dvakrát), za~sni¾ování vah vrcholù v~haldì rovnì¾ pouze $\O(m)$
 168 (nanejvý¹ $m$-krát provedu porovnání vah a \<DecreaseKey> v~kroku~\the\algcnt\ za~$\O(1)$).
 169
 170 Toto zlep¹ení je dùle¾itìj¹í, ne¾ by se mohlo zdát, proto¾e nám pro grafy s~mnoha hranami
 171 (konkrétnì pro grafy s~$m=\Omega(n\log n)$) dává lineární algoritmus.
 172
 173 \h{Kombinace Jarníkova a Borùvkova algoritmu}
 174
 175 K~dal¹ímu zlep¹ení dojde, kdy¾ pøed pøedchozím algoritmem spustíme $\log\log n$ cyklù Borùvkova
 176 algoritmu s~kontrahováním vrcholù, èím¾ graf zahustíme.
 177
 178 \s{Algoritmus: Jarníkùv algoritmus~\#3 (pùvod neznámý)}
 179 \algo
 180 \:Provedeme $\log\log n$ cyklù upraveného Borùvkova algoritmu s~kontrahováním hran popsaného vý¹e.
 181 \:Pokraèujeme Jarníkovým algoritmem~\#2.
 182 \endalgo
 183
 184 \s{Èasová slo¾itost:}
 185 Slo¾itost první èásti je $\O(m\log\log n)$.
 186 Poèet vrcholù se po~první èásti algoritmu sní¾í na~$n'\leq n/\log n$ a slo¾itost druhé èásti bude
 187 tedy nanejvý¹ $\O(m+n'\log n')=\O(m)$.
 188
 189 \h{Jarníkùv algoritmus s~omezením velikosti haldy}
 190
 191 Je¹tì vìt¹ího zrychlení dosáhneme, omezíme-li Jarníkovu algoritmu \#2 vhodnì
 192 velikost haldy, tak¾e nám nalezne jednotlivé podkostøièky zastavené v~rùstu
 193 pøeteèením haldy. Podle tìchto podkostøièek graf následnì skontrahujeme
 194 a budeme pokraèovat s~mnohem men¹ím grafem.
 195
 196 \s{Algoritmus: Jarníkùv algoritmus~\#4 (Fredman, Tarjan \cite{ft:fibonacci})}
 197 \algo
 198 \:Opakujeme, dokud máme netriviální $G$ (s alespoò jednou hranou):
 199 \::$t\leftarrow\vert V(G)\vert$.
 200 \::Zvolíme $k\leftarrow 2^{2m/t}$ (velikost haldy).
 201 \::$T\leftarrow\emptyset$.
 202 \::Opakujeme, dokud existují vrcholy mimo $T$:
 203 \:::Najdeme vrchol $v_0$ mimo $T$.
 204 \:::Spustíme Jarníkùv alg. \#2 pro celý graf od $v_0$. Zastavíme ho, pokud:
 205 \global\algcnt=\itemcount
 206 \::::$\vert H\vert\geq k$ (byla pøekroèena velikost haldy) nebo
 207 \::::$H=\emptyset$ (do¹li sousedé) nebo
 208 \::::do $T$ jsme pøidali hranu oboustrannì incidentní s~hranami v~$T$ (pøipojili
 209 jsme novou podkostru k~nìjaké u¾ nalezené).
 210 \::Kontrahujeme $G$ podle podkoster nalezených v~$T$.
 211 \endalgo
 212
 213 \s{Pozorování:}
 214 Pokud algoritmus je¹tì neskonèil, je ka¾dá z~nalezených podkoster v~$T$ incidentní s~alespoò $k$ hranami
 215 (do toho poèítáme i vnitøní hrany vedoucí mezi vrcholy podkostry).
 216 Jak to vypadá pro jednotlivá ukonèení:
 217 \numlist\ndotted
 218 \itemcount=\algcnt
 219 \:$\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.
 220 \:$H=\emptyset$ -- nemù¾e nastat, algoritmus by skonèil.
 221 \:Pøipojím se k~u¾ existující podkostøe -- jen ji zvìt¹ím.
 222 \endlist
 223
 224 \s{Èasová slo¾itost:}
 225 Dùsledkem pøedchozího pozorování je, ¾e poèet podkoster v~jednom prùchodu je nanejvý¹
 226 $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$.
 227 Prùchodù bude tedy nanejvý¹ $\log^* n$\foot{$\log^* n$ je inverzní funkce k~\uv{vì¾i
 228 z~mocnin}, èili $\min\{i:\log^{(i)} n<1 \}$, kde $\log^{(i)} n$ je $i$-krát iterovaný
 229 logaritmus.}, proto¾e prùchod s~$k>n$ bude u¾ urèitì poslední.
 230 Pøitom jeden vnìj¹í prùchod trvá $\O(m+t\log k)$, co¾ je pro $k=2^{2m/t}$
 231 rovno $\O(m)$. Celkovì tedy algoritmus pobì¾í v~èase $\O(m\log^{*}n)$.
 232
 233 I~odhad $\log^* n$ je ale pøíli¹ hrubý, proto¾e nezaèínáme s~haldou velikosti~1, nýbr¾
 234 $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\}$
 235 a èasovou slo¾itost odhadnout jako $\O(m\beta(m,n))$. To nám dává lineární algoritmus
 236 pro grafy s~$m\geq n\log^{(k)}n$ pro libovolnou konstantu $k$, jeliko¾ $\beta(m,n)$ tehdy vyjde
 237 omezená konstantou.
 238
 239 \h{Dal¹í výsledky}
 240
 241 \itemize\ibull
 242 \:$\O(m\alpha(m,n))$, kde $\alpha(m,n)$ je obdoba inverzní
 243   Ackermannovy funkce definovaná podobnì, jako je $\beta(m,n)$ obdobou $\log^*$.
 244   \cite{chazelle:ackermann}, \cite{pettie:ackermann}
 245 \:$\O({\cal T}(m,n))$, kde ${\cal T}(m,n)$ je hloubka optimálního rozhodovacího stromu
 246   pro nalezení minimální kostry v~grafech s~patøièným poètem hran a vrcholù
 247   \cite{pettie:optimal}.
 248   Jeliko¾ ka¾dý deterministický algoritmus zalo¾ený na~porovnávání vah lze popsat rozhodovacím stromem,
 249   je tento algoritmus zaruèenì optimální. Jen bohu¾el nevíme, jak optimální stromy vypadají, tak¾e
 250   je stále otevøeno, zda lze MST nalézt v~lineárním èase. Nicménì tento algoritmus
 251   pracuje i na~Pointer Machine, proèe¾ víme, ¾e pokud je lineární slo¾itosti mo¾né dosáhnout, není k~tomu
 252   potøeba výpoèetní síla RAMu.\foot{O výpoèetních modelech viz pøí¹tí kapitola.}
 253 \:$\O(m)$ pro grafy s~celoèíselnými vahami (na~RAMu) \cite{fw90trans} -- uká¾eme v~jedné
 254   z~následujících kapitol.
 255 \:$\O(m)$, pokud u¾ máme hrany setøídìné podle vah: jeliko¾ víme, ¾e zále¾í jen na~uspoøádání,
 256   mù¾eme váhy pøeèíslovat na~$1\ldots m$ a pou¾ít pøedchozí algoritmus.
 257 \:$\O(m)$ prùmìrnì: randomizovaný algoritmus, který pro libovolný vstupní graf dobìhne v~oèekávaném
 258   lineárním èase~\cite{karger:randomized}.
 259 \:Na~zji¹tìní, zda je zadaná kostra minimální, staèí $\O(m)$ porovnání \cite{komlos:verify} a dokonce
 260   lze v~lineárním èase zjistit, která to jsou \cite{king:verify}. Z~toho ostatnì vychází pøedchozí
 261   randomizovaný algoritmus.
 262 \endlist
 263
 264 \references
 265 \bye