Dynamické grafové datové struktury

Dynamické grafové datové struktury

Kód předmětu: NTIN023 Přednáší: Vladan Majerech

Tento text začal jako kusy osobních poznámek konvertovaných z LyXu. Z toho plyne mnoho nepřesností a neúplností, které čekají až je někdo opraví.

Vhodné materiály pro doplnění:

• MIT lecture notes (verze 2010)
• Diplomka M. Mareše
• články třeba odtud nebo ze stránky předmětu

Souvislost grafu semidynamicky

Je povoleno pouze přidávání hran. Vyřešeno velmi efektivní Union-Find strukturou od Tarjana v amortizovaném čase $ O\left(\alpha(m,n)\right) $ na operaci (union-by-rank/size a path-compression). Ve stejném asymptotickém čase prý lze dokonce dosáhnout worst-case složitosti pro find (union asi amortizovnaně) pomocí udržování stromů hloubky přesně dle inverzní Ackermannovy funkce.

Přidání undo

Je možné Union-Find strukturu rozšířit o backtracking (odebírání posledně přidané hrany) při amortizované složitosti $ O(\log n/\log\log n) $ na operaci. To je prý asymptoticky optimální.

U každého vrcholu udržujeme zásobník změn ukazatelů se značkami, za které změny mohl který union (například ukazatele do zásobníku operací union). Navíc je u každé položky počítadlo unionů, které "nic neprovedly". Dále máme globální zásobník, kde pro každý union je seznam ukazatelů na změněné ukazatele nebo timestamp.

Samotné zkracování cest neprobíhá klasickým způsobem přímého přepojování do kořene (to by bylo příliš změn), ale zkrácení vzdáleností přibližně na polovinu jednou z metod:

1. splitting – každý ukazatel na rodiče se změní na ukazatel na prarodiče, což vede k rozštěpení cesty na dvě.
2. halving – na prarodiče je přepojen pouze každý druhý vrchol. To se může víc hodit proto, že je méně updatů a další zkracování se lépe sdílí (ale okamžité zkrácení je nepatrně menší než při splittingu).

Tyto metody lze používat i ve verzi bez backtrackingu a zaručují stejnou asymptotickou složitost (důkazy hodně složité).

Prostorová složitost

Díky tomu, že při operacích unionse třídy spojují podle ranků (nebo velikostí) a při přepojení se vždy zvýší rozdíl mezi ranky (nebo je komponenta spojena s nějakou větší), může celkový počet změn jednoho ukazatele dosáhnout nejvýše $ \log n $. Navíc pro vrcholy, jejichž rank je menší než $ \log\log n $ (velikost podstromu menší než $ \log n $), cesty nezkracujeme (to zpomalí find jen o $ O(\log\log n) $). Z toho plyne, že zkracování probíhá pouze na lesu, který má v "listech" disjunktní komponenty velikosti alespoň $ 2^{\log\log n}=\log n $, takže počet vrcholů které můžou změnit pointer je nejvýše $ n/\log n $. Celková paměť spotřebovaná pro backtracking je tedy $ O\left(\frac{n}{\log n}\log n\right)=O(n) $ (a tedy i amortizovaný čas se zvýší jen o konstantu, protože splitting i halving dávají stejnou asymptotickou složitost jako přímé přepojování).

Časová složitost

Pro provádění undojsou dvě varianty:

1. zbrklá – změny příslušící vracené operaci union jsou okamžitě vráceny zpět
2. líná – změny jsou vraceny až při přístupu k pointeru při průchodu vrcholem. Neplatnost poznáme s pomocí časové známky přidané ke každé položce zásobníku.

Každé operaci union patří právě pointery vedoucí do vrcholu, který se při této operaci stal reprezentantem komponenty (tedy jiná množina pointerů, než byla při operaci změněna).

