SPQR-träd

En graf och dess SPQR-träd. De streckade svarta linjerna förbinder par av virtuella kanter, visade som svarta; de återstående kanterna är färgade enligt den trekopplade komponenten de tillhör.

Inom grafteorin , en gren av matematiken, är de trekopplade komponenterna i en dubbelkopplad graf ett system av mindre grafer som beskriver alla snitt med två vertex i grafen. Ett SPQR-träd är en träddatastruktur som används inom datavetenskap , och mer specifikt grafalgoritmer, för att representera de trekopplade komponenterna i en graf. SPQR-trädet i en graf kan konstrueras i linjär tid och har flera tillämpningar i dynamiska grafalgoritmer och grafritning .

De grundläggande strukturerna som ligger bakom SPQR-trädet, de trekopplade komponenterna i en graf, och sambandet mellan denna nedbrytning och de plana inbäddningarna av 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 orotat träd där det för varje nod x är associerat en oriktad graf eller multigraf G x . Noden, och grafen som är associerad med den, kan ha en av fyra typer, givet initialerna SPQR:

  • I en S-nod är den associerade grafen en cykelgraf med tre eller fler 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 dubbla till en cykelgraf. Detta fall är analogt med parallell komposition i serie-parallella grafer ; P står för "parallell".
  • I en Q-nod har den associerade grafen en enda reell kant. Detta triviala fall är nödvändigt för att hantera grafen som bara har en kant. I vissa arbeten med SPQR-träd visas inte denna typ av nod i SPQR-träden för 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-kopplad graf som inte är en cykel eller dipol. R:et står för "rigid": vid tillämpning av SPQR-träd vid inbäddning av plana grafer 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 , av vilka 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-kopplad graf G T , bildad enligt följande. Närhelst SPQR-trädkanten xy associerar den virtuella kanten ab av G x med den virtuella kanten cd av 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 enkel supervertex och ta bort de två virtuella kanter. Det vill säga, den större grafen är 2-klicksumman 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 vertex i en av graferna G x kan på detta sätt associeras med ett unikt vertex i G T , supervertexet till vilket det slogs samman.

Vanligtvis är det inte tillåtet i ett SPQR-träd för två S-noder att vara intilliggande, och inte heller för två P-noder att vara intilliggande, eftersom om en sådan angränsning inträffade skulle de två noderna kunna slås samman till en enda större nod. Med detta antagande bestäms SPQR-trädet unikt från dess graf. När en graf G representeras av ett SPQR- träd utan intilliggande P-noder och inga intilliggande S-noder, då är graferna G x associerade med noderna i SPQR-trädet kända som de trekopplade komponenterna av G.

Konstruktion

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

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

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

  1. Sortera kanterna på grafen efter paren av numeriska index för deras ändpunkter, med en variant av radixsortering som gör två omgångar av hinksortering , en för varje ändpunkt. 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 för det eventuella SPQR-trädet, vilket gör den återstående grafen 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 de separerande hörnen som ändpunkter) och upprepa denna delning tills det inte finns mer separerande par 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 in i flera trianglar.
  3. Märk varje delad komponent med ett P (en delad komponent med två vertex med flera kanter), ett S (en delad komponent i form av en triangel) eller ett R (vilken annan delad komponent). Även om 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, slå samman dem till en enda större komponent av samma typ.

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

Användande

Hitta snitt med 2 vertex

Med SPQR-trädet för en graf G (utan Q-noder) är det enkelt att hitta varje par av hörn u och v i G så att om du tar bort 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å ändpunkterna för en virtuell kant i grafen associerad med en R-nod, i vilket fall de två komponenterna representeras av de två underträ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 som är associerade med en P-nod som har två eller flera virtuella kanter. I det här fallet representeras komponenterna som bildas av avlägsnandet av u och v av underträd i SPQR-trädet, ett för varje virtuell kant i noden.
  • De två hörnen u och v kan vara två hörn i grafen som är associerade med en S-nod så att antingen u och v inte är intilliggande, eller så är kanten uv virtuell. Om kanten är virtuell, så tillhör paret ( u , v ) också en nod av typen P och R och komponenterna är som beskrivits ovan. Om de två hörnen inte är intill varandra representeras de två komponenterna av två banor i cykelgrafen som är associerade med S-noden och med SPQR-trädnoderna kopplade till dessa två banor.

Representerar alla inbäddningar av plana grafer

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

Se även

Anteckningar

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=SPQR_tree&oldid=1097624605 "