Obustronnie połączony komponent - Biconnected component

Przykładowy wykres z zaznaczonymi dwoma połączonymi komponentami
Każdy kolor odpowiada dwóm połączonym składnikom. Wielokolorowe wierzchołki są wyciętymi wierzchołkami, a zatem należą do wielu podwójnie połączonych komponentów.

W teorii wykres , A dwuspójna składowa (czasem określane jako 2-podłączonego urządzenia ) jest ilość biconnected subgraph . Każdy połączony graf rozkłada się na drzewo dwojako połączonych komponentów, zwane drzewem wycinanym z bloków grafu. Bloki są połączone ze sobą we wspólnych wierzchołkach zwanych wierzchołkami wyciętymi lub wierzchołkami oddzielającymi lub punktami artykulacji . W szczególności wycięty wierzchołek to dowolny wierzchołek, którego usunięcie zwiększa liczbę połączonych komponentów .

Algorytmy

Liniowe wyszukiwanie według głębokości w czasie

Klasyczny sekwencyjny algorytm do obliczania podwójnie połączonych komponentów w połączonym nieskierowanym grafie jest dziełem Johna Hopcrofta i Roberta Tarjana (1973). Działa w czasie liniowym i opiera się na przeszukiwaniu w głąb . Algorytm ten jest również nakreślony jako Problem 22-2 Wprowadzenia do algorytmów (zarówno wydanie drugie, jak i trzecie).

Chodzi o to, aby przeprowadzić wyszukiwanie w głąb, zachowując następujące informacje:

  1. głębokość każdego wierzchołka w drzewie wyszukiwania w głąb (po jego odwiedzeniu) oraz
  2. dla każdego wierzchołka v , najniższa głębokość sąsiadów wszystkich potomków v (włącznie z samym v ) w drzewie wyszukiwania według głębokości, zwanym najniższym punktem .

Głębokość jest standardowo utrzymywana podczas przeszukiwania według głębokości. Najniższy punkt v można obliczyć po odwiedzeniu wszystkich potomków v (tj. tuż przed usunięciem v ze stosu pierwszego wyszukiwania w głąb ) jako minimum głębokości v , głębokości wszystkich sąsiadów v (innych niż rodzic v w drzewie wyszukiwania w głąb) i najniższy punkt wszystkich elementów potomnych v w drzewie wyszukiwania w głąb.

Kluczowym faktem jest, że innego niż administrator wierzchołek v jest wierzchołkiem cięcie (lub punkt artykulacji) oddzielająca dwa dwuspójna składowa tylko wtedy, gdy jest dziecko y od v takie, że Lowpoint ( y ) ≥ głębokość ( v ). Właściwość tę można przetestować, gdy wyszukiwanie w głąb zostanie zwrócone z każdego elementu podrzędnego v (tj. tuż przed usunięciem v ze stosu wyszukiwania w głąb), a jeśli true , v rozdziela wykres na różne połączone elementy. Można to przedstawić, obliczając jeden podwójnie połączony komponent z każdego takiego y (komponent, który zawiera y, będzie zawierał poddrzewo y , plus v ), a następnie wymazując poddrzewo y z drzewa.

Wierzchołek główny musi być obsługiwany oddzielnie: jest to wierzchołek wycięty wtedy i tylko wtedy, gdy ma co najmniej dwoje dzieci w drzewie DFS. Dlatego wystarczy po prostu zbudować jeden komponent z każdego poddrzewa podrzędnego korzenia (w tym korzenia).

Pseudo kod

GetArticulationPoints(i, d)
    visited[i] := true
    depth[i] := d
    low[i] := d
    childCount := 0
    isArticulation := false

    for each ni in adj[i] do
        if not visited[ni] then
            parent[ni] := i
            GetArticulationPoints(ni, d + 1)
            childCount := childCount + 1
            if low[ni] ≥ depth[i] then
                isArticulation := true
            low[i] := Min (low[i], low[ni])
        else if ni ≠ parent[i] then
            low[i] := Min (low[i], depth[ni])
    if (parent[i] ≠ null and isArticulation) or (parent[i] = null and childCount > 1) then
        Output i as articulation point

Zauważ, że terminy dziecko i rodzic oznaczają relacje w drzewie DFS, a nie oryginalny wykres.

Demo algorytmu Tarjana do znajdowania wyciętych wierzchołków. D oznacza głębokość, a L oznacza niski punkt.


Inne algorytmy

Prostą alternatywą dla powyższego algorytmu są dekompozycje łańcuchowe , które są specjalnymi dekompozycjami uszu w zależności od drzew DFS . Dekompozycje łańcuchowe mogą być obliczane w czasie liniowym za pomocą tej reguły przechodzenia . Niech C będzie rozkładem łańcucha G . Wtedy G jest połączone 2 wierzchołkami wtedy i tylko wtedy, gdy G ma minimalny stopień 2 i C 1 jest jedynym cyklem w C . Daje to natychmiastowy test konektywności w czasie liniowym i można go rozszerzyć o listę wszystkich wierzchołków uciętych G w czasie liniowym za pomocą następującego stwierdzenia: Wierzchołek v w grafie spójnym G (z minimalnym stopniem 2) jest wierzchołkiem uciętym, jeśli i tylko jeśli v jest wypadkiem z mostem lub v jest pierwszym wierzchołkiem cyklu w C − C 1 . Lista ciętych wierzchołków mogą być wykorzystywane do tworzenia drzewa blok-cut z G w czasie liniowym.

