SPQR -träd - SPQR tree

En graf och dess SPQR -träd. De streckade svarta linjerna förbinder par virtuella kanter, som visas som svarta; de återstående kanterna färgas enligt den triconnected komponent de tillhör.

I grafteorin , en gren av matematik, är de trikopplade komponenterna i en dubbelkopplad graf ett system med mindre grafer som beskriver alla 2-vertex-snitt i grafen. Ett SPQR -träd är en träddatastruktur som används i datavetenskap , och mer specifikt grafalgoritmer , för att representera de trikopplade komponenterna i en graf. SPQR -trädet i en graf kan konstrueras i linjär tid och har flera applikationer i dynamiska grafalgoritmer och grafritning .

De grundläggande strukturerna som ligger till grund för SPQR -trädet, de trikopplade komponenterna i en graf och sambandet mellan denna sönderdelning och de plana inbäddningarna i en plan graf undersöktes först av Saunders Mac Lane  ( 1937 ); dessa strukturer användes i effektiva algoritmer av flera andra forskare innan de formaliserades som SPQR -trädet av Di Battista och Tamassia ( 1989 , 1990 , 1996 ).

Strukturera

Ett SPQR -träd har formen av ett outrotat träd där för varje nod x det är associerat ett oriktat diagram eller multigraf G x . Noden och den graf som är associerad med den kan ha en av fyra typer, med tanke på initialerna SPQR:

  • I en S -nod är den associerade grafen en cykeldiagram med tre eller flera hörn och kanter. Detta fall är analogt med seriesammansättning i serie -parallella grafer ; S står för "serie".
  • I en P -nod är den associerade grafen en dipolgraf , en multigraf med två hörn och tre eller flera kanter, den plana dubbel till en cykeldiagram. Detta fall är analogt med parallellkomposition i serie -parallella grafer ; P står för "parallell".
  • I en Q -nod har den associerade grafen en enda verklig kant. Detta triviala fall är nödvändigt för att hantera grafen som bara har en kant. I vissa arbeten på SPQR -träd visas inte denna typ av nod i SPQR -träden i grafer med mer än en kant; i andra verk måste alla icke-virtuella kanter representeras av Q-noder med en verklig och en virtuell kant, och kanterna i de andra nodtyperna måste alla vara virtuella.
  • I en R-nod är den associerade grafen en 3-ansluten graf som inte är en cykel eller dipol. R står för "rigid": i tillämpningen av SPQR -träd i plan inbäddning av graf har den associerade grafen för en R -nod en unik plan inbäddning.

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

Ett SPQR-träd T representerar en 2-ansluten graf G T , formad enligt följande. Närhelst SPQR -trädkanten xy associerar den virtuella kanten ab av G x med den virtuella kant -cd: n för G y , bilda en enda större graf genom att slå samman a och c till en enda supervertex, slå samman b och d till en annan supervertex och radera de två virtuella kanter. Det vill säga, den större grafen är 2-clique-summan av G x och G y . Genom att utföra detta limningssteg på varje kant av SPQR -trädet produceras grafen G T ; ordningen för att utföra limningsstegen påverkar inte resultatet. Varje toppunkt i en av graferna G x kan på detta sätt associeras med en unik toppunkt i G T , supervertexen till vilken den slogs samman.

Vanligtvis är det inte tillåtet i ett SPQR -träd att två S -noder är intilliggande, eller att två P -noder är intilliggande, för om en sådan närhet inträffade skulle de två noder kunna slås samman till en enda större nod. Med detta antagande bestäms SPQR -trädet unikt utifrån sin graf. När en graf G representeras av en SPQR träd med inga angränsande P noder och inga angränsande S noder, då graferna G x associerad med noderna i SPQR trädet är kända som de triconnected komponenterna i G .

Konstruktion

SPQR-trädet i en given 2-vertex-ansluten graf kan konstrueras i linjär tid .

Problemet med att konstruera de trikopplade komponenterna i en graf löstes först i linjär tid av Hopcroft & Tarjan (1973) . Baserat på denna algoritm föreslog Di Battista & Tamassia (1996) att hela SPQR -trädstrukturen, och inte bara listan över komponenter, skulle vara konstruerbar i linjär tid. Efter en implementering av en långsammare algoritm för SPQR-träd som en del av GDToolkit-biblioteket, gav Gutwenger & Mutzel (2001) den första linjära tidsimplementeringen. Som en del av denna process för att implementera denna algoritm korrigerade de också några fel i det tidigare arbetet med Hopcroft & Tarjan (1973) .

Algoritmen för Gutwenger & Mutzel (2001) inkluderar följande övergripande steg.

  1. Sortera kanterna på diagrammet efter paren av numeriska index för deras slutpunkter, med hjälp av en variant av radixsortering som gör två passningar av skopssortering , en för varje slutpunkt. Efter detta sorteringssteg kommer parallella kanter mellan samma två hörn att ligga intill varandra i den sorterade listan och kan delas upp i en P-nod i det slutliga SPQR-trädet, så att den återstående grafen blir enkel.
  2. Dela upp grafen i delade komponenter; det här är grafer som kan bildas genom att hitta ett par separerande hörn, dela upp grafen vid dessa två hörn i två mindre grafer (med ett länkat par virtuella kanter som har skiljevinkeln som slutpunkter) och upprepa denna delningsprocess tills det inte mer är separationspar finns. Partitionen som hittas på detta sätt är inte unikt definierad, eftersom de delar av grafen som ska bli S-noder i SPQR-trädet kommer att delas upp i flera trianglar.
  3. Märk varje delad komponent med en P (en två-toppig delad komponent med flera kanter), en S (en delad komponent i form av en triangel) eller en R (någon annan delad komponent). Det finns två delade komponenter som delar ett länkat par virtuella kanter, och båda komponenterna har typ S eller båda har typ P, men slå ihop dem till en enda större komponent av samma typ.

