drzewo SPQR - SPQR tree

Wykres i jego drzewo SPQR. Przerywane czarne linie łączą pary wirtualnych krawędzi, pokazane jako czarne; pozostałe krawędzie są pokolorowane zgodnie z trójpołączonym komponentem, do którego należą.

W teorii wykres , oddziału matematyce, że triconnected składniki o biconnected wykresie to system mniejszych wykresów, które opisują wszystkie kawałki 2-wierzchołków na wykresie. Drzewo SPQR jest drzewiastą strukturą danych używaną w informatyce , a dokładniej w algorytmach grafowych , do reprezentowania trójpołączonych elementów grafu. Drzewo SPQR grafu może być konstruowane w czasie liniowym i ma kilka zastosowań w dynamicznych algorytmach grafów i rysowaniu grafów .

Podstawowe struktury leżące u podstaw drzewa SPQR, tripołączone składniki grafu oraz związek między tym rozkładem a zanurzeniami planarnymi grafu planarnego zostały po raz pierwszy zbadane przez Saundersa MacLane'a  ( 1937 ); struktury te były używane w wydajnych algorytmach przez kilku innych badaczy przed ich formalizacją jako drzewo SPQR przez Di Battista i Tamassię ( 1989 , 1990 , 1996 ).

Struktura

Drzewo SPQR przyjmuje postać drzewa nieukorzenionego, w którym z każdym węzłem x jest powiązany graf nieskierowany lub multigraf G x . Węzeł i skojarzony z nim graf może mieć jeden z czterech typów, biorąc pod uwagę inicjały SPQR:

  • W węźle S powiązany graf jest grafem cyklu z co najmniej trzema wierzchołkami i krawędziami. Przypadek ten jest analogiczny do składania szeregów w grafach szeregowo-równoległych ; S oznacza „serię”.
  • W węźle P powiązany graf jest grafem dipolowym , multigrafem z dwoma wierzchołkami i trzema lub więcej krawędziami, planarnym dualnym do grafu cyklicznego. Przypadek ten jest analogiczny do składu równoległego w grafach szeregowo-równoległych ; P oznacza „równoległy”.
  • W węźle Q powiązany graf ma jedną rzeczywistą krawędź. Ten trywialny przypadek jest niezbędny do obsługi wykresu, który ma tylko jedną krawędź. W niektórych pracach dotyczących drzew SPQR ten typ węzła nie pojawia się w drzewach SPQR grafów z więcej niż jedną krawędzią; w innych pracach wszystkie niewirtualne krawędzie muszą być reprezentowane przez Q węzłów z jedną rzeczywistą i jedną wirtualną krawędzią, a krawędzie w innych typach węzłów muszą być wszystkie wirtualne.
  • W węźle R powiązany graf jest grafem o trzech połączeniach, który nie jest cyklem ani dipolem. R oznacza „sztywny”: w zastosowaniu drzew SPQR do osadzania grafu planarnego powiązany graf węzła R ma unikalne osadzanie planarne.

Każda krawędź xy dwóch węzłów drzewa SPQR jest związany z dwoma skierowanymi wirtualne krawędzie , z których jedna jest w krawędź G x , a drugi z nich jest krawędzią w g- y . Każda krawędź na wykresie G x może być wirtualną krawędź co najwyżej jeden SPQR krawędzi drzewa.

SPQR drzewa T oznacza 2-podłączony wykres G T , utworzonej w następujący sposób. Ilekroć krawędź drzewa SPQR xy kojarzy wirtualną krawędź ab z G x z wirtualną krawędzią cd z G y , utwórz pojedynczy większy wykres, łącząc a i c w pojedynczy supervertex, scalając b i d w inny pojedynczy supervertex i usuwając oba wirtualne krawędzie. Oznacza to, że większy wykres jest sumą dwóch klik z G x i G y . Wykonanie tego etap klejenia na każdej krawędzi drzewa SPQR wytwarza wykres G T ; kolejność wykonywania etapów klejenia nie wpływa na wynik. Każdy wierzchołek jednego z wykresów G x może wiązać się w ten sposób z unikalnym wierzchołka w G , T , w supervertex do której został połączone.

