6-borjar/6-borjar.tex

   1 \input ../sgr.tex
   2
   3 \prednaska{6}{Vylep¹ení Borùvkova a Jarníkova algoritmu}{zapsali Petr ©koda a Tomá¹ Gavenèiak}
   4
   5 \h{Upravená verze Borùvkova algoritmu pro rovinné grafy}
   6
   7 Vyjdeme z my¹lenky, ¾e mù¾eme po ka¾dém kroku pùvodního Borùvkova algoritmu vzniklé komponenty
   8 souvislosti grafu zkontrahovat do jednoho vrcholu a tím získat men¹í graf, který mù¾eme
   9 znovu rekurzivnì zmen¹ovat. To funguje obecnì, ale uká¾eme, ¾e pro rovinné grafy tak dosáhneme
  10 lineární èasové slo¾itosti.
  11
  12 \s{Pozorování:}
  13 Pokud $F \subseteq {\rm MST}(G)$ (kde ${\rm MST}(G)$ je minimální kostra grafu~$G$), $G'$~je graf vzniklý
  14 z~$G$ kontrakcí podél hran z~$F$, pak kostra grafu~$G$, která vznikne z~${\rm MST}(G')$ zpìtným
  15 expandováním kontrahovaných vrcholù, je ${\rm MST}(G)$.
  16 To nás vede k následujícímu algoritmu:
  17
  18 \s{Algoritmus: MST v rovinných grafech}
  19 \algo
  20 \:Ke ka¾dému vrcholu najdeme nejlevnìj¹í incidentní hranu -- dostaneme mno¾inu hran $F \subseteq E$.
  21 \:Graf zkontrahujeme podle $F$ následovnì:
  22 \::Prohledáme do ¹íøky graf $(V(G), F)$ a pøiøadíme vrcholùm èíslo komponenty, ve které jsou.
  23 \::Pøeèíslujeme hrany v~$G$ podle èísel komponent.
  24 \:Odstraníme násobné hrany:
  25 \::Setøídíme hrany lexikograficky pomocí pøihrádkového tøídìní (násobné hrany jsou nyní pospolu).
  26 \::Projdeme posloupnost hran a z~ka¾dého úseku multihran odstraníme v¹echny a¾ na nejlevnìj¹í hranu.
  27 \:Pokud stále máme netriviální graf, opakujeme pøedchozí kroky.
  28 \endalgo
  29
  30 \s{Èasová slo¾itost:}
  31 Oznaème si $n_i$ a $m_i$ poèet vrcholù a hran na~poèátku $i$-té iterace.
  32 Ka¾dý z~krokù 1--7 trvá $\O(m_i)$, proto i celý cyklus algoritmu trvá $\O(m_i)$.
  33 Poèet vrcholù grafu klesá s~ka¾dým cyklem exponenciálnì: $n_i \leq n / 2^i$.
  34 Na~zaèátku ka¾dého cyklu je graf rovinný (kontrakcí hrany v~rovinném grafu se rovinnost
  35 zachovává) a poèet hran rovinného grafu je lineární v poètu vrcholù, tak¾e
  36 platí $m_i < 3n_i$. Celkovou èasovou slo¾itost dostaneme jako souèet doby trvání
  37 v¹ech cyklù: $\O(\sum_i m_i) = \O(\sum_i n_i) = \O(n)$.
  38
  39 \h{Minorovì uzavøené tøídy}
  40
  41 Pøedchozí algoritmus ve~skuteènosti funguje v~lineárním èase i pro obecnìj¹í tøídy grafù,
  42 ne¾ jsou grafy rovinné. Tím správným universem jsou minorovì uzavøené tøídy:
  43
  44 \s{Definice:}
  45 Graf $H$ je {\I minorem} grafu $G$ $\equiv$ $H$ lze z $G$ získat
  46 mazáním vrcholù èi hran a kontrahováním hran. Znaèíme $H \preceq G$.
  47
  48 \s{Pozorování:}
  49 $H \subseteq G \Rightarrow H \preceq G$.
  50
  51 \s{Definice:}
  52 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}$.
  53
  54 \s{Vìta:} (Robertson, Seymour)
  55 Pokud je $\cal C$ minorovì uzavøená tøída grafù, existuje koneèná mno¾ina grafù $Z$ taková,
  56 ¾e pro ka¾dý graf $G$ platí:
  57 $$G \not\in {\cal C} \iff \exists H \in Z: H \preceq G.$$
  58 (Èili ka¾dou minorovì uzavøenou tøídu lze charakterizovat {\I koneèným} poètem zakázaných minorù.
  59 To není samo sebou, dokazuje se to dosti pracnì, ale plyne z~toho spousta zajímavých dùsledkù.)
  60
  61 \s{Pozorování:} Napøíklad pro rovinné grafy jsou tìmi zakázanými minory právì
  62 $K_{3,3}$ a $K_5$. To plyne z~Kuratowského vìty: jedna implikace je triviální,
  63 druhá dá trochu práce: pokud je $K_{3,3} \preceq G$, najde se v~$G$ podgraf
  64 isomorfní nìjakému dìlení~$K_{3,3}$; pokud je $K_5 \preceq G$, podgraf isomorfní
  65 dìlení~$K_5$ se v~$G$ najít nemusí, ale pokud se nenajde, najde se tam podgraf isomorfní
  66 dìlení $K_{3,3}$. (Zkuste si sami.)
  67
  68 \s{Vìta:} (Robertson, Seymour)
  69 Pokud je tøída grafù $\cal C$ minorovì uzavøená a netriviální (alespoò jeden graf v~ní le¾í
  70 a alespoò jeden nele¾í), pak $\exists c > 0: \forall G \in {\cal C}:
  71 \vert E(G) \vert \leq c\cdot  \vert V(G) \vert$.
  72
  73 \s{Dùsledek:}
  74 Jeliko¾ v¹echny grafy vygenerované pøedchozím algoritmem jsou minory grafu ze~vstupu,
  75 mù¾eme pro odhad jejich hustoty pou¾ít pøedchozí vìtu a dostaneme tak, ¾e pøedchozí
  76 algoritmus má lineární èasovou slo¾itost dokonce pro ka¾dou netriviální minorovì uzavøenou
  77 tøídu grafù.
  78
  79 %%%Tomas Gavenciak
  80
  81 \h{Jarníkùv algoritmus s Fibonacciho haldou}
  82
  83 Pùvodní Jarníkùv algoritmus s~haldou má díky ní slo¾itost $\O(m\log n)$, to zlep¹íme pou¾itím
  84 Fibonacciho haldy $H$, do~které si budeme ukládat trojice $(v,w,w(vw))$ vrcholù $v$ sousedících
  85 s~dosavadní podkostrou $T$ pøes hranu $vw$, $w\in T$, která bude navíc nejlevnìj¹í mo¾ná.
  86
  87 \newcount\algcnt
  88 \s{Algoritmus: Jarníkùv algoritmus~\#2 (Fredman, Tarjan)}
  89 \algo
  90 \:Zaèneme libovolným vrcholem $v_0$: $T=\{v_0\}$.
  91 \:Do~haldy $H$ umístíme v¹echny sousedy $v_0$ spolu s pøíslu¹nými hranami.
  92 \:Opakuji dokud $H\neq\emptyset$:
  93 \::$(v,w,w(vw))=\<DeleteMin>(H)$
  94 \::$T:=T\cup\{vw\}$
  95 \::Pro v¹echny sousedy $u\in E\backslash T$ vrcholu $v$ upravím haldu:
  96 \:::Pokud je $u$ v~$H$ nový, pøidáme jej spolu s~nejlevnìj¹í hranou vedoucí z~$u$ do~$T$.
  97 \:::Pokud u¾ $u$ v~$H$ je a $uv$ je levnìj¹í ne¾ pùvodní nejlevnìj¹í hrana z~$u$
  98 do~$T$, nahradím jeho záznam v~$H$ za~$(u,v,w(uv))$ a provedu $\<DecreaseKey>(u,w(uv))$.
  99 \global\algcnt=\itemcount
 100 \endalgo
 101
 102 Správnost algoritmu pøímo plyne ze~správnosti Jarníkova algoritmu.
 103
 104 \s{Èasová slo¾itost:}
 105 Slo¾itost tohoto algoritmu bude $\O(m+n\log n)$, nebo» vnitøní cyklus se provede
 106 nanejvý¹ $n$-krát, za~\<DeleteMin> v~nìm tedy zaplatíme $\O(n\log n)$, za~pøidávání
 107 vrcholù do~$H$ a~nalezání nejlevnìj¹ích hran zaplatíme $\O(m)$ (na~ka¾dou hranu takto
 108 sáhneme nanejvý¹ dvakrát), za~sni¾ování vah vrcholù v~haldì rovnì¾ pouze $\O(m)$
 109 (nanejvý¹ $m$-krát provedu porovnání vah a \<DecreaseKey> v~$\the\algcnt.$ za~$\O(1)$).
 110
 111 Toto zlep¹ení je dùle¾itìj¹í, ne¾ by se mohlo zdát, proto¾e nám pro grafy s~mnoha hranami
 112 (konkrétnì pro grafy s~$m=\Omega(n\log n)$) dává lineární algoritmus.
 113
 114 \h{Kombinace Jarníkova a Borùvkova algoritmu}
 115
 116 K~dal¹ímu zlep¹ení dojde, kdy¾ nejprve spustíme $\log\log n$ cyklù Borùvkova algoritmu
 117 s~kontrahováním vrcholù, tímto dojde k~velkému sní¾ení poètu vrcholù.
 118
 119 \s{Algoritmus: Jarníkùv algoritmus~\#3 (pùvod neznámý)}
 120 \algo
 121 \:Provedeme $\log\log n$ cyklù upraveného Borùvkova algoritmu s~kontrahováním hran popsaného vý¹e.
 122 \:Pokraèujeme Jarníkovým algoritmem~\#2.
 123 \endalgo
 124
 125 \s{Èasová slo¾itost:}
 126 Slo¾itost první èásti je $\O(m\log\log n)$.
 127 Poèet vrcholù se po~první èásti algoritmu sní¾í na~$n'\leq n/\log n$ a slo¾itost druhé èásti bude
 128 tedy nanejvý¹ $\O(m+n\log n'/\log n)=\O(m)$. Nyní ji¾ máme lineární algoritmus i~pro grafy
 129 s~$m\geq n\log\log n$.
 130
 131 \h{Jarníkùv algoritmus s~omezením velikosti haldy}
 132
 133 Je¹tì vìt¹ího zrychlení dosáhneme, omezíme-li Jarníkovu algoritmu \#2 vhodnì
 134 velikost haldy a takto budeme bìhem jednoho Jarníkova algoritmu skládat pouze
 135 jednotlivé podkostøièky zastavené v rùstu pøeteèením haldy, podle kterých
 136 graf následnì skontrahujeme a budeme pokraèovat s mnohem men¹ím grafem.
 137
 138 \s{Algoritmus: Jarníkùv algoritmus~\#4 (Fredman, Tarjan)}
 139 \algo
 140 \:Opakuji, dokud mám netriviální $G$ (s alespoò jedou hranou).
 141 \::$t=\vert V_G\vert$.
 142 \::Zvolím $k=2^{2m/t}$ podle aktuálního $t$.
 143 \::$T=\emptyset$
 144 \::Opakuji, dokud existují vrcholy mimo $T$:
 145 \:::Najdu vrchol $v_0$ mimo $T$.
 146 \:::Spustím Jarníkùv alg. \#2 pro celý graf od $v_0$, zastavím ho, pokud:
 147 \global\algcnt=\itemcount
 148 \::::$\vert H\vert\geq k$ (pøekroèena vel. haldy) nebo
 149 \::::$H=\emptyset$ (do¹li sousedé) nebo
 150 \::::do $T$ jsem pøidal hranu oboustrannì incidentní s~hranami v~$T$ (pøipojil
 151 jsem novou podkostru k~nìjaké u¾ nalezené).
 152 \::Skontrahuji $G$ podle podkoster nalezených v~$T$.
 153 \endalgo
 154
 155 \s{Pozorování:}
 156 Ka¾dá z~nalezených podkoster v~$T$ je incidentní s~alespoò $k$ hranami (a~nebo
 157 algoritmus u¾ konèí).
 158 Jak to vypadá pro jednotlivá ukonèení:
 159 \numlist\ndotted
 160 \itemcount=\algcnt
 161 \:$\vert H\vert\geq k$ -- bylo u¾ pøidáno dost vrcholù.
 162 \:$H=\emptyset$ -- nalezena celá kostra, konèím.
 163 \:Pøipojím se k~u¾ existující podkostøe -- jen ji zvìt¹ím.
 164 \endlist
 165
 166 \s{Èasová slo¾itost:}
 167 Dùsledkem pozorování je, ¾e poèet podkoster v~jednom prùchodu je nanejvý¹
 168 $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$,
 169 prùchodù bude tedy nanejvý¹ $\log^* n$\foot{$\log^* n$ je inverzní funkce k~\uv{vì¾i
 170 z~mocnin}, èili $\min\{i:\log^{(i)} n<1 \}$, kde $\log^{(i)} n$ je $i$-krát iterovaný
 171 logaritmus.}, proto¾e prùchod s~$k>n$ bude u¾ urèitì poslední.
 172 Jeden vnìj¹í prùchod trvá $\O(m+t\log k)$, zvolím-li tedy $k=2^{2m/t}$, potom bude mít
 173 jeden prùchod slo¾itost $\O(m)$. Celková slo¾itost bude $\O(m\log^{*}n)$.
 174 Podrobnìj¹í analýza pak dá je¹tì o~nìco lep¹í výsledek, a~to $\O(m\beta(m,n))$, kde
 175 $\beta(m,n)=\min\{i:\log^{(i)}n<m/n\}$, co¾ opìt dává lineární algoritmus pro
 176 grafy s~$m\geq n\log^{(k)}n$ pro libovolnou konstantu $k$ ($\beta(m,n)$ tehdy vyjde konstantní).
 177
 178
 179 %\newbox\tombox\newdimen\tomwd
 180 %\setbox\tombox=\hbox{$\log\log\log\dots\log$}
 181 %\tomwd=\wd\tombox
 182 %\raise 7pt\hbox{$\underbrace{\box\tombox}\kern-\tomwd
 183 %\lower 16pt\hbox to\tomwd{$\hfill\log^{*}n$\hfill} n<1$},
 184 %\message{dim: \the\tomwd, \the\tombox}
 185
 186 \h{Dal¹í výsledky}
 187
 188 Chazelle popisuje algoritmus se slo¾itostí $\O(m\alpha(m,n))$. Podle Pettieho je mo¾né dosáhnout
 189 a¾ optima, tedy slo¾itosti $\O(T(m,n))$, kde $T$ je hloubka optimálního rozhodovacího stromu
 190 pro grafy na~$n$ vrcholech s $m$ hranami (není ale známo, jak ho sestrojit, ani jak je hluboký);
 191 zajímavé je, ¾e tento algoritmus funguje i na Pointer Machine, tak¾e pokud existuje lineární
 192 algoritmus na~MST, nepotøebuje sílu RAMu.\foot{O výpoèetních modelech viz pøí¹tí pøedná¹ka.}
 193
 194 \bye