Při amortizaci je potřeba zaplatit navíc vznik a přepojení každého ukazatele (což pokryje i všechny undo operace). Ukazatele rozdělíme na dvě skupiny:

1. dlouhý je naúčtován operaci find, která ho vytvořila. Pro union-by-size: rozdíl log-sizů je alespoň $ c\log\log n $. Pro uninon-by-rank: navíc také pokud rozdíl ranků alespoň $ c\log\log n $. V obou případech je počet dlouhých pointerů na cestě při findu nejvýše $ \log n/c\log\log n $ (TODO proč? a proč ne pro path compression).
2. krátký je naúčtován operaci union, která za ukazatel zodpovídá. Pro union-by-size: rozdíl log-sizů nejvýše $ c\log\log n $ imlikuje podíl sizů nejvýše $ \log^cn $, tedy abychom se vešli do velikosti komponenty, je počet krátkých pointerů do vrcholu nejvýše $ \log^cn=O(\log n/\log\log n) $ pro $ c<1 $.

Pro find i union tedy lze dostat amortizovanou složitost na operaci až na $ O(\log n/\log\log n) $.

Sleator-Tarjanovy stromy (Sleator-Tarjanovy-stromy)

Nazývány také link-cut trees nebo dynamic trees. Je to dynamická struktura pro reprezentaci neorientovaného lesa zakořeněných stromů, hrany mohou být ohodnocené. Pokud se někdy mluví o aktuální orientaci hran, pak je to vždy směr do kořene příslušného stromu.

Operace probíhají vždy pouze na kořenové cestě, o které také můžeme udržovat nějaké agregované informace. Amortizovaná složitost operací je $ O(\log n) $ ve velikosti stromu.

Vnější operace

• link$ (v,w) $ připojí hranou strom s kořenem $ v $ pod vrchol $ w $.
• cut$ (v) $ odpojí vrchol od otce (odebere hranu).
• evert$ (v) $ upraví reprezenaci lesa tak, aby byl vrchol $ v $ reprezentován v kořeni svého stromu.

Použití pro hledání blokujícího toku v Dinicově algoritmu

Hrany přecházejí z vrstevnaté sítě přest ST-strom až do výsledného blokujícího toku. Máme vybranou cestu ze zdroje do cíle, snížíme kapacity všech hran na cestě o minimum z kapacit na cestě. Pak odstraňujeme hrany s nulovou kapacitou a přidáváme zatím nepoužité hrany, dokud nedostaneme st-cestu.

V kořeni každého splay-stromu je vždy uložena minimální kapacita celého podstromu (v rámci cesty) a rozdíl kapacity vrcholu od kapacity otce (kapacity příslušných hran).

Reprezentace grafu

Graf je dekomponován na cesty, které jsou reprezentovány jako Splay-stromy, kde uzly stromu odpovídají vrcholům cesty (plus informace o hraně nad uzlem). Strom navíc obsahuje přímé odkazy na oba konce cesty. Každý uzel obsahuje navíc odkazy na cesty připojené hranami mimo rozklad a každá cesta (kromě kořenové) obsahuje odkaz na cestu, pomocí které je připojena ke kořeni.

Existují worst-case varianty, ale jsou komplikovanější. Mimo kořenovou cestu se dekomponuje na cesty z těžkých hran (ty vedou mezi dvěma vrcholy se stejnou log-size). Místo splay stromů se pak používají locally-biased stromy.

Vnitřní operace

• splice "přehodí výhybku" ve vrcholu.
• extended splay vysplayuje vrchol $ x $ do kořene celého ST-stromu, pomocí splicea splay operací. Má tři fáze:
  1. Dostane do kořenů cest všechny uzly do kterých se přeskakovalo mezi cestami. To se provede pomocí jednoho průchodu směrem do kořene se splay operacemi na cestě.
  2. Provede splice operace tak, aby vznikla požadovaná kořenová cesta. Nejprve zajistíme, aby byl $ x $ na konci cesty, pak přehazujeme výhybky ke kořeni stromu.
  3. Provede splay a dostane tak požadovaný vrchol do kořene celého ST-stromu.

