SPQR strom

Strom SPQR je stromová datová struktura používaná v informatice , konkrétně v grafových algoritmech, k reprezentaci tříspojených složek grafu. Tri-spojené komponenty dvojitě spojeného grafu jsou soustavou menších grafů, které popisují všechny 2-vrcholové části grafu. SPQR strom grafu může být sestaven v lineárním čase [1] [2] a má některé aplikace v dynamických grafových algoritmech a vizualizaci grafů .

Základní strukturou, která je základem stromu SPQR, jsou tři spojené komponenty grafu a vztah mezi takovým rozkladem a plošnými vnořeními poprvé studoval McLane [3] . Tyto struktury byly použity jinými výzkumníky v efektivních algoritmech [4] , než byly formalizovány jako strom SPQR Di Batista a Tamassia [5] [6] [7] .

Struktura

Strom SPQR má podobu nekořenového stromu , ve kterém je pro každý uzel x přidružený neorientovaný graf nebo multigraf G x . Uzel a s ním spojený graf může být jedním ze čtyř typů, zkráceně SPQR:

Každá hrana xy mezi dvěma uzly stromu SPQR je spojena se dvěma směrovanými virtuálními hranami , z nichž jedna je v G x a druhá v G y . Každá hrana v grafu G x může být virtuální hranou maximálně pro jednu hranu stromu SPQR.

SPQR strom T je 2-souvislý graf GT vytvořený následovně. Pokud hrana xy stromu SPQR spojuje virtuální hranu ab grafu G x s virtuální hranou cd grafu G y , vznikne větší graf sloučením a a c do jednoho supervertexu, sloučením b a d do jiného supervertexu. a odstranění dvou virtuálních hran. To znamená, že větší graf je součet za 2 kliknutí G x a G y . Pokračování takového lepení každé hrany stromu SPQR dává graf G T , pořadí lepení neovlivňuje výsledek. Každý vrchol v jednom z grafů G x může být tímto způsobem spojen s jedním vrcholem v G T , tedy nadvrcholem, do kterého byl sloučen.

Obvykle není povoleno, aby dva uzly typu S nebo dva uzly typu P sousedily v rámci stromu SPQR, protože s takovou sousedností mohou být dva uzly sloučeny do jednoho většího uzlu. S tímto požadavkem je strom SPQR jednoznačně definován grafem a grafy G x spojené s uzly stromu SPQR jsou známé jako tři spojené komponenty grafu G .

Budova

SPQR strom daného 2-vertex-spojeného grafu lze sestavit v lineárním čase [1] [2] .

Problém sestrojení třísouvislých složek grafu v lineárním čase poprvé řešili Hopcroft a Tarjan [1] . Di Battista a Tamassia [7] na základě tohoto algoritmu navrhli, že celou strukturu stromu SPQR a pouze jeho součásti lze budovat v lineárním čase. Poté, co byla implementace pomalejšího algoritmu pro stromy SPQR zahrnuta do knihovny GDToolkit, dali Gutwenger a Mutzel [2] první implementaci lineárního času. V rámci implementačního procesu opravili některé dřívější práce Hopcrofta a Tarjana [1] .

Algoritmus Gutwengera a Mutzela [2] zahrnuje následující kroky.

  1. Hrany grafu seřadíme podle dvojic indexů jeho koncových vrcholů pomocí varianty radix sort , která dělá dva průchody blokového řazení (jeden průchod pro každý konec). Poté budou rovnoběžné hrany stát vedle sebe v setříděném seznamu a lze je rozdělit na P-uzel konečného stromu SPQR, čímž se zbývající graf zjednoduší.
  2. Rozdělíme graf na komponenty. Tyto komponenty lze vytvořit nalezením dvojic oddělujících vrcholů a rozdělením grafu přes tyto dva vrcholy na menší grafy (s přidruženými dvojicemi virtuálních hran, které mají oddělující vrcholy jako vrcholy listů). Proces dělení se opakuje, dokud se nevyskytnou páry, u kterých lze dělení provést. Takto získaný oddíl nemusí být nutně jedinečný, protože části grafu, které by se měly stát S-uzly stromu SPQR, jsou rozděleny do několika trojúhelníků.
  3. Každou komponentu příčky označíme písmenem P (dvouvertexová komponenta s více hranami), písmenem S (komponenta ve tvaru trojúhelníku) nebo R (jakákoli jiná komponenta). Pokud existují dvě komponenty, které sdílejí spojenou dvojici virtuálních hran, a obě komponenty jsou typu S nebo obě komponenty jsou typu P, sloučte tyto komponenty do jedné větší komponenty stejného typu.

Gutwenger a Mutzel [2] používají hloubkové prohledávání k nalezení struktury, kterou nazývají „palmou“. Palma je postavena na základě hloubkového vyhledávacího stromu a má oblouky vyhledávacího stromu s orientací od kořene stromu k listům, zbývající oblouky (palmové listy) jsou orientovány ke kořeni. Gutwenger a Mutzel pak hledají speciální předobjednávku číslování pro uzly dlaně a používají určité vzory v tomto číslování k identifikaci párů vrcholů, které mohou rozdělit graf na menší komponenty. Pokud je komponenta nalezena tímto způsobem, zásobník se použije k identifikaci hran, které by měly být součástí nové komponenty .

Použití

Hledání 2-vrcholových sekcí

S SPQR stromem G (žádné Q uzly) lze přímo najít každý pár u a v v G , jehož odstranění způsobí, že G bude odpojeno, ale zůstane připojené komponenty:

Reprezentace všech vložení rovinných grafů

Pokud je rovinný graf 3-souvislý, má jedinečné rovinné vložení až do výběru vnější plochy a orientace vložení – plochy vložení jsou přesně cykly grafu. Avšak pro 2-souvislé rovinné grafy (s označenými vrcholy a hranami), které nejsou 3-souvislé, může být větší volnost při hledání rovinného vnoření. Přesněji, pokud jsou dva uzly stromu SPQR grafu spojeny dvojicí virtuálních hran, je možné změnit orientaci jedné z hran vůči druhé. Navíc v uzlu typu P stromu SPQR mohou být různé části grafu spojené s virtuálními hranami uzlu P libovolně permutovány. Tímto způsobem lze popsat všechna rovinná zobrazení grafu [8] .

Viz také

Poznámky

  1. ↑ 1 2 3 4 Hopcroft, Tarjan, 1973 .
  2. ↑ 1 2 3 4 5 Gutwenger, Mutzel, 2001 .
  3. ↑ Mac Lane, 1937 .
  4. ↑ Například Horcroft a Tarjan ( Hopcroft, Tarjan 1973 ), Binstock a Monma ( Bienstock, Monma 1988 ). Oba dokumenty byly citovány jako předchůdci Di Batista a Tamassia.
  5. ↑ 1 2 3 4 Di Battista, Tamassia, 1989 .
  6. ↑ Di Battista, Tamassia, 1990 .
  7. ↑ 1 2 Di Battista, Tamassia, 1996 .
  8. ↑ Mac Lane (1937) .

Literatura

Odkazy