SPQR-träd

Ett SPQR-träd är en träddatastruktur som används inom datavetenskap , nämligen i grafalgoritmer, för att representera de tre sammankopplade komponenterna i en graf. Trekopplade komponenter i en dubbelkopplad graf är ett system av mindre grafer som beskriver alla 2-vertexsektioner av grafen. SPQR-trädet för en graf kan byggas i linjär tid [1] [2] och har vissa tillämpningar i dynamiska grafalgoritmer och grafvisualisering .

Den grundläggande strukturen som ligger bakom SPQR-trädet är de tre sammankopplade komponenterna i en graf, och förhållandet mellan en sådan nedbrytning och plana inbäddningar studerades först av McLane [3] . Dessa strukturer användes av andra forskare i effektiva algoritmer [4] innan de formaliserades som ett SPQR-träd av Di Batista och Tamassia [5] [6] [7] .

Struktur

Ett SPQR-träd har formen av ett orotat träd , där det för varje nod x finns en tillhörande oriktad graf eller multigraf G x . En nod och grafen associerad med den kan vara en av fyra typer, förkortade som SPQR:

Varje xy- kant mellan två SPQR-trädnoder är associerad med två riktade virtuella kanter , av vilka en är i G x och den andra i G y . Varje kant i grafen G x kan vara en virtuell kant för högst en kant av SPQR-trädet.

SPQR-trädet T är en 2-kopplad graf G T bildad enligt följande. Om kanten xy på SPQR-trädet länkar den virtuella kanten ab på grafen G x med den virtuella kanten cd på grafen G y , bildas en större graf genom att slå samman a och c till en supervertex, slå samman b och d till en annan supervertex , och ta bort två virtuella kanter. Det vill säga, den större grafen är summan över 2-klick G x och G y . Fortsättningen av sådan limning av varje kant av SPQR-trädet ger grafen G T , limningsordningen påverkar inte resultatet. Varje vertex i en av graferna G x kan på detta sätt associeras med en enda vertex i G T , det vill säga super-vertexen i vilken den slogs samman.

Det är vanligtvis inte tillåtet att två noder av typ S eller två noder av typ P ligger intill ett SPQR-träd, eftersom med en sådan närhet kan två noder slås samman till en större nod. Med detta krav är SPQR-trädet unikt definierat av en graf, och graferna G x associerade med noderna i SPQR-trädet är kända som de tri-anslutna komponenterna i grafen G .

Byggnad

Ett SPQR-träd för en given 2-vertex-kopplad graf kan byggas i linjär tid [1] [2] .

Problemet med att konstruera tre sammankopplade komponenter i en graf i linjär tid löstes först av Hopcroft och Tarjan [1] . Baserat på denna algoritm föreslog Di Battista och Tamassia [7] att hela strukturen för ett SPQR-träd, och endast de av dess komponenter, kan byggas i linjär tid. Efter implementeringen av den långsammare algoritmen för SPQR-träd inkluderades i GDToolkit-biblioteket, gav Gutwenger och Mutzel [2] den första implementeringen av linjär tid. Som en del av implementeringsprocessen korrigerade de en del av det tidigare arbetet av Hopcroft och Tarjan [1] .

Algoritmen för Gutwenger och Mutzel [2] inkluderar följande steg.

  1. Vi sorterar kanterna på grafen efter par av index för dess ändhörn med en variant av radix sort , som gör två omgångar av blocksortering (en pass för varje ände). Efter det kommer de parallella kanterna att stå sida vid sida i den sorterade listan och kan delas upp i en P-nod i det slutliga SPQR-trädet, vilket gör den återstående grafen enkel.
  2. Vi delar upp grafen i komponenter. Dessa komponenter kan bildas genom att hitta par av separerande hörn och dela upp grafen över dessa två hörn i mindre grafer (med tillhörande par av virtuella kanter som har de separerande hörnen som bladhörn). Partitioneringsprocessen upprepas tills det finns par över vilka partitionering kan utföras. Partitionen som erhålls på detta sätt är inte nödvändigtvis unik, eftersom de delar av grafen som ska bli S-noder i SPQR-trädet är uppdelade i flera trianglar.
  3. Vi märker varje komponent i partitionen med bokstaven P (komponent med två vertex med flera kanter), med bokstaven S (triangelformad komponent) eller R (vilken annan komponent som helst). Så länge det finns två komponenter som delar ett sammankopplat par virtuella kanter, och båda komponenterna är av typ S eller båda komponenterna är av typ P, slå samman dessa komponenter till en större komponent av samma typ.

Gutwenger och Mutzel [2] använder djup -första sökning för att hitta en struktur som de kallar en "palmträd". Palmen är byggd på basis av ett djup-första sökträd och har sökträdets bågar med orientering från trädets rot till löven, de återstående bågarna (palmbladen) är orienterade mot roten. Gutwenger och Mutzel letar sedan efter en speciell numreringsförordning för palmnoderna och använder vissa mönster i den numreringen för att identifiera par av hörn som kan dela upp grafen i mindre komponenter. Om en komponent hittas på detta sätt används stacken för att identifiera kanterna som ska vara en del av den nya komponenten .

Användning

Hitta sektioner med 2 vertex

Med ett SPQR-träd av G (inga Q-noder), kan man direkt hitta varje par av u och v i G vars borttagning gör att G kopplas bort men lämnar anslutna komponenter:

Representation av alla inbäddningar av plana grafer

Om en plan graf är 3-kopplad har den en unik plan inbäddning upp till valet av den yttre ytan och orienteringen av inbäddningen – ytorna på inbäddningen är exakt grafens cykler. Men för 2-kopplade plana grafer (med märkta hörn och kanter) som inte är 3-kopplade, kan det finnas större frihet att hitta en plan inbäddning. Mer specifikt, om två noder i ett SPQR-träd i en graf är sammankopplade med ett par virtuella kanter, är det möjligt att ändra orienteringen av en av kanterna i förhållande till den andra. Dessutom, vid en nod av typ P i ett SPQR-träd, kan olika delar av grafen associerade med de virtuella kanterna på nod P permuteras godtyckligt. Alla plana representationer av en graf kan beskrivas på detta sätt [8] .

Se även

Anteckningar

  1. ↑ 1 2 3 4 Hopcroft, Tarjan, 1973 .
  2. ↑ 1 2 3 4 5 Gutwenger, Mutzel, 2001 .
  3. ↑ Mac Lane, 1937 .
  4. ↑ Till exempel Horcroft och Tarjan ( Hopcroft, Tarjan 1973 ), Binstock och Monma ( Bienstock, Monma 1988 ). Båda tidningarna har citerats som föregångare av Di Batista och 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) .

Litteratur

Länkar