SPQR træ

Et SPQR-træ er en trædatastruktur, der bruges i datalogi , nemlig i grafalgoritmer, til at repræsentere de tre-forbundne komponenter i en graf. Tri-forbundne komponenter i en dobbeltforbundet graf er et system af mindre grafer, der beskriver alle 2-vertex sektioner af grafen. SPQR-træet i en graf kan bygges i lineær tid [1] [2] og har nogle applikationer i dynamiske grafalgoritmer og grafvisualisering .

Den grundlæggende struktur, der ligger til grund for SPQR-træet, er de tre-forbundne komponenter i en graf, og forholdet mellem en sådan nedbrydning og plane indlejringer blev først undersøgt af McLane [3] . Disse strukturer blev brugt af andre forskere i effektive algoritmer [4] , før de blev formaliseret som et SPQR-træ af Di Batista og Tamassia [5] [6] [7] .

Struktur

Et SPQR-træ har form af et urodfæstet træ , hvor der for hver node x er en tilknyttet urettet graf eller multigraf G x . En knude og den graf, der er knyttet til den, kan være en af ​​fire typer, forkortet SPQR:

• En knude af type S (serie = seriel forbindelse), den tilhørende graf er en cyklus med tre eller flere hjørner og kanter. Dette tilfælde ligner seriel forbindelse i parallel-serielle grafer [5] .
• En knude af type P (parallel = parallelforbindelse), den tilhørende graf er en dipol ( dual cycle graf), en multigraf med to spidser og tre eller flere kanter. Dette tilfælde ligner parallelforbindelse i parallel-sekventielle grafer [5] .
• En node af typen Q, den tilhørende graf har en enkelt kant. Denne trivielle sag er nødvendig for at arbejde med grafer, der består af en enkelt kant. I noget arbejde med SPQR-træer vises denne nodetype ikke i SPQR-træer af grafer med mere end én kant. I andre papirer kræves det, at alle ikke-virtuelle kanter repræsenteres af noder af type Q med én reel og én virtuel kant, og alle kanter af noder af andre typer skal være virtuelle.
• En knude af type R (rigid = rigid), den tilhørende graf er en 3-forbundet graf, der hverken er en cyklus eller en dipol. "Stiv" betyder her, at når du bruger SPQR-træer til en plan grafindlejring, har grafen forbundet med knude R en enkelt plan indlejring [5] .

Hver xy -kant mellem to SPQR-træknuder er forbundet med to rettede virtuelle kanter , hvoraf den ene er i G x og den anden i G y . Hver kant i grafen G x kan være en virtuel kant for højst én kant af SPQR-træet.

SPQR-træet T er en 2-forbundet graf G T dannet som følger. Hvis kanten xy på SPQR-træet forbinder den virtuelle kant ab på grafen G x med den virtuelle kant cd på grafen G y , dannes en større graf ved at flette a og c ind i et supervertex, flette b og d ind i et andet supervertex , og sletning af to virtuelle kanter. Det vil sige, at den større graf er summen over 2-klik G x og G y . Fortsættelsen af ​​sådan limning af hver kant af SPQR-træet giver grafen G T , rækkefølgen af ​​limning påvirker ikke resultatet. Hvert toppunkt i en af ​​graferne G x kan på denne måde associeres med et enkelt toppunkt i G T , det vil sige super-toppunktet, som det blev flettet ind i.

Det er normalt ikke tilladt for to noder af type S eller to noder af type P at være tilstødende inden for et SPQR-træ, fordi med en sådan adjacency kan to noder slås sammen til en større node. Med dette krav er SPQR-træet entydigt defineret af en graf, og graferne G x knyttet til noderne i SPQR-træet er kendt som de tre-forbundne komponenter i grafen G .

Konstruktion

Et SPQR-træ af en given 2-vertex-forbundet graf kan bygges i lineær tid [1] [2] .

Problemet med at konstruere tre-forbundne komponenter i en graf i lineær tid blev først løst af Hopcroft og Tarjan [1] . Baseret på denne algoritme foreslog Di Battista og Tamassia [7] , at hele strukturen af ​​et SPQR-træ, og kun de af dets komponenter, kan bygges i lineær tid. Efter implementeringen af ​​den langsommere algoritme for SPQR-træer blev inkluderet i GDToolkit-biblioteket, gav Gutwenger og Mutzel [2] den første implementering af lineær tid. Som en del af implementeringsprocessen korrigerede de noget af det tidligere arbejde af Hopcroft og Tarjan [1] .

Algoritmen for Gutwenger og Mutzel [2] inkluderer følgende trin.

1. Vi sorterer kanterne af grafen efter par af indekser af dens endehjørner ved hjælp af en variant af radix sort , som laver to gennemløb af bloksortering (en passage for hver ende). Derefter vil de parallelle kanter stå side om side i den sorterede liste og kan opdeles i en P-node i det endelige SPQR-træ, hvilket gør den resterende graf enkel.
2. Vi opdeler grafen i komponenter. Disse komponenter kan dannes ved at finde par af adskillende spidser og opdele grafen over disse to spidser i mindre grafer (med tilhørende par af virtuelle kanter, der har de adskillende spidser som bladhjørner). Partitioneringsprocessen gentages, indtil der er par, som partitionering kan udføres over. Den partition, der opnås på denne måde, er ikke nødvendigvis unik, da de dele af grafen, der skulle blive til S-knuder i SPQR-træet, er opdelt i flere trekanter.
3. Vi mærker hver komponent i partitionen med bogstavet P (to-vertex-komponent med flere kanter), med bogstavet S (trekantformet komponent) eller R (enhver anden komponent). Så længe der er to komponenter, der deler et forbundet par virtuelle kanter, og begge komponenter er af type S, eller begge komponenter er af type P, skal disse komponenter flettes til en større komponent af samme type.