Časová složitost

Váha uzlu $ W_v=1+ $ celkový počet uzlů v podstromech připojených pod $ v $ necestovými hranami (tranzitivně). Potenciál uzlu $ x $ je $ \mu_x=\log\sum_{y\in T_x}W_y $ kde $ T_x $ je množina uzlů v podstromu v rámci cesty. Celkový potenciál je součet přes všechny uzly.

Změny potenciálů ve fázích:

1. Váhy uzlů se nemění – necestové hrany jsou beze změny. Za splaye je potřeba zaplatit změny potenciálů vrcholů do kterých se přeskakovalo mezi cestami. Protože $ \mu x_i\le\mu x_i'\le\mu x_{i+1} $, dohromady lze omezit $ \mu x_k'-\mu x_1 $.
2. Váhy se mění, ale v sumě se čísla pouze přesouvají mezi různými $ W_x $ a potenciály se tedy nemění.
3. Za poslední splay je potřeba zaplatit rozdíl potenciálů = $ \mu x_k'-\mu x_1' $.

Dohromady lze tedy omezit amortizovanou složitost na $ 2*\left(\mu x_k'-\mu x_1\right)=O(\log n) $.

Proč tohle? Vždyť to předchozí stačí...

Celkem je cena extended splay rovna $ 1+\textrm{počet přeskoků}+c(\mu_{x*}-\mu_x) $. Přeskoky přes lehké hrany můžeme schovat do rozdílu potenciálů, zbývají tedy těžké mezicestové hrany. Do potenciálu tedy přidáme počet těžkých necestových hran.

Westbrook-Tarjan struktura

Udržuje hranovou nebo vrcholovou 2-souvislost semidynamicky a v amortizovaném čase $ O(\alpha(k,n)) $ na operaci (je povoleno pouze přidávat hrany nebo vrcholy). Verze s backtrackingem má složitost $ O\left(\frac{\log n}{\log\log n}\right) $. Terminologie:

• vrchol – v grafu
• uzel – v reprezentaci cest

Úprava reprezentace cest:

• indikátor otáčející orientaci cesty v každém uzlu
• vrcholy uspořádány do spojáku, navíc koncové vrcholy mají odkazy do kořene cesty

Hledání cesty mezi vrcholy

Idea: běhám po vrcholech směrem ke kořeni a značím si je, dokud se nepotkám. Děláme to pomocí procházky po uzlech, což je složitější, protože obecně nevím, jestli jdu po cestě směrem ke kořeni (grafu, ne cesty) nebo od kořene; dokážu ale vždy jít na opačnou stranu než jsem přišel. Při značení navštívených uzlů si navíc značím směr průchodu.

+ čárkované hrany reprezentujeme z union-findů

Základní idea

1-souvislost i 2-souvislost můžeme udržovat zvlášť, v klasických Union-Find strukturách. Navíc potřebujeme reprezentovat způsob propojení bridge-bloků (2-souvislých komponent). Udržujeme les obsahující dva typy vrcholů – původní vrcholy a navíc nový vrchol pro každý bridge-blok. Zde se odlišují verze pro různé typy 2-souvislosti.

1. Pro hranovou 2-souvislost jsou podstatné pouze vrcholy reprezentující bridge-bloky. U původních vrcholů grafu pouze potřebujeme znát, do kterého bridge-bloku patří (to zvládneme i s Union-Find strukturami).
2. Vrcholová 2-souvislost je komplikovanější, protože bridge-bloky představují množiny hran původního grafu. V lese bridge-bloků pak vedou hrany pouze mezi vrcholy odlišných typů, kde jsou komponenty propojeny přes artikulace.

Dotazy řešíme přímo pomocí Union-Find struktury. Při vkládání hrany $ \{u,v\} $ nastane jedna z možností:

1. $ u $ a $ v $ nebyly souvislé – dojde ke spojení komponent mostem (2-souvislost není ovlivněna) pomocí operace link$ (u,v) $. V menším z obou ST-stromů je vysplayován spojující vrchol a celý strom je pak připojen do většího ST-stromu (pod jeho spojující vrchol).

   Pozn.: u každé 1-souvislé komponenty si tedy potřebujeme udržovat počet vrcholů

   Ve stromu, do kterého připojujeme může být nutné spojovat vrstvy – pak v těch spojovaných provádíme omezený splay (do kořene nově vzniklé vrstvy).
2. $ u $ a $ v $ byly právě 1-souvislé – dojde ke spojení bridge-bloků ležících na kružnici kterou uzavřela přidaná hrana, pomocí operace condense$ (u,v) $. Nejprve najdeme cestu mezi $ u $ a $ v $ tak, že paralelně postupujeme z obou vrcholů ke kořeni (to zvládneme v čase úměrném délce cesty). Pak všechny hrany cesty zkontrahujeme a spojíme tak bridge-bloky do jednoho, včetně aktualizace 2-souvislosti v Union-Find struktuře.
3. $ u $ a $ v $ byly 2-souvislé – přidání hrany v rámci bridge-bloku nic nemění

Struktura modifikovaného ST-stromu

Jednotlivé splay stromy reprezentující cesty rozkladu jsou uspořádány do vrstev tak, že:

• každá vrstva je souvislý blok stromů
• velikost nadřazené vrstvy je vždy alespoň dvojnásobná (co do počtu vrcholů; alternativně s větší logsize)

Při operaci link se jednotlivé vrstvy propojují tak, aby byl invariant o jejich velikostech zachován.

Upravená operace extended splay vrcholu $ v $ probíhá v pěti fázích:

1. Nalezneme všechny úseky cest v rozkladu mezi $ v $ a kořenem. Vrcholy, kde se přeskakuje mezi cestami rozkladu vysplayujeme do kořenů svých cest (tedy mezi $ v $ a kořenem celého stromu teď budou pouze mezicestové hrany propojující kořeny cest rozkladu).
2. Provedeme splice na hrany mezi $ v $ a kořenem, které vedou v rámci stejné vrstvy. Cestu mezi $ v $ a kořenem tedy budou tvořit cesty rozkladu pospojované mezivrstvovými hranami.
3. Provedeme splay na vrcholech incidentních se zmíněnými mezivrstvovými hranami. Dostaneme tak cestu z $ v $ do kořene tvořenou pouze mezivrstvovými hranami.
4. Na tyto hrany provedeme splice a propojíme vrstvy na cestě (postupně odspoda ke kořeni). Vznikne nám cesta rozkladu mezi $ v $ a kořenem.
5. Vysplayujeme $ v $ do kořene.

Navíc operace partial extended splay: při spojování stromů může být porušen invariant vrstev, potřebujeme je spojovat dokud je porušen. Cíl: amortizovaná cena spojování úměrná logsize menšího ze spojovaných stromů.

Potenciál ST-stromu

Pro vrchol $ v $ buď $ W_v $ rovno počtu všech vrcholů pod $ v $, včetně těch připojených hranami mimo rozklad na cesty (i mezivrstvovými) a včetně $ v $ samotného. Pak definujme váhu vrcholu$ \mu_v=\left\lceil \log\sum_{u\mbox{ pod }v}W_u\right\rceil $ a váhu celého ST-stromu definujme jako součet vah všech vrcholů + počet vrstev.

Pozn.: nejsem si jistý, zda má být celá část horní, dolní, nebo jestli na tom nezáleží

Změny potenciálů pak zaplatí splayování, spojování vrstev zaplatí přeskoky a splicování už asymptotickou složitost nezvýší.

Přidání operace undo

Využije se rozšíření Union-Find struktur o undo...

U každé stromové hrany udržujeme počet pokrývajících hran, ale budeme tyto počty zvyšovat líně a budeme udržovat minima v podstromech (jako při hledání blokujícího toku). Pokud je vkládaná hrana $ \{u,v\} $ mostem, přidá se s počtem 0. Jinak je vyselektována cesta mezi $ u $ a $ v $ – pokud je minimum z počtů na cestě nenulové, je pouze evidována "prázdná operace" (abychom věděli, že se při undo nic nedělá), jinak jsou počty na cestě inkremetovány (líně, jen v kořeni). Při undo se pak analogicky buď nic nedělá, nebo jsou líně sníženy počty na cestě mezi $ u $ a $ v $.

Pro vrcholovou 2-souvislost se situace komplikuje, je potřeba udržovat u každého vrcholu lokální informaci o tom, které dvojice incidentních hran jsou pokryty2.

Fredericksonova clusterizace

Udržuje plně dynamickou hranovou 2-souvislost ve worst-case čase $ O(m) $, pomocí sparsifikace lze čas snížit na $ O(n) $. Algoritmus předpokládá stupně vrcholů nejvýše 3, vyšších stupňů se můžeme zbavit zavedením kruhových objezdů bez zhoršení asymptotické složitosti.

Clusterizace stromu

$ z $-clusterizace stromu je rozdělení vrcholů splňující:

• každý cluster má nejvýše $ z $ vrcholů a je stromově souvislý
• stupeň clusteru je nejvýše 3 a pokud je roven 3, pak obsahuje jediný vrchol (stupeň je počet hran vedoucích mimo cluster)
• lokální minimalita – žádné dva clustery nelze spojit, aniž by byla porušena některá z předchozích podmínek

Vytvoření $ z $-clusterizace a přidávání vrcholů nebo hran je snadné, stačí slučovat clustery, dokud to jde (rekurzivní konstrukce z kořene). Mazání stromové hrany je komplikovanější, ale i tam se situace ustálí po konstantním počtu operací.

2-clusterizace na $ n $ vrcholech obsahuje nejvýše $ \frac{5}{6}n $ clusterů

Každému clusteru obsahujícímu dva vrcholy přiřadíme 6 mincí a ukážeme, že je můžeme rozdistribuovat tak, že každý vrchol dostane alespoň jednu minci. Strom zakořeníme v každém clusteru dle stupně:

1. Listový cluster. Pokud má dva vrcholy, pak pošle nahoru tři mince a zbytek si nechá (jedna zůstane nevyužita). Pokud má jen jeden vrchol, tak dostane shora jednu minci na jeho pokrytí (rodičem totiž může být jedině dvouvrcholový cluster).
2. Cluster stupně dva. Pokud má dva vrcholy, pak pošle tři mince nahoru a jednu dolu. Pokud má jeden vrchol, pak dostane tři mince od potomka (který musí mít buď stupeň tři, nebo dva vrcholy) a nahoru pošle dvě mince (nahoře musí být cluster stupně tři).
3. Cluster stupně tři dostane od obou potomků po dvou mincích (nejsou jednovrcholové) a pošle nahoru tři mince.

Z toho plyne, že alespoň třetina clusterů obsahuje dva vrcholy a tedy počet clusterů je nejvýše $ \frac{5}{6}n $.

$ z $-clusterizace na $ n $ vrcholech obsahuje $ O(n/z) $ clusterů

Udělejme 2-clusterizaci na clusterech: spojení jen tam, kde bránila velikost (ne stupeň), tedy měli jsme alespoň $ \frac{1}{6}n $ clusterů velikosti alespoň $ \frac{1}{2}z $.

Smazání hrany

Chceme v čase $ O(1) $. Spojování může nastat kvůli snížení stupně nebo snížení počtu vrcholů (jsou odděleny). Pro clustery stupně 1 nebo 2 musela být důvodem nepřipojení jedině velikost. Zmenšení:

• cluster stupně 1 se může spojit se sousedem a snížit jeho stupeň (viz snížení stupně níže).
• cluster stupně 2 se tedy přinejhorším spojí s oběma sousedy.

Snížení stupně: XXX

Topologické stromy

Při použití rekurzivního dělení – na úrovni 0 $ z $-clusterizace a na všech dalších 2-clusterizace až do jediného clusteru bude celkový počet clusterů všech úrovní $ \Theta\left(\frac{m}{z}\right) $. Frederickson používá $ z\approx\sqrt{m} $. Rekurzivním dělením vzniká topologický strom, kde každý vrchol odpovídá clusteru, v kořeni je cluster obsahující všechny vrcholy původního grafu a synové clusteru jsou clustery o úroveň níž (je tedy vždy jeden syn nebo dva).

Pozn.: "topologický strom" je ve skutečnosti obecný les, navíc pokud uvážíme pomocné hrany spojující sousední clustery, není graf ani acyklický

Modifikace topologického stromu typicky zasáhne všechny jeho vrstvy, ale práce na každé z nich je omezena konstantou, takže celkem trvá $ O\left(\log m\right) $. Při průchodu odspodu udržujeme množiny clusterů aktuální vrstvy: $ L_D $ (zrušené), $ L_C $ (změněné) a $ L_A $ (zatím bez otce). Zpracování vrstvy:

• Pro každý cluster $ C $ v $ L_D $ zrušíme reprezentaci $ C $ ve stromu. Pokud $ C $ je kořen, končíme zpracování. Pokud byl $ C $ jediným synem, přidáme otce do $ L'_D $. Jinak bratra vložíme do $ L'_C $ (pokud už není v $ L_C $ nebo $ L_D $).
• Zpracujeme každou sourozeneckou dvojici $ \{x,x'\}\subseteq L_C $. Pokud je jejich otec stále korektním clusterem, přidáme ho do $ L'_C $. Jinak přesuneme $ x $ a $ x' $ do $ L_A $ a otce do $ L'_D $.
• Zpracujeme zbytek intuitivně.

Reprezentace cest

V topologickém stromu přímo není zachycena informace o cestách v kostře. Pro každý cluster $ C $ tedy definujme jeho úplnou a částečnou cestu podle pravidel:

1. $ C $ má úroveň 0 (vrchol původního grafu). Částečná cesta obsahuje tento vrchol a úplná cesta je prázdná.
2. $ C $ má jednoho syna $ D $. Pak $ C $ zdědí cesty od $ D $.
3. $ C $ má syny $ D_1 $ a $ D_2 $ spojené hranou $ e $, BÚNO má $ D_1 $ stupeň větší nebo roven stupni $ D_2 $.
   1. $ C $ je kořen. Částečná cesta je prázdná a úplná cesta vznikne spojením částečných cest synů hranou $ e $.
   2. $ D_1 $ má stupeň tři (a tedy $ D_2 $ musí mít stupeň jedna). Částečná cesta obsahuje jediný vrchol z $ D_1 $ a úplná cesta vznikne prodloužením úplné cesty z $ D_1 $ o hranu $ e $ a jediný vrchol z $ D_1 $.
   3. Jinak je částečná cesta spojením částečných cest $ D_1 $ a $ D_2 $ hranou $ e $ a úplná cesta je prázdná.

Částečná cesta:

• v clusterech stupně jedna vede odněkud zevnitř do hraničního vrcholu
• v clusterech stupně dva vede mezi hraničními vrcholy
• v clusterech stupně tři je tvořena jediným vrcholem

Každá hrana patří do právě jedné úplné cesty.

Evidence pokrytí cest

Spočtena pro každý cluster z evidence jeho synů.

V hlavě každé úplné cesty si budeme pamatovat vzdálenost k nejbližšímu mostu na cestě (top-to-bridge).

Přidání pokrývací hrany do stromu clusterů:

Nestromové hrany

Informace o nestromových hranách jsou udržovány v topologickém stromu druhé dimenze. Ten obsahuje informace pro každou dvojici clusterů na stejné úrovni, tedy zabírá paměť $ \Theta(m) $. Update mění konstantně široký pás ve stromu clusterů

Dotazy na 2-spojitost: nejprve najdeme projekce obou vrcholů do boundary tree. Pokud jsou ve stejném vrcholu, porovnám vzdálenosti k nejbližšímu mostu na cestě k boundary tree se vzdálenostmi k nejbližšímu společnému vrcholu. Pokud jsou v různých vrcholech, vyřešíme to v boundary tree. Tam je cesta rozložena na úseky podle průniků s úplnými cestami, úseků je $ O(\log m) $.

Sparsifikace

Certifikát vlastnosti – podgraf, který ji také splňuje. Například pro hranovou $ 2 $-souvislost je to kostra grafu + kostra zbytku. Stabilní certifikát je funkce $ f $ zobrazující graf na podgraf, který je certifikátem a splňuje:

• $ f\left(G\cup H\right)=f\left(f\left(G\right)\cup H\right) $
• $ f\left(G\cup\{e\}\right)\setminus f\left(G\right) $ má velikost $ O(1) $

Pokud jsme schopni efektivně udržovat řídký stabilní certifikát, můžeme udržovat rekurzivně definovaný strom. Množinu vrcholů vždy rozdělíme napůl a vytvoříme tři syny – dva z grafů indukovaných podmnožinama vrcholů a jeden ze zbytku hran (bipartitní graf). První dva podgrafy zpracujeme rekurzivně stejným způsobem. V bipartitním grafu vždy rozdělíme obě partity napůl a tím vzniknou čtyři bipartitní grafy.

Takto vznikne strom hloubky $ \log n $, kde každá hrana původního grafu se vyskytuje právě v grafech na jedné cestě z kořene do listu.

ET-stromy

Ve stromu zorientujeme hrany oběma směry, ty tvoří eulerovskou cestu. Nad cestou si postavíme nějaký strom, navíc každý vrchol stromu si pamatuje jeden významný výskyt v ET – tam se o něm evidují informace.

Spojování stromů:

• u jednoho je potřeba vrchol, přes který spojujeme dostat na kraj ET (split stromu ve vrcholu a prohození částí)
• u druhého split ve vrcholu a vložení prvního (upraveného) stromu

Rozdělení stromu:

• najdu oba výskyty hrany, rozdělím v nich strom
• prostřední strom a join krajních jsou výsledky

Jiná strukt. (11.11.2010) - asi překonaná

Asi randomizovaná amortizovaná souvislost v čase $ \log^{3}n $. Nejprve dekrementálně, pak dynamizace.

Sample = $ c\log^{2}n $ nestromových hran z $ G_i $ incidentních s $ T_1 $.

M. R. Henzinger, Valerie King: Randomized dynamic graph algorithms with polylogarithmic time per operation (section 2.4: a fully dynamic connectivity algorithm).

Top-tree

Top-tree slouží pro reprezentaci neorientovaného lesa hierarchií clusterů. Každý cluster představuje zobecněnou hranu – vždy reprezentuje souvislý podgraf, má nejvýše dva vnější vrcholy a je tvořen nejvýše dvěma clustery (nebo jedním vrcholem původního lesa).

Vnitřní operace na clusterech:

• create edge
• destroy edge
• split – rozdělí cluster
• join – spojí dva clustery
• decide – potřeba jen pro non-local search, rozhodne ve kterém ze dvou clusterů v kořeni se nachází hledaný vrchol

Top-tree podporuje vnější operace:

• expose – udělá z jednoho nebo dvou parametrů vnější vrchol(y)
• link – spojení dvou stromů
• cut – smazání hrany
• non-local search – najde vrchol podle dané operace decide

Triviální aplikace

• Průměr stromu (tj. délka nejdelši cesty ve stromu): pro každý cluster spočteme jeho délku, délky nejdelších cest z obou hraničních vrcholů a průměr clusteru.
• Vzdálenost k nejbližšímu označenému vrcholu. Operace: označ/odznač vrchol, dotaz na vrchol.
• Centrum stromu (tj. hrana která sousedí s centrem leží v bicentru): pomocí průměru, decide a non-local search.
• Meeting point tří vrcholů stromu. Zjistím vzdálenosti mezi dvojicemi a spočtu z nich pozici meeting pointu. Pak na něj skočím.

Hranová 2-souvislost pomocí top-tree

Pozn.: Fredericsonův driver je lepší pro vypínání aktualizací kvůli komplikované kombinaci perzistence a amortizace.

V amortizovaném čase $ O\left(\log^{4}n\right) $.

• V top-tree máme kostru a pro každou hranu uloženou úroveň jejího pokrytí a pokrývající hranu. Nestromové hrany mají úroveň $ \in\{0,\dots,\log n\} $. Na začátku úroveň 0, ale předplatíme budoucí zdvihání úrovní.
• Jediný složitý případ je smazání nestromové hrany. Na celý interval pokrytý hranou zavoláme uncover$ (v,w,i) $: všechny hrany pokryté na úrovni nejvýše $ i $ nastavíme na nepokryté ($ i:=-1 $, líně – vlastnost clusteru).
• recover$ (v,w,i) $ obnoví pokrytí na cestě na úrovni nejvýše $ i $

Implementace

Pro každý cluster udržujeme:

• cover$ (c) $ je úroveň pokrytí, coverEdge$ (c) $ je pokrývající hrana
• lazy informace: coverMinus$ (c) $ $ \ge $ coverPlus$ (c) $, coverPlusEdge$ (c) $. Hrany pokryté na nejvýše coverMinus jsou odkryty a pokrytí všeho je navýšeno na coverPluss hranou coverPlusEdge$ (c) $.

Pro cestový cluster $ c $ označme $ X_{c,v,i,j} $ množinu všech vnitřních vrcholů $ x $ v $ c $ takových, že cesta $ \left(x\dots p(x)\right) $ je pokryta alespoň na $ j $ a cesta $ \left(v..p(x)\right) $ je pokryta alespoň na $ i $ ($ v $ je krajní vrchol $ c $ a $ p(x) $ je projekce $ x $ na vybranou cestu kostry). Evidujme:

• incident$ (c,v,i,j) $ je počet nestromových hran úrovně $ =j $ vedoucích z vrcholů $ X_{c,v,i,j} $ (bereme orientovaně, některé hrany můžeme počítat z obou stran).
• size$ (c,v,i,j)=\left|X_{c,v,i,j}\right| $.

Pro necestový cluster $ c $ evidujeme:

• incident$ (c,v,j) $ je počet nestromových hran úrovně $ =j $ vedoucích z vrcholů $ X_{c,v,j} $ (analogicky).
• size$ (c,v,j)=\left|X_{c,v,j}\right| $.

Další operace

• clean$ (c) $ odpropaguje lazy informace do synů.
• find$ (u,c,i) $ najde hranu v $ c $ úrovně $ i $ takovou, že jej projekce je neblíž k $ u $.

Dynamická minimální kostra

• pro každý cluster udržujeme nejtěžší hranu + nestromoví sousedi....

Drivery

Driver říká které clustery se spojují dohromady (pořadí spojování vrcholů).

• pokud máme driver kde základní clustery jsou jednotlivé vrcholy a chceme mít v top stromech větší, ignorujeme clustery až do určité velikosti.

Pomocí Fredericksona

• dva druhy top-clusterů: pro F-clustery a pro hrany mezi nimi