Zazwyczaj w drzewie SPQR nie jest dozwolone, aby dwa węzły S sąsiadowały ze sobą ani dwa węzły P, ponieważ gdyby doszło do takiego sąsiedztwa, dwa węzły mogłyby zostać połączone w jeden większy węzeł. Przy takim założeniu drzewo SPQR jest jednoznacznie określane na podstawie swojego wykresu. Gdy wykres G jest reprezentowane przez drzewo SPQR bez sąsiednich węzłów P i nie ma sąsiadujących węzłów S, to wykresy G x związane z węzłów drzewa SPQR są znane jako triconnected składników G .

Budowa

Drzewo SPQR danego grafu połączonego dwoma wierzchołkami można skonstruować w czasie liniowym .

Problem konstrukcji trójspójnych składowych grafu został po raz pierwszy rozwiązany w czasie liniowym przez Hopcrofta i Tarjana (1973) . Opierając się na tym algorytmie, Di Battista i Tamassia (1996) zasugerowali, że pełna struktura drzewa SPQR, a nie tylko lista składników, powinna być konstruowana w czasie liniowym. Po zaimplementowaniu wolniejszego algorytmu dla drzew SPQR w ramach biblioteki GDToolkit, Gutwenger i Mutzel (2001) dostarczyli pierwszą implementację w czasie liniowym. W ramach tego procesu implementacji tego algorytmu poprawili także niektóre błędy we wcześniejszej pracy Hopcrofta i Tarjana (1973) .

Algorytm Gutwengera i Mutzela (2001) obejmuje następujące ogólne kroki.

  1. Posortuj krawędzie wykresu według par indeksów liczbowych ich punktów końcowych, korzystając z wariantu sortowania radix, który wykonuje dwa przejścia sortowania kubełkowego , po jednym dla każdego punktu końcowego. Po tym kroku sortowania równoległe krawędzie między tymi samymi dwoma wierzchołkami będą przylegały do ​​siebie na posortowanej liście i można je podzielić na węzeł P w ewentualnym drzewie SPQR, pozostawiając pozostały wykres prosty.
  2. Podziel wykres na podzielone komponenty; są to grafy, które można utworzyć, znajdując parę oddzielających się wierzchołków, dzieląc graf na tych dwóch wierzchołkach na dwa mniejsze (z połączoną parą wirtualnych krawędzi z oddzielającymi wierzchołkami jako punktami końcowymi) i powtarzając ten proces podziału, aż przestanie być istnieją pary rozdzielające. Podział znaleziony w ten sposób nie jest jednoznacznie zdefiniowany, ponieważ części grafu, które powinny stać się węzłami S drzewa SPQR, zostaną podzielone na wiele trójkątów.
  3. Oznacz każdy podzielony komponent za pomocą P (podzielony komponent z dwoma wierzchołkami i wieloma krawędziami), S (podzielony komponent w formie trójkąta) lub R (dowolny inny podzielony komponent). Chociaż istnieją dwa podzielone komponenty, które dzielą połączoną parę wirtualnych krawędzi i oba komponenty mają typ S lub oba mają typ P, połącz je w jeden większy komponent tego samego typu.

Aby znaleźć rozszczepione komponenty, Gutwenger i Mutzel (2001) stosują wyszukiwanie w głąb, aby znaleźć strukturę, którą nazywają palmą; jest to drzewo poszukiwania w głąb, którego krawędzie są zorientowane od korzenia drzewa, na krawędzie należące do drzewa i w kierunku korzenia dla wszystkich innych krawędzi. Następnie znajdują specjalną numerację węzłów w drzewie w przedsprzedaży i używają pewnych wzorców w tej numeracji, aby zidentyfikować pary wierzchołków, które mogą podzielić graf na mniejsze składniki. Gdy składnik zostanie znaleziony w ten sposób, struktura danych stosu jest używana do identyfikacji krawędzi, które powinny być częścią nowego składnika.