Gutwenger og Mutzel [2] bruger dybde -første søgning for at finde en struktur, de kalder en "palmetræ". Palmen er bygget på basis af et dybde-første søgetræ og har buer af søgetræet med orientering fra træets rod til bladene, de resterende buer (palmeblade) er orienteret mod roden. Gutwenger og Mutzel leder derefter efter en speciel nummereringsforudbestilling til palmeknuderne og bruger bestemte mønstre i den nummerering til at identificere par af hjørner, der kan opdele grafen i mindre komponenter. Hvis en komponent findes på denne måde, bruges stakken til at identificere de kanter, der skal være en del af den nye komponent .

Brug

Finde 2-vertex sektioner

Med et SPQR-træ af G (ingen Q-noder) kan man direkte finde hvert par af u'er og v'er i G , hvis fjernelse gør G afbrudt, men efterlader tilsluttede komponenter:

• De to spidser u og v kan være de to ender af en virtuel kant i grafen, der er knyttet til en R-node. I dette tilfælde er de to komponenter repræsenteret af to undertræer af SPQR-træet, som er et resultat af fjernelse af en kant af SPQR-træet.
• De to spidser u og v kan være to spidser i en graf, der er knyttet til en P-node, der har to eller flere virtuelle kanter. I dette tilfælde er komponenterne dannet ved at fjerne u og v repræsenteret af undertræer i SPQR-træet, en for hver virtuel kant i noden.
• De to spidser u og v kan være to spidser i grafen, der er knyttet til en S-knude, der ikke støder op til hverken u eller v , eller kanten uv er virtuel. Hvis kanten er virtuel, så tilhører parret ( u , v ) en knude af typen P eller R, og komponenterne er beskrevet ovenfor. Hvis to hjørner ikke støder op til S, så er komponenterne repræsenteret af de to stier i cyklussen, der er knyttet til knudepunktet S og SPQR-træknuderne, der er knyttet til disse to stier.

Repræsentation af alle indlejringer af plane grafer

Hvis en plan graf er 3-forbundet, har den en unik plan indlejring op til valget af den ydre flade og orienteringen af ​​indlejringen - fladerne af indlejringen er nøjagtigt grafens cyklusser. Men for 2-forbundne plane grafer (med mærkede spidser og kanter), som ikke er 3-forbundne, kan der være mere frihed til at finde en plan indlejring. Mere specifikt, hvis to knudepunkter i et SPQR-træ i en graf er forbundet med et par virtuelle kanter, er det muligt at ændre orienteringen af ​​en af ​​kanterne i forhold til den anden. Derudover kan forskellige dele af grafen, der er forbundet med de virtuelle kanter af knudepunktet P, permuteres vilkårligt ved en knude af typen P i et SPQR-træ. Alle plane repræsentationer af en graf kan beskrives på denne måde [8] .

Se også

• Bi-forbundet komponenttræ , en lignende træstruktur for vertex-2-forbundne komponenter
• Gomori-Hu-træet , en anden træstruktur, der beskriver forbindelseskanterne på en graf
• Trænedbrydning , generalisering til store sektioner

Noter

1. ↑ 1 2 3 4 Hopcroft, Tarjan, 1973 .
2. ↑ 1 2 3 4 5 Gutwenger, Mutzel, 2001 .
3. ↑ Mac Lane, 1937 .
4. ↑ For eksempel Horcroft og Tarjan ( Hopcroft, Tarjan 1973 ), Binstock og Monma ( Bienstock, Monma 1988 ). Begge papirer er blevet citeret som forløbere af Di Batista og 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

• Di Battista G., Tamassia R. Incremental planarity testing // Proc. 30. årlige symposium om grundlaget for datalogi . - 1989. - S. 436-441. - doi : 10.1109/SFCS.1989.63515 .
• Di Battista G., Tamassia R. On-line grafalgoritmer med SPQR-træer // Proc. 17. internationale kollokvium om automater, sprog og programmering . - Springer-Verlag, 1990. - T. 443. - S. 598-611. — ( Forelæsningsnotater i Datalogi ). - doi : 10.1007/BFb0032061 .
• Di Battista G., Tamassia R. On-line planaritetstest  // SIAM Journal on Computing. - 1996. - T. 25 , no. 5 . — S. 956–997 . - doi : 10.1137/S0097539794280736 .
• Gutwenger C., Mutzel P. En lineær tidsimplementering af SPQR-træer // Proc. 8. internationale symposium om graftegning (GD 2000) . - Springer-Verlag, 2001. - T. 1984. - S. 77–90. — (Forelæsningsnotater i datalogi). - doi : 10.1007/3-540-44541-2_8 .
• Hopcroft J., Tarjan R. Opdeling af en graf i treforbundne komponenter. — SIAM Journal on Computing. - 1973. - T. 2. - S. 135–158. - doi : 10.1137/0202012 .
• Mac Lane S. En strukturel karakterisering af plane kombinatoriske grafer  // Duke Mathematical Journal. - 1937. - T. 3 , Nr. 3 . — S. 460–472 . - doi : 10.1215/S0012-7094-37-00336-3 .

Links

• implementering af SPQR-træet i Open Graph Drawing Framework.
• implementering af tre-forbundne komponenter i Java i jBPT-biblioteket (se TCTree-klassen).