SPQR fa

Az SPQR-fa egy olyan fa adatstruktúra, amelyet a számítástechnikában , nevezetesen a gráfalgoritmusokban használnak a gráf három összekapcsolt összetevőinek ábrázolására. A duplán összefüggő gráf hármas összefüggő komponensei kisebb gráfok rendszere, amelyek a gráf összes 2 csúcsos szakaszát leírják. A gráf SPQR fája lineáris időben felépíthető [1] [2] , és van néhány alkalmazása a dinamikus gráfalgoritmusokban és a gráfvizualizációban .

Az SPQR fa alapszerkezetét egy gráf hármas összeköttetésű komponensei alkotják, az ilyen dekompozíció és a síkbeli beágyazások közötti kapcsolatot először McLane vizsgálta [3] . Ezeket a struktúrákat más kutatók használták hatékony algoritmusokban [4] , mielőtt Di Batista és Tamassia [5] [6] [7] SPQR fává formálták volna őket .

Szerkezet

Az SPQR fa egy gyökerezetlen fa formájú , amelyben minden x csomóponthoz tartozik egy irányítatlan gráf vagy multigráf G x . Egy csomópont és a hozzá tartozó gráf a négy típus egyike lehet, rövidítve SPQR:

• S típusú csomópont (sorozat = soros kapcsolat), a hozzá tartozó gráf három vagy több csúcsot és élt tartalmazó ciklus . Ez az eset hasonló a párhuzamos-soros gráfok soros kapcsolásához [5] .
• P típusú csomópont (párhuzamos = párhuzamos kapcsolat), a hozzá tartozó gráf egy dipólus ( kétciklusú gráf), egy két csúcsú és három vagy több élű multigráf . Ez az eset hasonló a párhuzamos-szekvenciális gráfok párhuzamos kapcsolásához [5] .
• Q típusú csomópont, a hozzá tartozó gráfnak egyetlen éle van. Erre a triviális esetre van szükség az egyetlen élből álló gráfok kezeléséhez. Egyes SPQR-fákon végzett munkákban ez a csomóponttípus nem jelenik meg az egynél több élű gráfok SPQR-fáiban. Más dokumentumokban az összes nem virtuális élt Q típusú csomópontoknak kell reprezentálniuk egy valós és egy virtuális éllel, a más típusú csomópontok minden élének pedig virtuálisnak kell lennie.
• Egy R típusú csomópont (merev = merev), a hozzá tartozó gráf egy 3-kapcsolatú gráf, amely sem nem ciklus, sem nem dipólus. A "merev" itt azt jelenti, hogy ha SPQR fákat használunk sík gráfbeágyazáshoz, az R csomóponthoz tartozó gráf egyetlen síkbeli beágyazással rendelkezik [5] .

A két SPQR fa csomópontja közötti minden xy élhez két irányított virtuális él tartozik, amelyek közül az egyik a G x -ben , a másik pedig a Gy - ben van . A G x gráf minden éle az SPQR fa legfeljebb egy élének virtuális éle lehet.

A T SPQR fa egy 2-összefüggõ G T gráf , amelyet a következõképpen alakítunk ki. Ha az SPQR fa xy éle összekapcsolja a G x gráf ab virtuális élét a G y gráf cd virtuális élével , akkor egy nagyobb gráf keletkezik úgy, hogy a és c egy szupervertexbe, b és d pedig egy másik szupervertexbe. és két virtuális él törlése. Vagyis a nagyobb grafikon a G x és G y 2 kattintás összege . Az SPQR fa minden élének ilyen ragasztásának folytatása a G T gráfot adja , a ragasztás sorrendje nem befolyásolja az eredményt. A G x gráfok egyikének minden csúcsa ily módon társítható a G T egyetlen csúcsával , vagyis azzal a szupercsúccsal, amelybe beolvadt.

Általában nem megengedett, hogy két S típusú csomópont vagy két P típusú csomópont szomszédos legyen egy SPQR fán belül, mert ilyen szomszédossággal két csomópont összevonható egy nagyobb csomópontba. Ezzel a követelménnyel az SPQR fát egy gráf egyedileg definiálja, és az SPQR fa csomópontjaihoz társított G x gráfokat a G gráf hármas komponenseiként ismerjük .