För att hitta de delade komponenter Gutwenger & Mutzel (2001) användning djup-först-sökning för att hitta en struktur som de kallar en palm; det här är ett djup-första sökträd med sina kanter orienterade bort från trädets rot, efter kanterna som tillhör trädet och mot roten för alla andra kanter. De hittar sedan en särskild förbeställning av noderna i trädet, och använder vissa mönster i denna numrering för att identifiera par hörn som kan dela upp grafen i mindre komponenter. När en komponent hittas på detta sätt används en stackdatastruktur för att identifiera kanterna som ska vara en del av den nya komponenten.

Användande

Hitta snitt med två hörn

Med SPQR -trädet i en graf G (utan Q -noder) är det enkelt att hitta varje par hörn u och v i G så att borttagning av u och v från G lämnar en frånkopplad graf och de anslutna komponenterna i de återstående graferna:

  • De två hörnen u och v kan vara de två slutpunkterna för en virtuell kant i grafen associerad med en R -nod, i vilket fall de två komponenterna representeras av de två subträden i SPQR -trädet som bildas genom att ta bort motsvarande SPQR -trädkant.
  • De två hörnen u och v kan vara de två hörnen i grafen associerade med en P -nod som har två eller flera virtuella kanter. I detta fall representeras de komponenter som bildas genom avlägsnandet av u och v av subtrees i SPQR -trädet, en för varje virtuell kant i noden.
  • De två hörnen u och v kan vara två hörn i grafen associerad med en S -nod så att antingen u och v inte är intill varandra, eller så är kanten uv virtuell. Om kanten är virtuell tillhör paret ( u , v ) också en nod av typ P och R och komponenterna är som beskrivits ovan. Om de två hörnen inte ligger intill varandra representeras de två komponenterna av två vägar i cykeldiagrammet som är associerat med S -noden och med SPQR -trädnoderna som är kopplade till de två banorna.

Representerar alla inbäddningar av plana grafer

Om en plan graf är 3-ansluten har den en unik plan inbäddning upp till valet av vilket ansikte som är ytterytan och inbäddningens orientering : inbäddningens ytor är exakt de icke-separerande cyklerna i grafen. För en plan graf (med märkta hörn och kanter) som är 2-ansluten men inte 3-ansluten kan det dock finnas större frihet att hitta en plan inbäddning. Närhelst två noder i SPQR -trädet i grafen är anslutna med ett par virtuella kanter är det specifikt möjligt att vända orienteringen för en av noderna (ersätta den med dess spegelbild) i förhållande till den andra. I en P -nod i SPQR -trädet kan dessutom de olika delarna av grafen som är anslutna till virtuella kanter på P -noden godtyckligt permuteras . Alla plana representationer kan beskrivas på detta sätt.

Se även

Anteckningar

Referenser

  • Bienstock, Daniel; Monma, Clyde L. (1988), "Om komplexiteten att täcka hörn med ansikten i en plan graf", SIAM Journal on Computing , 17 (1): 53–76, CiteSeerX  10.1.1.542.2314 , doi : 10.1137/0217004.
  • Di Battista, Giuseppe; Tamassia, Roberto (1989), "Incremental planarity testing", Proc. 30th Annual Symposium on Foundations of Computer Science , s. 436–441, doi : 10.1109/SFCS.1989.63515.
  • Di Battista, Giuseppe; Tamassia, Roberto (1990), "On-line grafalgoritmer med SPQR-träd", Proc. 17th International Colloquium on Automata, Languages ​​and Programming , Lecture Notes in Computer Science , 443 , Springer-Verlag, s. 598–611, doi : 10.1007/BFb0032061.
  • Di Battista, Giuseppe; Tamassia, Roberto (1996), "On-line planarity testing" (PDF) , SIAM Journal on Computing , 25 (5): 956–997, doi : 10.1137/S0097539794280736.
  • Gutwenger, Carsten; Mutzel, Petra (2001), "En linjär tidsimplementering av SPQR-träd", Proc. 8th International Symposium on Graph Drawing (GD 2000) , Lecture Notes in Computer Science, 1984 , Springer-Verlag, s. 77–90, doi : 10.1007/3-540-44541-2_8.
  • Hopcroft, John ; Tarjan, Robert (1973), "Dela upp en graf i trikopplade komponenter", SIAM Journal on Computing , 2 (3): 135–158, doi : 10.1137/0202012 , hdl : 1813/6037.
  • Mac Lane, Saunders (1937), "En strukturell karakterisering av plana kombinatoriska grafer", Duke Mathematical Journal , 3 (3): 460–472, doi : 10.1215/S0012-7094-37-00336-3.

externa länkar