Stosowanie

Znajdowanie cięć 2-wierzchołkowych

Z drzewem SPQR grafu G (bez węzłów Q) łatwo jest znaleźć każdą parę wierzchołków u i v w G tak, że usunięcie u i v z G pozostawia rozłączony graf i połączone składowe pozostałych grafów:

  • Dwa wierzchołki u i v mogą być dwoma punktami końcowymi wirtualnej krawędzi na grafie związanym z węzłem R, w którym to przypadku dwa komponenty są reprezentowane przez dwa poddrzewa drzewa SPQR utworzonego przez usunięcie odpowiedniej krawędzi drzewa SPQR.
  • Dwa wierzchołki u i v mogą być dwoma wierzchołkami grafu związanymi z węzłem P, który ma dwie lub więcej wirtualnych krawędzi. W tym przypadku składniki utworzone przez usunięcie z U i V reprezentują poddrzewach drzewa SPQR, po jednym dla każdej z krawędzi wirtualnego w węźle.
  • Dwa wierzchołki u i v mogą być dwoma wierzchołkami na grafie powiązanymi z węzłem S tak, że u i v nie są sąsiadujące lub krawędź uv jest wirtualna. Jeśli krawędź jest wirtualna, wtedy para ( u , v ) również należy do węzła typu P i R, a składowe są takie, jak opisano powyżej. Jeśli te dwa wierzchołki nie sąsiadują ze sobą, wówczas dwa komponenty są reprezentowane przez dwie ścieżki grafu cyklu powiązanego z węzłem S iz węzłami drzewa SPQR dołączonymi do tych dwóch ścieżek.

Reprezentujące wszystkie zanurzenia grafów planarnych

Jeśli graf planarny jest połączony w trójkę , ma unikalne osadzenie planarne aż do wyboru, która ściana jest ścianą zewnętrzną i orientacji osadzenia: ścianki osadzenia są dokładnie nierozdzielającymi się cyklami grafu. Jednak w przypadku grafu płaskiego (z oznaczonymi wierzchołkami i krawędziami), które są połączone w 2, ale nie w 3, może istnieć większa swoboda w znalezieniu osadzenia płaskiego. W szczególności, gdy dwa węzły w drzewie SPQR grafu są połączone parą wirtualnych krawędzi, możliwe jest odwrócenie orientacji jednego z węzłów (zastępując go jego lustrzanym odbiciem) względem drugiego. Dodatkowo, w węźle P drzewa SPQR, różne części grafu połączone z wirtualnymi krawędziami węzła P mogą być dowolnie permutowane . W ten sposób można opisać wszystkie reprezentacje planarne.

Zobacz też

Uwagi

Bibliografia

  • Bienstock, Daniel; Monma, Clyde L. (1988), „O złożoności pokrywania wierzchołków przez powierzchnie w grafie planarnym”, 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 flatarity 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), "Algorytmy wykresów on-line z drzewami SPQR", 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), " Testowanie płaskości on-line" (PDF) , SIAM Journal on Computing , 25 (5): 956-997, doi : 10.1137/S0097539794280736.
  • Gutwenger, Carsten; Mutzel, Petra (2001), "Liniowa implementacja w czasie drzew SPQR", 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, Jan ; Tarjan Robert (1973), „Dzielenie wykresu na trójpołączone elementy”, SIAM Journal on Computing , 2 (3): 135-158, doi : 10.1137/0202012 , hdl : 1813/6037.
  • Mac Lane, Saunders (1937), "Charakterystyka strukturalna planarnych grafów kombinatorycznych", Duke Mathematical Journal , 3 (3): 460-472, doi : 10.1215/S0012-7094-37-00336-3.

Zewnętrzne linki