Épület

Egy adott 2 csúcsú összefüggő gráf SPQR fája lineáris időben felépíthető [1] [2] .

A gráf három összefüggő komponensének lineáris időben történő megszerkesztésének problémáját először Hopcroft és Tarjan [1] oldotta meg . Ezen algoritmus alapján Di Battista és Tamassia [7] azt javasolta, hogy egy SPQR-fa teljes szerkezete, és csak a komponensei építhetők fel lineáris időben. Miután a GDToolkit könyvtárba bekerült az SPQR fák lassabb algoritmusa, Gutwenger és Mutzel [2] megadta a lineáris idő első implementációját. A megvalósítási folyamat részeként kijavították Hopcroft és Tarjan korábbi munkáját [1] .

Gutwenger és Mutzel [2] algoritmusa a következő lépéseket tartalmazza.

1. A gráf éleit a végcsúcsainak indexpárjai alapján rendezzük a radix sort egyik változatával , amely két lépést hajt végre a blokkrendezésben (mindegyik véghez egy lépés). Ezt követően a párhuzamos élek egymás mellett állnak a rendezett listában, és feloszthatók a végső SPQR fa P-csomópontjára, így a fennmaradó gráf egyszerűvé válik.
2. A grafikont komponensekre bontjuk. Ezeket a komponenseket úgy lehet kialakítani, hogy találunk elválasztó csúcspárokat, és a két csúcs feletti gráfot kisebb gráfokra bontjuk (a kapcsolódó virtuális élpárokkal az elválasztó csúcsok levélcsúcsként). A particionálási folyamat addig ismétlődik, amíg nem lesznek olyan párok, amelyeken a particionálás végrehajtható. Az így kapott partíció nem feltétlenül egyedi, mivel a gráf azon részei, amelyeknek az SPQR fa S-csomópontjaivá kell válniuk, több háromszögre vannak osztva.
3. A partíció minden egyes összetevőjét P betűvel (több élű két csúcsú komponens), S betűvel (háromszög alakú komponens) vagy R betűvel (bármely más komponens) címkézzük. Mindaddig, amíg két olyan összetevő van, amelyek egy összekapcsolt virtuális élpáron osztoznak, és mindkét komponens S típusú vagy mindkét összetevő P típusú, egyesítse ezeket az összetevőket egy nagyobb, azonos típusú összetevővé.

Gutwenger és Mutzel [2] a mélységi keresést használja , hogy megtalálja az általuk "pálmafának" nevezett szerkezetet. A pálmafa egy mélységi keresőfa alapján épül fel, és a keresőfa ívei a fa gyökerétől a levelek felé irányulnak, a fennmaradó ívek (pálmalevelek) a gyökér felé irányulnak. Gutwenger és Mutzel ezután speciális számozási előrendelést keresnek a tenyércsomópontokhoz, és ebben a számozásban bizonyos mintákat használnak, hogy azonosítsák azokat a csúcspárokat, amelyek a gráfot kisebb komponensekre oszthatják fel. Ha egy komponenst ilyen módon talál meg, akkor a verem azonosítja azokat az éleket, amelyeknek az új komponens részét kell képezniük .

Használat

2 csúcsos szakaszok keresése

Egy G SPQR fával (nincs Q csomópont) közvetlenül megkereshető minden u és v pár G -ben, amelynek eltávolítása G -t szétválasztja, de összekapcsolt komponenseket hagy:

