\input ../sgr.tex

\prednaska{10}{Dekompozice stromù}{zapsal Ale¹ ©nupárek}

\h{Union-Find problem}
Na Uion-Find problem (UF) mù¾eme nahlí¾et ze více stran (udr¾ování ekvivalencí, 
inkrementální souvislost grafu). K èemu je to dobré? 
Napøíklad v Kruskalovì algoritmu pro hledání minimálních koster v grafu.
\h{Udr¾ování tøíd ekvivalence }
Mìjme nìjakou mno¾inu M, která se dá rozlo¾it na k ekvivalentních podmon¾in (tøídy ekvivalence). Na mno¾iòe M chceme provádìt 
dvì operace: jsou p,q z M ekvivalentní (ve stejné tøídì ekvivalence)? (find(p,q)) Dále chceme umìt spojit dvì tøídy ekvivalence do jedné (union(p,q)).
\h{Inkrementální idr¾ování komponent souvislosti grafu}
Jedná se o pøipad podobný udr¾ování tøíd ekvivalence. Tentokrát mnou¾inou M bude mno¾ina vrcholù V grafu G (V,E). 
Za »øídy ekvivalence budou jednotlivé komponenty souvislosti grafu G. Operace find nám øekne o dvou vrcholech nachází-li
se ve stejné komponen»e, èi nikoliv. Operace union nám spojí dvì komponenty do jedné pøidáním hrany. Pokud pøipustíme mazání hran, 
øe©ení problému je výraznì te¾¹í.

\h{Bì¾ná implementace }
Ka¾dé tøídì ekvivalence pøiøadíme unikátní barvu, kterou obarvíme její prvky. Pro operaci find staèí porovnat barvy prvkù. 
Pro operaci union dvou komponent je nutné pøebarvit obì na stejnou barvu. Budeme pøebarvovat 
v¾dy tu men¹í pak celková operace union bude trvat $\O(n\log(n) + m)$. (Ka¾dé pøebarvení minimálnì zdvojnásobí velikost nové komponenty.)
\h {Chytøej¹í implementace }
Budeme-li prvky za stejné tøídy reprezentovat ve jednom stromì (synové mají ukazatel svého otce), operaci find
provedeme prùchodem ze zadaných prvkù do koøene. Prvky jsou ve stejné komponentì souvislosti, pokud mají stejného otce.
Operace union bude spojení dvou stromù do jednoho (otec jednoho stromu se zavìsí pod listy druhého). 
Takto definovaný union nemusí garantovat logaritmickou slo¾itost pro find, 
v extrémním pøipadì mù¾e strom mít lineární hloubku vzhledem k poètu vrcholù.

Degeneraci stromu lze zabránit pøidánim podmínky urèující, jaký strom bude dole.
První mmo¾nost (union by size) je povìsit dolu vìtsí strom.
Druhá mo¾nost (union by rank) je ka¾dému vrcholu nastavit na zaèátku nìjaký rank (tøeba 1). Pokud je $r1<r2$ pak strom s r1 povìsíme dolu.
Pokud $r1=r2$ pak ve slouèeném stromù zvý¹íme v koøeni rank o 1. Informace o ranku nám zabere ménì pamìti ne¾ o velikosti stromu.

Dal¹i mo¾nost pro zkrácení vý¹ky stromu je path compression. Pøi operaci find si pamatujeme pro¹lé vrcholy a pøesmìrujeme 
jejich ukazatele na otce na koøen.

\s{Vìta: } UF s Union by size nebo Union by rank s path compression mají amortizovanì 
slo¾itost $\O(n\alpha(n))$, kde $\alpha(n)$ je inverzní funkce k Ackermanovì funkci. ($\alpha(poèet atomù ve vesmíru)=5$)

\h {Microtree/Macrotree decomposition}

\s{Otázka: } Je mo¾né provádìt UF v lep¹ím èase kdy¾ bude pøedem znám výsledný strom?

Cíl: UF lze za pomoci preprocesingu v èase $\O(n)$  zvládnout amortizovanì v èase $\O(1)$ na U,F.

