10-decomp/10-decomp.tex

   1 \input ../sgr.tex
   2
   3 \prednaska{10}{Dekompozice stromù}{zapsal Ale¹ ©nupárek}
   4
   5 \h{Union-Find problem}
   6 Na Uion-Find problem (UF) mù¾eme nahlí¾et ze více stran (udr¾ování ekvivalencí,
   7 inkrementální souvislost grafu). K èemu je to dobré?
   8 Napøíklad v Kruskalovì algoritmu pro hledání minimálních koster v grafu.
   9 \h{Udr¾ování tøíd ekvivalence }
  10 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
  11 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)).
  12 \h{Inkrementální idr¾ování komponent souvislosti grafu}
  13 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).
  14 Za »øídy ekvivalence budou jednotlivé komponenty souvislosti grafu G. Operace find nám øekne o dvou vrcholech nachází-li
  15 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,
  16 øe©ení problému je výraznì te¾¹í.
  17
  18 \h{Bì¾ná implementace }
  19 Ka¾dé tøídì ekvivalence pøiøadíme unikátní barvu, kterou obarvíme její prvky. Pro operaci find staèí porovnat barvy prvkù.
  20 Pro operaci union dvou komponent je nutné pøebarvit obì na stejnou barvu. Budeme pøebarvovat
  21 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.)
  22 \h {Chytøej¹í implementace }
  23 Budeme-li prvky za stejné tøídy reprezentovat ve jednom stromì (synové mají ukazatel svého otce), operaci find
  24 provedeme prùchodem ze zadaných prvkù do koøene. Prvky jsou ve stejné komponentì souvislosti, pokud mají stejného otce.
  25 Operace union bude spojení dvou stromù do jednoho (otec jednoho stromu se zavìsí pod listy druhého).
  26 Takto definovaný union nemusí garantovat logaritmickou slo¾itost pro find,
  27 v extrémním pøipadì mù¾e strom mít lineární hloubku vzhledem k poètu vrcholù.
  28
  29 Degeneraci stromu lze zabránit pøidánim podmínky urèující, jaký strom bude dole.
  30 První mmo¾nost (union by size) je povìsit dolu vìtsí strom.
  31 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.
  32 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.
  33
  34 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
  35 jejich ukazatele na otce na koøen.
  36
  37 \s{Vìta: } UF s Union by size nebo Union by rank s path compression mají amortizovanì
  38 slo¾itost $\O(n\alpha(n))$, kde $\alpha(n)$ je inverzní funkce k Ackermanovì funkci. ($\alpha(poèet atomù ve vesmíru)=5$)
  39
  40 \h {Microtree/Macrotree decomposition}
  41
  42 \s{Otázka: } Je mo¾né provádìt UF v lep¹ím èase kdy¾ bude pøedem znám výsledný strom?
  43
  44 Cíl: UF lze za pomoci preprocesingu v èase $\O(n)$  zvládnout amortizovanì v èase $\O(1)$ na U,F.
  45
  46 \h{Clusterizace}
  47 \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
  48 G na podgrafy na podgrafy G1,G2 ... Gk s následujícimi vlastnostmi:
  49 \itemize\ibull
  50 \: $\forall v  \in V \exists !\ i: v \in C_i$
  51 \: $\forall i\  C_i\leq C$
  52 \: $\forall i$ vnìj¹i stupeò $C\leq3$, pokud $C_i=3$ pak $\|C_i\|=1$
  53 \: ¾ádné dva sousední clustery nelze spojit
  54 \endlist
  55
  56 Co udìlat se stromem, ve kterém existuje vrchol se stupnìm vìt¹im ne¾ 3? Pou¾ijeme French trick.
  57 V¹echny vrcholy s vy¹¹im stupnìm jak 3, rozdìlíme na více vrcholù se stupnìm 3 spojených cestou.
  58 Tato ùprava nám asymptoticky nezmìní èasovou slo¾itost UF o proti pùvodnímu stromu.
  59
  60
  61 \s{Lemma: } Pro ka¾dou C-clusterizaci n-vrcholového stromu je  $\O(n/C)$ clusterù.
  62
  63 \s{Vìta: } Pro ka¾dé C lze C-clusterizaci (splòujíci pøedchozí lemma) najít v èase $\O(n)$.
  64
  65 \s{Dùkaz: } za pomoci DFS ...
  66 \h{Jednodu¹¹í clusterizace}
  67 Pøedpokládejme, ¾e máme zakoøeòené stromy
  68 \s{Definice: } Koøeny makrostromù jsou nejvy¹¹i vrcholy, pod kterými je maximálnì $\log(n)$ listù.
  69 Celá clusterizace se nám rozpadne na následujíci pøipady:
  70 \itemize\ibull
  71 \:N-strom: (má stupeò 1)
  72 \:M-strom: (má stupeò 2)
  73 \:cestu: ka¾dá cesta se popí¹e bitovým polem, jednotlivé úseky se poí¹í jednotlivými slovy
  74 \endlist
  75 poèet listù v makrostromu je maximálnì $n/\log(n)$ z toho vyplývá, ¾e vý¹ka makrostromu $\O(n/log(n))$
  76
  77 \s{Co si potøebujeme pamatovat}
  78 \itemize\ibull
  79 \: $\log(n)$ na clusterizaci
  80 \: 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))$
  81 \:mikrostromy, bitovì popsány
  82 \endlist
  83
  84 \h{Makrostromy}
  85 V makrostromu jsou takové hrany, které vedly v pùvodním stromu mezi clustery, vrcholy budou hranièní
  86 vrcholy pøislu¹ných clusterù, cluster stupnì 1 je v novém stromì list, cluster stupnì 2 nahradíme
  87 hranou mezi hranièními vrcholy a cluster stupòe 3 má jeden vnìj¹í vrchol, který je také v novém stromì.
  88
  89 \s{find(x,y)}
  90 \algo
  91 nech» $i,j: x \in C_i, y \in C_j$
  92 \:pokud $i=j$, ptáme se v $C_i$ (mikro-find(i,j))
  93 \: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$)
  94         find($i$,$j$):=makro-find($h_i$,$h_j$) and mikro-find($i$,$h_i$) and mikro-find($j$,$h_j$);
  95 \endalgo
  96
  97 \s{delete(x,y)}
  98 \algo
  99 \: pokud $x,y$ je makro-hrana, sma¾eme ji
 100 \: 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),
 101 pak makro-delete hrany odpovýdajíci $C_i$. ($C_i$ je neprùchodná)
 102 \endalgo
 103 \h{Mikrostromy}
 104 \itemize\ibull
 105 \: strom zakoøením a oèísluji mu hrany $0..h <  \log(n)$
 106 \: pamatujeme si: \itemize\ibull
 107   \:$\forall v \in C_i$ mno¾inu hran $P_v$ na cestì do koøene v (bitový vektor)
 108   \:mon¾inu smazaných hran, operace delete pøidá hranu do mno¾iny
 109   \:hranièní vrcholy
 110   \endlist
 111 \: $P_x \oplus  P_y$ je cesta z x do y
 112 \endlist
 113 \bye