• A két u és v csúcs egy virtuális él két vége lehet az R csomóponthoz társított gráfban. Ebben az esetben a két komponenst az SPQR-fa két részfája képviseli, amelyek az SPQR-fa élének eltávolításából származnak.
• A két u és v csúcs két vagy több virtuális éllel rendelkező P-csomóponthoz társított gráf két csúcsa lehet. Ebben az esetben az u és v eltávolításával létrehozott komponenseket az SPQR fa részfái képviselik, a csomópont minden egyes virtuális éléhez egy-egy.
• A két u és v csúcs lehet a gráf két csúcsa, amely egy olyan S-csomóponthoz van társítva, amely nem szomszédos sem u , sem v -vel, vagy az uv él virtuális. Ha az él virtuális, akkor az ( u , v ) pár egy P vagy R típusú csomóponthoz tartozik, és a komponenseket fentebb leírtuk. Ha két csúcs nem szomszédos S-vel, akkor a komponenseket az S csomóponthoz tartozó ciklus két útja és az ehhez a két útvonalhoz kapcsolódó SPQR fa csomópontjai reprezentálják.

Síkgráfok összes beágyazásának ábrázolása

Ha egy síkgráf 3-as összeköttetésű, akkor egyedi síkbeágyazása van a külső lap megválasztásáig és a beágyazás tájolásáig – a beágyazás lapjai pontosan a gráf ciklusai. Azonban a 2-kapcsolatú síkgráfok esetében (címkézett csúcsokkal és élekkel), amelyek nem 3-as összeköttetésűek, nagyobb szabadság lehet a síkbeli beágyazás megtalálásában. Pontosabban, ha egy gráf SPQR fájának két csomópontját egy pár virtuális él köti össze, akkor lehetőség van az egyik él orientációjának megváltoztatására a másikhoz képest. Ezenkívül egy SPQR-fa P típusú csomópontjában a P csomópont virtuális éleihez társított gráf különböző részei tetszőlegesen permutálhatók. Egy gráf minden síkbeli reprezentációja leírható így [8] .

Lásd még

• Bi-connected komponens fa, hasonló fastruktúra a vertex-2-kapcsolt komponensekhez
• A Gomori-Hu fa , egy másik fastruktúra, amely egy gráf összekapcsolhatósági éleit írja le
• Fabontás , általánosítás nagy szakaszokra

Jegyzetek

1. ↑ 1 2 3 4 Hopcroft, Tarjan, 1973 .
2. ↑ 1 2 3 4 5 Gutwenger, Mutzel, 2001 .
3. ↑ Mac Lane, 1937 .
4. ↑ Például Horcroft és Tarjan ( Hopcroft, Tarjan 1973 ), Binstock és Monma (Bienstock , Monma 1988 ). Di Batista és Tamassia mindkét papírt előfutárként említette.
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) .

Irodalom

• Di Battista G., Tamassia R. Inkrementális síkosság tesztelése // Proc. 30. éves szimpózium a számítástechnika alapjairól . - 1989. - S. 436-441. - doi : 10.1109/SFCS.1989.63515 .
• Di Battista G., Tamassia R. On-line gráfalgoritmusok SPQR-fákkal // Proc. 17. Nemzetközi Kollokvium automatákkal, nyelvekkel és programozással . - Springer-Verlag, 1990. - T. 443. - S. 598-611. — ( Számítástechnikai előadásjegyzetek ). - doi : 10.1007/BFb0032061 .
• Di Battista G., Tamassia R. On-line síksági tesztelés  // SIAM Journal on Computing. - 1996. - T. 25 , sz. 5 . — S. 956–997 . - doi : 10.1137/S0097539794280736 .
• Gutwenger C., Mutzel P. SPQR-trees lineáris time implementációja // Proc. 8. Nemzetközi Grafikonrajzi Szimpózium (GD 2000) . - Springer-Verlag, 2001. - T. 1984. - S. 77–90. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/3-540-44541-2_8 .
• Hopcroft J., Tarjan R. Egy gráf felosztása háromösszefüggõ komponensekre. — SIAM Journal on Computing. - 1973. - T. 2. - S. 135–158. - doi : 10.1137/0202012 .
• Mac Lane S. A planáris kombinatorikus gráfok szerkezeti jellemzése  // Duke Mathematical Journal. - 1937. - T. 3 , sz. 3 . – S. 460–472 . - doi : 10.1215/S0012-7094-37-00336-3 .

Linkek

• az SPQR fa megvalósítása az Open Graph Drawing Frameworkben.
• három összekapcsolt összetevők megvalósítása Java nyelven a jBPT könyvtárban (lásd a TCTree osztályt).