\h{Clusterizace}
\s {Definice: } Nech» G je je graf kde $\forall v \in V(G): deg(v)<=3$ a $c \in N$ pak c-clusterizací grafu G je rozklad
G na podgrafy na podgrafy G1,G2 ... Gk s následujícimi vlastnostmi:
\itemize\ibull
\: $\forall v  \in V \exists !\ i: v \in C_i$
\: $\forall i\  C_i\leq C$
\: $\forall i$ vnìj¹i stupeò $C\leq3$, pokud $C_i=3$ pak $\|C_i\|=1$
\: ¾ádné dva sousední clustery nelze spojit
\endlist

Co udìlat se stromem, ve kterém existuje vrchol se stupnìm vìt¹im ne¾ 3? Pou¾ijeme French trick.
V¹echny vrcholy s vy¹¹im stupnìm jak 3, rozdìlíme na více vrcholù se stupnìm 3 spojených cestou. 
Tato ùprava nám asymptoticky nezmìní èasovou slo¾itost UF o proti pùvodnímu stromu.


\s{Lemma: } Pro ka¾dou C-clusterizaci n-vrcholového stromu je  $\O(n/C)$ clusterù.

\s{Vìta: } Pro ka¾dé C lze C-clusterizaci (splòujíci pøedchozí lemma) najít v èase $\O(n)$.

\s{Dùkaz: } za pomoci DFS ...
\h{Jednodu¹¹í clusterizace}
Pøedpokládejme, ¾e máme zakoøeòené stromy
\s{Definice: } Koøeny makrostromù jsou nejvy¹¹i vrcholy, pod kterými je maximálnì $\log(n)$ listù.
Celá clusterizace se nám rozpadne na následujíci pøipady: 
\itemize\ibull
\:N-strom: (má stupeò 1)
\:M-strom: (má stupeò 2)
\:cestu: ka¾dá cesta se popí¹e bitovým polem, jednotlivé úseky se poí¹í jednotlivými slovy
\endlist
poèet listù v makrostromu je maximálnì $n/\log(n)$ z toho vyplývá, ¾e vý¹ka makrostromu $\O(n/log(n))$

\s{Co si potøebujeme pamatovat}
\itemize\ibull
\: $\log(n)$ na clusterizaci
\: makrostrom  G s $C_i$ zkontrahovanými pro deg 1,3 do vrcholu a deg 2 do hrany, jeho velikost je $\O(n/\log(n))$
\:mikrostromy, bitovì popsány
\endlist

\h{Makrostromy}
V makrostromu jsou takové hrany, které vedly v pùvodním stromu mezi clustery, vrcholy budou hranièní
vrcholy pøislu¹ných clusterù, cluster stupnì 1 je v novém stromì list, cluster stupnì 2 nahradíme 
hranou mezi hranièními vrcholy a cluster stupòe 3 má jeden vnìj¹í vrchol, který je také v novém stromì.

\s{find(x,y)}
\algo
nech» $i,j: x \in C_i, y \in C_j$
\:pokud $i=j$, ptáme se v $C_i$ (mikro-find(i,j))
\:pokud $i\not = j$, najdeme hranièní vrcholy pøíslu¹ných clusterù, tj. $h_i \in C_i, h_j \in C_j$ a provedeme makro-find($h_i$,$h_j$)
	find($i$,$j$):=makro-find($h_i$,$h_j$) and mikro-find($i$,$h_i$) and mikro-find($j$,$h_j$);
\endalgo

\s{delete(x,y)}
\algo
\: pokud $x,y$ je makro-hrana, sma¾eme ji
\: pokud $x,y \in C_i$  pak mikro-delete v $C_i$, pokud je $deg(C_i)=2$ a find($h_1$,$h_2$)==FALSE ($h_1, h_2$hranièní vrcholy), 
pak makro-delete hrany odpovýdajíci $C_i$. ($C_i$ je neprùchodná)
\endalgo
\h{Mikrostromy}
\itemize\ibull
\: strom zakoøením a oèísluji mu hrany $0..h <  \log(n)$
\: pamatujeme si: \itemize\ibull  
  \:$\forall v \in C_i$ mno¾inu hran $P_v$ na cestì do koøene v (bitový vektor)
  \:mon¾inu smazaných hran, operace delete pøidá hranu do mno¾iny
  \:hranièní vrcholy
  \endlist
\: $P_x \oplus  P_y$ je cesta z x do y
\endlist
\bye
