9-decomp/9-decomp.tex

   1 \input ../sgr.tex
   2
   3 \hyphenation{mikro-strom mikro-stro-mo-vé}
   4
   5 \prednaska{9}{Dekompozice stromů}{}
   6
   7 V~této kapitole ukážeme několik datových struktur založených
   8 na~myšlence dekompozice problému na~dostatečně malé podproblémy,
   9 které už umíme (obvykle vhodným kódováním čísly) řešit v~konstantním
  10 čase.
  11
  12 \h{Union-Find Problem}
  13
  14 \s{Problém:} Udržování tříd ekvivalence: na~počátku máme $N$ jednoprvkových ekvivalenčních
  15 tříd, provádíme operace \<Find> (zjištění, zda dva prvky jsou ekvivalentní) a \<Union>
  16 (sloučení dvou tříd do~jedné). Také na~to lze pohlížet jako na~inkrementální udržování
  17 komponent souvislosti neorientovaného grafu: \<Union> je přidání hrany, \<Find> test,
  18 zda dva vrcholy leží v~téže komponentě. To se hodí v~mnoha algoritmech, kupříkladu
  19 v~Kruskalově algoritmu pro hledání minimální kostry.
  20
  21 \s{Triviální řešení:} Prvky každé třídy obarvíme unikátní barvou (identifikátorem
  22 třídy). Operace \<Find> porovnává barvy, \<Union> prvky jedné ze~sjednocovaných
  23 tříd přebarvuje.
  24
  25 Operace \<Find> tak pracuje v~konstantním čase, \<Union> může zabrat až lineární čas. Můžeme si
  26 pomoci tím, že vždy přebarvíme {\I menší} ze~slučovaných ekvivalenčních tříd (budeme
  27 si pro každou třídu pamatovat seznam jejích prvků a velikost). Tehdy může být každý
  28 prvek přebarven jen $\O(\log n)$-krát, jelikož každým přebarvením se alespoň zdvojnásobí
  29 velikost třídy, ve~které prvek leží. Posloupnost operací \<Union>, kterou vznikla třída
  30 velikosti~$k$, tak trvá $\O(k\log k)$, takže můžeme bezpečně prohlásit, že amortizovaná
  31 složitost operace \<Union> je $\O(\log n)$.
  32
  33 \s{Chytřejší řešení:} Každou třídu budeme reprezentovat zakořeněným stromem s~hranami
  34 orientovanými směrem ke~kořeni (jinými slovy pro každý prvek si pamatujeme jeho otce
  35 nebo že je to kořen). \<Find> nalezne kořeny stromů a porovná je, \<Union> připojí kořen
  36 jedné třídy pod kořen druhé. Aby stromy nedegenerovaly, přidáme dvě pravidla:
  37
  38 \itemize\ibull
  39 \:{\I Union dle ranku:} každý kořen $v$ si bude pamatuje svůj rank $r(v)$, což je nějaké
  40 přirozené číslo. Na~počátku jsou všechny ranky nulové. Pokud spojujeme
  41 dva stromy s~kořeny $v$, $w$ a $r(v)<r(w)$, připojíme $v$ pod~$w$ a rank zachováme.
  42 Pokud $r(v)=r(w)$, připojíme libovolně a nový kořen bude mít rank $r(v)+1$.%
  43 \foot{Stejně by fungovalo pravidlo {\I Union dle velikosti,} které připojuje menší
  44 strom pod větší, ale ranky máme raději, neb jsou skladnější a snáze se analyzují.}
  45
  46 \:{\I Komprese cest:} pokud z~vrcholu vystoupíme do~kořene (například
  47 během operace \<Find>), přepojíme všechny vrcholy na~cestě, po~které jsme prošli,
  48 rovnou pod kořen.
  49 \endlist
  50
  51 Pro účely analýzy struktury budeme uvažovat také ranky ostatních vrcholů -- každý vrchol
  52 si ponese svůj rank z~doby, kdy byl naposledy kořenem. Struktura se ovšem
  53 podle ranků vnitřních vrcholů nijak neřídí a nemusí si je ani pamatovat.
  54 Stromu s~kořenem ranku~$r$ budeme zkráceně říkat {\I strom ranku~$r$.}
  55
  56 \s{Invariant~C:} Na každé cestě z~vrcholu do~kořene příslušného stromu ranky
  57 ostře rostou. Jinými slovy rank vrcholu, který není kořen, je menší, než je rank
  58 jeho otce.
  59
  60 \proof
  61 Na počátku (pro jednovrcholové stromy) tvrzení jistě platí.
  62 Nechť provedeme Union, který připojí vrchol~$v$ pod~$w$. Cesty do~kořene z~vrcholů,
  63 které ležely pod~$w$, zůstanou zachovány, pouze se vrcholu~$w$ případně
  64 zvýší rank. Cesty z~vrcholů pod~$v$ se rozšíří o~hranu~$vw$, na které rank
  65 v~každém případě roste.
  66 Komprese cest nahrazuje otce vrcholu jeho vzdálenějším předkem, takže se rank
  67 otce může jedině zvýšit.
  68 \qed
  69
  70 \s{Invariant~R:} Strom ranku~$r$ obsahuje alespoň $2^r$ vrcholů.
  71
  72 \proof
  73 Indukcí podle času. Pro jednovrcholové stromy o~nulovém ranku tvrzení platí.
  74 Nechť připojíme vrchol~$v$ pod vrchol~$w$. Je-li $r(v)<r(w)$, rank stromu
  75 zůstane zachován a strom se ještě zvětší. Je-li $r(v)=r(w)$, rank stromu
  76 se zvětší o~1, ale z~indukce víme, že oba spojované stromy měly alespoň
  77 $2^{r(v)}$ vrcholů, takže jejich spojením vznikne strom o~alespoň $2^{r(v)+1}$
  78 vrcholech. Komprese cest zasahuje pouze do~vnitřní struktury stromu, ranky
  79 ani velikosti stromů nemění.
  80 \qed
  81
  82 \s{Důsledek:} Rank každého stromu je $\O(\log n)$, takže rank každého vnitřního
  83 vrcholu taktéž. Díky invariantu~C strávíme výstupem z~každého vrcholu do~kořene
  84 také čas $\O(\log n)$, takže logaritmická je i složitost operací \<Union> a \<Find>.
  85
  86 K~tomu nám ovšem stačilo samotné pravidlo Union podle ranku, o~kompresi cest
  87 jsme zatím dokázali pouze to, že složitost v~nejhorším případě nezhoršuje.%
  88 \foot{Mimochodem, Komprese cest samotná by také na~složitost $\O(\log n)$ amortizovaně stačila \cite{tarjan84setunion}.}
  89 Kombinace obou metod se ve~skutečnosti chová mnohem lépe:
  90
  91 \s{Věta:} (Tarjan, van Leeuwen \cite{tarjan84setunion})
  92 Posloupnost $m$~operací \<Union> a \<Find> provedená na~prázdné struktuře s~$n$ vrcholy
  93 trvá $\O(n + m\alpha(m,n))$, kde $\alpha$ je inverzní Ackermannova funkce.%
  94 \foot{Je známo \cite{fredman:cellprobe}, že asymptoticky lepší složitosti nelze dosáhnout,
  95 a~to ani v~modelu silnějším než RAM. Námi uváděný algoritmus si téměř vystačí
  96 s~Pointer Machine, jen porovnávání ranků z~tohoto modelu vybočuje. Složitost
  97 operací v~nejhorším případě je obecně horší, je znám dolní odhad $\Omega(\log n/\log\log n)$;
  98 více viz Alstrup \cite{alstrup:worstuf}.}
  99
 100 Důkaz této věty neuvádíme, jelikož je technicky dosti náročný. Místo toho podobnou
 101 metodou ukážeme trochu slabší výsledek s~iterovaným logaritmem:
 102
 103 \s{Věta':} Ve~struktuře s~$n$ prvky trvá provedení posloupnosti $m$~operací
 104 \<Union> a \<Find> $\O((n+m)\cdot\log^* n)$.
 105
 106 \def\up{\mathop{\uparrow}}
 107
 108 \s{Definice:} {\I Věžovou funkci} $2\up k$ definujeme následovně: $2\up 0=1$,
 109 $2\up (k+1)=2^{2\up k}$.
 110
 111 Funkce $2\up k$ je tedy $k$-krát iterovaná mocnina dvojky a $\log^*$ je funkce
 112 k~této funkci inverzní.
 113
 114 Vrcholy ve~struktuře si nyní rozdělíme podle jejich ranků:
 115 $k$-tá skupina bude tvořena těmi vrcholy, jejichž rank je od~$2\up (k-1)+1$ do~$2\up k$. Vrcholy jsou
 116 tedy rozděleny do~$1+\log^*\log n$ skupin. Odhadněme nyní shora počet vrcholů v~$k$-té
 117 skupině.
 118
 119 \s{Invariant~S:} V~$k$-té skupině leží nejvýše $n/(2\up k)$ vrcholů.
 120
 121 \proof
 122 Nejprve ukážeme, že vrcholů s~rankem~$r$ je nejvýše $n/2^r$. Kdybychom nekomprimovali
 123 cesty, snadno to plyne z~invariantů~C a~R: každému vrcholu ranku~$r$ přiřadíme všech
 124 jeho alespoň $2^r$ potomků. Jelikož ranky na cestách směrem ke~kořeni rostou, žádného
 125 potomka jsme nemohli přiřadit více vrcholům. Komprese cest ovšem nemůže invariant
 126 porušit, protože nemění ranky ani rozhodnutí, jak proběhne který \<Union>.
 127
 128 Teď už stačí odhad $n/2^r$ sečíst přes všechny ranky ve~skupině:
 129 $$
 130 {n \over 2^{2\up(k-1)+1}} + {n \over 2^{2\up(k-1)+2}} + \cdots + {n \over 2^{2\up k}} \le
 131 {n \over 2^{2\up(k-1)}} \cdot \sum_{i=1}^\infty {1 \over 2^i} =
 132 {n \over 2^{2\up(k-1)}} \cdot 1 =
 133 {n \over 2\up k}.
 134 $$
 135 \qed
 136
 137 \>{\sl Důkaz věty:}
 138 Operace \<Union> a \<Find> potřebují nekonstantní čas pouze na~vystoupání
 139 po~cestě ze~zadaného vrcholu~$v$ do~kořene stromu. Čas strávený na~této cestě
 140 je přímo úměrný počtu hran cesty. Celá cesta je přitom rozpojena a všechny
 141 vrcholy ležící na~ní jsou přepojeny přímo pod~kořen stromu.
 142
 143 Hrany cesty, které spojují vrcholy z~různých skupin (takových je $\O(\log^* n)$),
 144 naúčtujeme právě prováděné operaci. Celkem jimi tedy strávíme čas $\O(m\log^*n)$.
 145 Zbylé hrany budeme počítat přes celou dobu běhu algoritmu a účtovat je vrcholům.
 146
 147 Uvažme vrchol~$v$ v~$k$-té skupině, jehož rodič leží také v~$k$-té skupině.
 148 Jelikož hrany na cestách do~kořene ostře rostou, každým přepojením vrcholu~$v$ rank jeho
 149 rodiče vzroste. Proto po nejvýše $2\up k$ přepojeních se bude rodič vrcholu~$v$ nacházet
 150 v~některé z~vyšších skupin. Jelikož rank vrcholu~$v$ se už nikdy nezmění, bude hrana z~$v$
 151 do~jeho otce již navždy hranou mezi skupinami. Každému vrcholu v~$k$-té skupině tedy naúčtujeme
 152 nejvýše $2\up k$ přepojení a jelikož, jak už víme, jeho skupina obsahuje nejvýše $n/(2\up k)$ vrcholů,
 153 naúčtujeme celé skupině čas $\O(n)$ a všem skupinám dohromady $\O(n\log^* n)$.
 154 \qed
 155
 156 \h{Union-Find s~předem známými Uniony}
 157
 158 Dále nás bude zajímat speciální varianta Union-Find problému, v~níž dopředu známe
 159 posloupnost Unionů, čili strom, který spojováním komponent vznikne.\foot{Kdy se to hodí?
 160 Třeba v~Thorupově lineárním algoritmu \cite{thorup:usssp} na~nejkratší cesty nebo
 161 ve~Weiheho taktéž lineárním algoritmu \cite{weihe:paths} na~hledání hranově disjunktních
 162 cest v~rovinných grafech.}
 163 Jiná interpretace téhož (jen pozpátku) je dekrementální udržování komponent
 164 souvislosti lesa: na~počátku je dán les, umíme smazat hranu a otestovat, zda jsou
 165 dva vrcholy v~témže stromu.
 166
 167 Popíšeme algoritmus,
 168 který po~počátečním předzpracování v~čase $\O(n)$ zvládne \<Union> i \<Find> v~amortizovaně
 169 konstantním čase. Tento algoritmus je kombinací dekompozic popsaných Alstrupem \cite{alstrup97optimal,alstrup98marked}.
 170
 171 \s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakořeněný strom $T$ o~$n$ vrcholech
 172 definujeme:
 173 \itemize\ibull
 174 \:{\I Kořeny mikrostromů} budou nejvyšší vrcholy v~$T$, pod~nimiž je nejvýše $\log n$ listů
 175 a které nejsou kořenem celého~$T$.
 176 \:{\I Mikrostromy} leží v~$T$ od~těchto kořenů níže.
 177 \:{\I Spojovací hrany} vedou z~kořenů mikrostromů do~jejich otců.
 178 \:{\I Makrostrom} je tvořen zbývajícími vrcholy a hranami stromu~$T$.
 179 \endlist
 180
 181 \s{Pozorování:} Každý mikrostrom má nejvýše $\log n$ listů. Pod každým listem makrostromu leží
 182 alespoň jeden mikrostrom (může jich být i více, viz dekompozice hvězdy na~obrázku), takže
 183 listů makrostromu je nejvýše $n/\log n$.
 184
 185 Vnitřních vrcholů makro- i mikrostromů ale může být nešikovně mnoho, protože se ve~stromech mohou
 186 vyskytovat dlouhé cesty. Pomůžeme si snadno: každou cestu si budeme pamatovat zvlášť a ve~stromu
 187 ji nahradíme hranou, která bude vložena právě tehdy, když budou přítomny všechny hrany cesty.
 188
 189 \s{Příklad:} Následující obrázek ukazuje dekompozici několika stromů za~předpokladu,
 190 že $\log n=4$. Vrcholy mikrostromů jsou černé, makrostromu bílé. Spojovací hrany kreslíme tečkovaně,
 191 hrany komprimovaných cest tučně.
 192
 193 \medskip
 194 \fig{mima.epdf}{}
 195
 196 \s{Algoritmus pro cesty:} Cestu délky~$l$ rozdělíme na~úseky délky $\log n$, pro něž si uložíme
 197 množiny již přítomných hran (po~bitech jako čísla). Pak si ještě pamatujeme zkomprimovanou cestu (hrany
 198 odpovídají úsekům a jsou přítomny právě tehdy, jsou-li přítomny všechny hrany příslušného úseku)
 199 délky $l/\log n$ a pro ni \uv{přebarvovací} strukturu pro Union-Find.
 200
 201 \>$\<Union>(x,y)$ (přidání hrany $e=xy$ do~cesty):
 202 \algo
 203 \:Přidáme $e$ do množiny hran přítomných v~příslušném úseku.
 204 \:Pokud se tím úsek naplnil, přidáme odpovídající hranu do~zkomprimované cesty.
 205 \endalgo
 206
 207 \>$\<Find>(x,y):$
 208 \algo
 209 \:Pokud $x$ a $y$ jsou v~témže úseku, otestujeme bitovými operacemi, zda
 210   jsou všechny hrany mezi $x$ a $y$ přítomny.
 211 \:Pokud jsou v~různých úsecích, rozdělíme cestu z~$x$ do~$y$ na~posloupnost celých úseků,
 212   na~které nám odpoví zkomprimovaná cesta, a~dva dotazy v~krajních částečných úsecích.
 213 \endalgo
 214
 215 Operace uvnitř úseků pracují v~čase $\O(1)$, operace na~zkomprimované cestě v~$\O(\log l)$
 216 amortizovaně, ale za~dobu života struktury je jich $\O(l/\log n)=\O(l/\log l)$, takže celkově zaberou lineární čas.
 217
 218 \s{Komprese cest:} Operace na~mikro/makro-stromech budeme následujícím způsobem
 219 převádět na~operace s~jejich cestově komprimovanými podobami a na~operace s~cestovými strukturami:
 220
 221 \>$\<Union>(x,y)$:
 222 \algo
 223 \:Pokud $e=xy$ leží uvnitř nějaké cesty, přidáme ji do~cesty, což buďto způsobí
 224   přidávání jiné hrany, a~nebo už jsme hotovi.
 225 \:Provedeme \<Union> v~komprimovaném stromu.
 226 \endalgo
 227
 228 \>$\<Find>(x,y)$:
 229 \algo
 230 \:Pokud $x$ a $y$ leží uvnitř jedné cesty, zeptáme se cestové struktury a končíme.
 231 \:Pokud $x$ leží uvnitř nějaké cesty, zjistíme dotazem na~cestovou strukturu,
 232   ke~kterému krajnímu vrcholu cesty je připojen, a~$x$ nahradíme tímto vrcholem.
 233   Není-li připojen k~žádnému, je~evidentně odpověď na~celý \<Find> negativní;
 234   pokud k~oběma, vybereme si libovolný, protože jsou stejně v~cestově komprimovaném
 235   stromu spojeny hranou. Analogicky pro~$y$.
 236 \:Zeptáme se struktury pro komprimovaný strom.
 237 \endalgo
 238
 239 \s{Algoritmus pro mikrostromy:} Po~kompresi cest má každý mikrostrom nejvýše $2\log n$
 240 vrcholů, čili také nejvýše tolik hran. Hrany si očíslujeme přirozenými čísly, každou
 241 množinu hran pak můžeme reprezentovat $(2\log n)$-bitovým číslem a množinové operace
 242 provádět pomocí bitových v~konstantním čase.
 243
 244 Pro každý mikrostrom si předpočítáme pro všechny jeho vrcholy~$v$ množiny~$P_v$ hran ležících
 245 na~cestě z~kořene mikrostromu do~$v$. Navíc si budeme pro celý mikrostrom pamatovat množinu
 246 přítomných hran~$F$.
 247
 248 \>$\<Union>(x,y):$
 249
 250 \algo
 251 \:Najdeme pořadové číslo $i$ hrany $xy$ (máme předpočítané).
 252 \:$F \leftarrow F \cup \{i\}$.
 253 \endalgo
 254
 255 \>$\<Find>(x,y):$
 256
 257 \algo
 258 \:$P \leftarrow P_x \mathop{\Delta} P_y$ (množina hran ležících na~cestě z~$x$ do~$y$).
 259 \:Pokud $P\setminus F=\emptyset$, leží $x$ a $y$ ve~stejně komponentě, jinak ne.
 260 \endalgo
 261
 262 \s{Algoritmus pro celý problém:} Strom rozložíme na~mikrostromy, makrostrom a spojovací
 263 hrany. V~mikrostromech i makrostromu zkomprimujeme cesty. Pro cesty a mikrostromy použijeme
 264 výše popsané struktury, pro každou spojovací hranu si budeme pamatovat jen značku,
 265 zda je přítomna, a pro makrostrom přebarvovací strukturu.
 266
 267 \>$\<Union>(x,y)$:
 268
 269 \algo
 270 \:Pokud $e=xy$ je spojovací, poznamenáme si, že je přítomna, a~končíme.
 271 \:Nyní víme, že $e$ leží uvnitř mikrostromu nebo makrostromu, a~tak provedeme \<Union>
 272    na~příslušné struktuře.
 273 \endlist
 274
 275 \>$\<Find>(x,y)$:
 276
 277 \algo
 278 \:Leží-li $x$ a $y$ v~jednom mikrostromu, zeptáme se struktury pro~mikrostrom.
 279 \:Je-li $x$ uvnitř mikrostromu, zeptáme se mikrostruktury na~spojení s~kořenem mikrostromu.
 280   Není-li, odpovíme {\sc ne}, stejně jako když není přítomna příslušná spojovací hrana.
 281   Jinak $x$ nahradíme listem makrostromu, do~kterého spojovací hrana vede. Podobně pro~$y$.
 282 \:Odpovíme podle struktury pro makrostrom.
 283 \endalgo
 284
 285 \s{Analýza:} Operace \<Find> trvá konstantní čas, protože se rozloží na~$\O(1)$ \<Find>ů
 286 v~dílčích strukturách a každý z~nich trvá konstantně dlouho. Všech $n$ operací \<Union>
 287 trvá $\O(n)$, jelikož způsobí $\O(n)$ amortizovaně konstantních operací s~mikrostromy, spojovacími
 288 hranami a cestami a $\O(n/\log n)$ operací s~makrostromem, které trvají $\O(\log n)$ amortizovaně
 289 každá.%
 290 \foot{To je v~průměru $\O(1)$ na~operaci a dokonce i amortizovaně, pokud necháme inicializaci
 291 struktury, která je lineární, naspořit potenciál $\O(n)$, ze~kterého budeme průběžně platit
 292 slučování v~makrostromu.}
 293
 294 \s{Cvičení:} Zkuste pomocí dekompozice vyřešit následující problém: je dán strom,
 295 jehož každý vrchol může být označený. Navrhněte datovou strukturu, která bude umět
 296 v~čase $\O(\log\log n)$ označit nebo odznačit vrchol a v~čase $\O(\log n/\log\log n)$ najít
 297 nejbližšího označeného předchůdce.
 298
 299 \h{Fredericksonova clusterizace}
 300
 301 Mikro/makro-stromová dekompozice není jediný způsob, jak stromy rozkládat. Někdy
 302 se více hodí následující myšlenka:
 303
 304 \s{Definice:} {\I (Fredericksonova clusterizace)} Nechť $k\ge 1$ je přirozené číslo
 305 a $T$~strom s~maximálním stupněm nejvýše~3. Pak $k$-clusterizací stromu~$T$
 306 nazveme libovolný rozklad $V_1\cup\ldots\cup V_t$ množiny~$V(T)$, pro který platí:
 307 \itemize\ibull
 308 \:Podgrafy stromu~$T$ indukované jednotlivými~$V_i$ jsou souvislé.
 309 Těmto podgrafům budeme říkat {\I clustery} a značit je~$C_i$.
 310 \:Z~každého clusteru vedou nejvýše 3~hrany do sousedních clusterů.
 311 Takovým hranám říkáme {\I vnější,} jejich počet je {\I vnější stupeň} clusteru $\<ed>(C_i)$.
 312 Hrany uvnitř clusterů nazveme {\I vnitřní.}
 313 \:Nechť $\vert C_i\vert$ značí počet vrcholů clusteru~$C_i$.
 314 Pak pro všechny clustery platí $\vert C_i\vert \le k$
 315 a pro clustery vnějšího stupně~3 dokonce $\vert C_i\vert = 1$.
 316 \:Žádné dva sousední clustery není možné sloučit.
 317 \endlist
 318
 319 \s{Úmluva:}
 320 Clustery vnějšího stupně~0 se nazývají {\I izolované,}
 321 stupně~1 {\I listové,}
 322 stupně~2 {\I cestové} a
 323 stupně~3 {\I větvicí.}
 324
 325 \s{Pozorování:} Nechť $C$ a~$D$ jsou sousední clustery (bez újmy na obecnosti $\<ed>(C) \ge \<ed>(D)$).
 326 Kdy je lze sloučit? Především $\vert C\vert + \vert D\vert$ musí být nejvýše rovno~$k$. Pak mohou
 327 nastat následující případy:
 328 \itemize\ibull
 329 \:Pokud~$C$ i~$D$ jsou listové, lze je sloučit do jednoho izolovaného clusteru.
 330 \:Pokud~$C$ je cestový a $D$~listový, lze je sloučit do listového clusteru.
 331 \:Pokud~$C$ i~$D$ jsou cestové, lze je sloučit do cestového clusteru.
 332 \:Pokud~$C$ je větvicí a $D$~listový, lze je sloučit do cestového clusteru.
 333 \:V~ostatních případech slučovat nelze, neboť by vznikl cluster vnějšího stupně~4
 334   nebo stupně~3 s~více než jedním vrcholem.
 335 \endlist
 336
 337 \s{Věta:} (Frederickson \cite{frederickson91ambivalent}) Každá $k$-clusterizace stromu~$T$
 338 na $n$~vrcholech obsahuje $\O(n/k)$ clusterů.
 339
 340 \proof
 341 Pokud clusterizace obsahuje pouze izolované nebo listové clustery, pak je konstantně
 342 velká a tvrzení triviálně platí.
 343
 344 Pokud navíc obsahuje cestové clustery, musí být clustery propojeny do jedné cesty,
 345 která začíná a končí listovými clustery a ostatní clustery jsou cestové. Cestové
 346 clustery rozdělíme na velké (alespoň $k/2$ vrcholů) a malé (ostatní). Všimneme si,
 347 že malé spolu nemohou sousedit. Velkých je přitom nejvýše $n/k$, takže malých
 348 nejvýše $n/k+1$.
 349
 350 Zbývá obecný případ, v~němž jsou i větvicí clustery. Uvažme clusterizační strom~$S$:
 351 jeho vrcholy odpovídají clusterům, hrany externím hranám mezi nimi. Tento strom zakořeňme
 352 v~libovolném větvicím clusteru.
 353
 354 Pokud ve~stromu~$S$ nahradíme každou nevětvící se cestu hranou, vznikne nějaký
 355 komprimovaný strom~$S'$. V~něm už jsou pouze listové clustery (coby listy) a
 356 větvicí clustery (jako vnitřní vrcholy).
 357
 358 Nyní si všimneme, že pro každý list~$\ell$ stromu~$S$ platí, že tento cluster
 359 spolu s~cestovými clustery nad ním (které se schovaly do hrany mezi~$\ell$ a jeho
 360 otcem) musí mít velikost alespoň~$k$. V~opačném případě by totiž bylo možné
 361 tyto clustery společně s~větvicím clusterem nad nimi sloučit do jediného clusteru,
 362 což by porušilo poslední podmínku z~definice clusterizace.
 363
 364 Proto strom~$S'$ obsahuje nejvýše $n/k$ listů. A~jelikož všechny jeho vnitřní
 365 vrcholy mají alespoň~2 syny, musí být vnitřních vrcholů také nanejvýš $n/k$.
 366
 367 Zbývá započítat cestové clustery. Uvažme hranu~$e$ stromu~$S'$ a cestové clustery,
 368 které se do ní zkomprimovaly. Už víme, že je-li celková velikost těchto clusterů~$r$,
 369 může jich být nanejvýš $2r/k + 1$. A~jelikož clustery jsou disjunktní, v~součtu
 370 přes všechny hrany~$e$ dostaneme $2n/k + \hbox{počet hran stromu~$S'$} = \O(n/k)$.
 371
 372 Clusterů všech typů je tedy dohromady $\O(n/k)$.
 373 \qed
 374
 375 \s{Věta:} (Frederickson \cite{frederickson91ambivalent}) Pro každé~$k$ lze $k$-clusterizaci
 376 stromu o~$n$~vrcholech najít v~čase $\O(n)$.
 377
 378 \proof
 379 Clusterizaci lze najít upraveným hledáním do hloubky, ale při tom je nutné řešit
 380 mnoho různých případů slučování clusterů. Místo toho použijeme následující
 381 hladový algoritmus.
 382
 383 Nejprve vytvoříme z~každého vrcholu triviální cluster. Taková clusterizace
 384 splňuje všechny podmínky kromě poslední. Budeme tedy clustery hladově slučovat.
 385
 386 Pořídíme si frontu clusterů, u~nichž jsme ještě nezkontrolovali slučitelnost.
 387 Na počátku do ní umístíme všechny clustery. Pak vždy odebereme cluster, prozkoumáme
 388 jeho sousedy a pokud mezi nimi je nějaký, s~nímž lze slučovat, tak to provedeme.
 389 Nový cluster uložíme do fronty, oba staré z~fronty odstraníme.
 390
 391 Všimneme si, že při každé kontrole poklesne velikost fronty o~1 -- buďto jsme
 392 neslučovali a zmizel pouze kontrolovaný cluster, anebo slučovali, ale pak zmizely
 393 dva clustery a přibyl jeden. Jelikož kontrolu i sloučení zvládneme v~konstantním
 394 čase, celý algoritmus doběhne v~čase $\O(n)$.
 395 \qed
 396
 397 \s{Použití:} Předchozí variantu Union-Find problému bychom také mohli vyřešit nahrazením
 398 vrcholů stupně většího než~3 \uv{kruhovými objezdy bez jedné hrany},
 399 nalezením $(\log n)$-clusterizace, použitím bitové reprezentace množin uvnitř clusterů
 400 a přebarvovací struktury na~hrany mezi clustery.
 401
 402 \h{Stromoví předchůdci}
 403
 404 \s{Problém:} {\I (Least Common Ancestor alias LCA)} Chceme si předzpracovat zakořeněný strom~$T$
 405 tak, abychom dokázali pro libovolné dva vrcholy $x,y$ najít co~nejrychleji jejich nejbližšího
 406 společného předchůdce.
 407
 408 \s{Triviální řešení LCA:}
 409 \itemize\ibull
 410 \:Vystoupáme z~$x$ i $y$ do~kořene, označíme vrcholy na~cestách a kde se poprvé
 411   potkají, tam je hledaný předchůdce. To je lineární s~hloubkou a nepotřebuje
 412   předzpracování.
 413 \:Vylepšení: Budeme stoupat z~$x$ a $y$ střídavě. Tak potřebujeme jen lineárně mnoho
 414   kroků vzhledem ke~vzdálenosti společného předchůdce.
 415 \:Předpočítáme všechny možnosti: předzpracování $\O(n^2)$, dotaz $\O(1)$.
 416 \:\dots\ co dál?
 417 \endlist
 418
 419 \>Věrni vtipům o~matfyzácích a článku \cite{bender00lca} převedeme raději tento problém na~jiný.
 420
 421 \s{Problém:} {\I (Range Minimum Query alias RMQ)} Chceme předzpracovat posloupnost čísel
 422 $a_1,\ldots a_n$ tak, abychom uměli rychle počítat $\min_{x\le i\le y} a_i$.%
 423 \foot{Všimněte si, že pro sumu místo minima je tento problém velmi snadný.}
 424
 425 \s{Lemma:} LCA lze převést na~RMQ s~lineárním časem na~předzpracování a konstantním
 426 časem na~převod dotazu.
 427
 428 \proof Strom projdeme do~hloubky a pokaždé, když vstoupíme do~vrcholu (ať již poprvé nebo se do~něj vrátíme),
 429 zapíšeme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejvyšší vrchol mezi libovolnou
 430 návštěvou~$x$ a libovolnou návštěvou~$y$.
 431 \qed
 432
 433 \s{Triviální řešení RMQ:}
 434 \itemize\ibull
 435 \:Předpočítáme všechny možné dotazy: předzpracování $\O(n^2)$, dotaz $\O(1)$.
 436 \:Pro každé $i$ a $j\le \log n$ předpočítáme $m_{ij} = \min\{ a_i, a_{i+1}, \ldots, a_{i+2^j-1} \}$,
 437 čili minima všech bloků velkých jako nějaká mocnina dvojky. Když se poté někdo zeptá
 438 na~minimum bloku $a_i,a_{i+1},\ldots,a_{j-1}$, najdeme největší~$k$ takové, že $2^k < j-i$
 439 a vrátíme:
 440 $$\min( \min\{ a_i, \ldots, a_{i+2^k-1} \}, \min\{ a_{j-2^k}, \ldots, a_{j-1} \} ).$$
 441 Tak zvládneme dotazy v~čase $\O(1)$ po~předzpracování v~čase $\O(n\log n)$.
 442 \endlist
 443
 444 My si ovšem všimneme, že náš převod z~LCA vytváří dosti speciální instance problému RMQ,
 445 totiž takové, v~nichž je $\vert a_i - a_{i+1} \vert = 1$. Takovým instancím budeme
 446 říkat RMQ${\pm}1$ a budeme je umět řešit šikovnou dekompozicí.
 447
 448 \s{Dekompozice} pro RMQ${\pm}1$: Vstupní posloupnost rozdělíme na~bloky velikosti $b=1/2\cdot \log n$,
 449 každý dotaz umíme rozdělit na~část týkající se celých bloků a maximálně dva dotazy na~části bloků.
 450
 451 Všimneme si, že ačkoliv bloků je mnoho, jejich možných typů (tj. posloupností klesání
 452 a stoupání) je pouze $2^{b-1}\le\sqrt n$ a bloky téhož typu se liší pouze posunutím
 453 o~konstantu. Vybudujeme proto kvadratickou strukturu pro jednotlivé typy a pro každý
 454 blok si zapamatujeme, jakého je typu a jaké má posunutí. Celkem strávíme čas
 455 $\O(n + \sqrt n \cdot \log^2 n) = \O(n)$ předzpracováním a $\O(1)$ dotazem.
 456
 457 Mimo to ještě vytvoříme komprimovanou posloupnost, v~níž každý blok nahradíme
 458 jeho minimem. Tuto posloupnost délky $n/b$ budeme používat pro části dotazů
 459 týkající se celých bloků a připravíme si pro ni \uv{logaritmickou} variantu
 460 triviální struktury. To nás bude stát $\O(n/b\cdot\log (n/b))=\O(n/\log n\cdot\log n)=\O(n)$ na~předzpracování
 461 a $\O(1)$ na~dotaz.
 462
 463 Tak jsme získali algoritmus pro RMQ${\pm}1$ s~konstantním časem na~dotaz po~lineárním
 464 předzpracování a výše zmíněným převodem i algoritmus na~LCA se stejnými parametry.
 465 Ještě ukážeme, že převod může fungovat i v~opačném směru, a~tak můžeme získat
 466 i konstantní/lineární algoritmus pro obecné RMQ.
 467
 468 \s{Definice:} {\I Kartézský strom} pro posloupnost $a_1,\ldots,a_n$ je strom,
 469 jehož kořenem je minimum posloupnosti, tj. nějaké $a_j=\min_i a_i$, jeho levý podstrom je
 470 kartézský strom pro $a_1,\ldots,a_{j-1}$ a pravý podstrom kartézský strom pro $a_{j+1},\ldots,a_n$.
 471
 472 \s{Lemma:} Kartézský strom je možné zkonstruovat v~lineárním čase.
 473
 474 \proof Použijeme inkrementální algoritmus. Vždy si budeme pamatovat
 475 kartézský strom pro již zpracované prvky a pozici posledního zpracovaného
 476 prvku v~tomto stromu. Když přidáváme další prvek, hledáme místo, kam ho
 477 připojit, od~tohoto označeného prvku nahoru. Povšimněme si, že vzhledem
 478 k~potenciálu rovnému hloubce označeného prvku je časová složitost přidání
 479 prvku amortizovaně konstantní.
 480 \qed
 481
 482 \s{Lemma:} RMQ lze převést na~LCA s~lineárním časem na~předzpracování a konstantním
 483 časem na~převod dotazu.
 484
 485 \proof Sestrojíme kartézský strom a RMQ převedeme na~LCA v~tomto stromu.
 486 \qed
 487
 488 Výsledky této podkapitoly můžeme shrnout do~následující věty:
 489
 490 \s{Věta:} Problémy LCA i RMQ je možné řešit v~konstantním čase na~dotaz
 491 po~předzpracování v~lineárním čase.
 492
 493 \s{Cvičení:} Vymyslete jednodušší strukturu pro RMQ, víte-li, že všechny dotazy budou na~intervaly stejné délky.
 494
 495 \references
 496 \bye