W wersji online problemu wierzchołki i krawędzie są dodawane (ale nie usuwane) dynamicznie, a struktura danych musi utrzymywać dwupołączone komponenty. Jeffery Westbrook i Robert Tarjan (1992) opracowali wydajną strukturę danych dla tego problemu opartą na rozłącznych strukturach danych . W szczególności przetwarza n dodawania wierzchołków i m dodawania krawędzi w całkowitym czasie O( m  α ( m ,  n ) ) , gdzie α jest odwrotną funkcją Ackermanna . Udowodniono, że ten termin jest optymalny.

Uzi Vishkin i Robert Tarjan (1985) zaprojektowali równoległy algorytm na CRCW PRAM, który działa w czasie O(log  n ) z n  +  m procesorami. Guojing Cong i David A. Bader (2005) opracowali algorytm, który osiąga przyspieszenie 5 z 12 procesorami na SMP . Przyspieszenia przekraczające 30 w oparciu o oryginalny algorytm Tarjana-Vishkina zgłosili James A. Edwards i Uzi Vishkin (2012).

Powiązane struktury

Relacja równoważności

Można zdefiniować binarną relację na krawędziach dowolnego nieskierowanego grafu, zgodnie z którą dwie krawędzie e i f są powiązane wtedy i tylko wtedy, gdy e  =  f lub graf zawiera prosty cykl przez oba e i f . Każda krawędź jest związana ze sobą, a krawędź e jest związana z inną krawędzią f wtedy i tylko wtedy, gdy f jest związane w ten sam sposób z e . Mniej oczywiście jest to relacja przechodnia : jeśli istnieje prosty cykl zawierający krawędzie e i f oraz inny prosty cykl zawierający krawędzie f i g , to można połączyć te dwa cykle, aby znaleźć prosty cykl przechodzący przez e i g . Dlatego jest to relacja równoważności i może być używana do podziału krawędzi na klasy równoważności, podzbiory krawędzi o właściwości, że dwie krawędzie są ze sobą powiązane wtedy i tylko wtedy, gdy należą do tej samej klasy równoważności. Podgrafy utworzone przez krawędzie w każdej klasie równoważności są dwuspójnymi składowymi danego grafu. Zatem dwójkowo połączone komponenty dzielą krawędzie grafu; jednak mogą dzielić wierzchołki ze sobą.

Wykres blokowy

Wykres blokowy danego wykresu G jest wykresem przecięcia jej bloków. W ten sposób ma jeden wierzchołek dla każdego bloku G i krawędź między dwoma wierzchołkami, gdy odpowiadające dwa bloki mają wspólny wierzchołek. Wykres H jest wykresem blokowym innego grafu G dokładnie wtedy, gdy wszystkie bloki H są kompletnymi podgrafami. Wykresy H z tą właściwością nazywane są wykresami blokowymi .

Drzewo cięte blokowo

Progowej , cięcie wierzchołek lub punkt przegubu grafu G ma wierzchołek, który jest współdzielony przez dwa lub więcej bloków. Strukturę bloków i punktów cięcia połączonego grafu można opisać za pomocą drzewa zwanego drzewem cięcia bloków lub drzewem BC . To drzewo ma wierzchołek dla każdego bloku i dla każdego punktu artykulacji danego grafu. W drzewie wyciętym z bloku znajduje się krawędź dla każdej pary bloku i punkt artykulacyjny należący do tego bloku.

Wykres i jego wycięte z bloków drzewo.
Bloki to: b 1 =[1,2], b 2 =[2,3,4], b 3 =[2,5,6,7], b 4 =[7,8,9,10,11 ] b 5 = [8,12,13,14,15], b 6 = [10,16] i b 7 = [10,17,18];
punkty odcięcia to: c 1 =2, c 2 =7, c 3 =8 i c 4 =10.

Zobacz też

Uwagi

  1. ^ Hopcroft, J.; Tarjan, R. (1973). „Algorytm 447: wydajne algorytmy do manipulacji wykresami”. Komunikaty ACM . 16 (6): 372–378. doi : 10.1145/362248.362272 .
  2. ^ Schmidt, Jens M. (2013), "Prosty test na 2-Vertex- i 2-Edge-Connectivity", litery przetwarzania informacji , 113 (7): 241-244, arXiv : 1209.0700 , doi : 10.1016/j. ipl.2013.01.016.
  3. ^ Westbrook, J.; Tarjan, RE (1992). „Utrzymywanie komponentów połączonych mostem i biconnected on-line”. Algorytmika . 7 (1–6): 433–464. doi : 10.1007/BF01758773 .
  4. ^ Tarjan, R.; Wiszkin, U. (1985). „Efektywny algorytm równoległej dwułączności”. SIAM J. Comput. 14 (4): 862–874. CiteSeerX  10.1.1.465.8898 . doi : 10.1137/0214061 .
  5. ^ Guojing Cong i David A. Bader (2005). „Experimental Study of Parallel Biconnected Components Algorytmy na symetrycznych wieloprocesorach (SMP)”. Materiały z 19th International Conference on Parallel and Distributed Processing Symposium . s. 45b. doi : 10.1109/IPDPS.2005.100 .
  6. ^ Edwards, JA; Wiszkin, U. (2012). „Lepsze przyspieszenia przy użyciu prostszego programowania równoległego dla połączeń wykresów i biconnectivity”. Materiały z międzynarodowych warsztatów z 2012 r. nt. programowania modeli i zastosowań wielordzeniowych i wielordzeniowych - PMAM '12 . P. 103. doi : 10.1145/2141702.2141714 . Numer ISBN 9781450312110.
  7. ^ Tarjan i Vishkin (1985) przypisują definicję tej relacji równoważności Harary'emu (1969) ; jednak Harary nie wydaje się opisywać tego wprost.
  8. ^ Harary, Frank (1969), Teoria grafów , Addison-Wesley, s. 29.
  9. ^ Harary (1969) , s. 36.

Bibliografia

Linki zewnętrzne