Dynamiczna łączność

W informatyce i teorii grafów dynamiczna struktura łączności to struktura danych, która dynamicznie przechowuje informacje o połączonych elementach grafu.

Zestaw V wierzchołków grafu jest stały, ale zbiór E krawędzi może się zmieniać. Trzy przypadki, w kolejności trudności, to:

Krawędzie są dodawane tylko do wykresu (można to nazwać łącznością przyrostową );
Krawędzie są usuwane tylko z wykresu (można to nazwać łącznością dekrementalną );
Krawędzie można dodawać lub usuwać (można to nazwać w pełni dynamiczną łącznością ).

Po każdym dodaniu/usunięciu krawędzi dynamiczna struktura łączności powinna dostosować się tak, aby mogła dawać szybkie odpowiedzi na zapytania w postaci „czy istnieje ścieżka między x i y ?” (równoważnie: „czy wierzchołki x i y należą do tego samego połączonego komponentu?”).

Łączność przyrostowa

Jeśli można dodawać tylko krawędzie, problem z dynamiczną łącznością można rozwiązać za pomocą struktury danych o zbiorze rozłącznym . Każdy zestaw reprezentuje połączony komponent; istnieje ścieżka między x i y wtedy i tylko wtedy, gdy należą one do tego samego zbioru. Zamortyzowany czas na operację wynosi $gdzie$ n to wierzchołków α to odwrotna

Łączność malejąca

Przypadek, w którym można usuwać tylko krawędzie, został rozwiązany przez Shimona Evena i Yossi Shiloacha.

Struktura wykorzystuje tabelę , która określa dla każdego wierzchołka nazwę komponentu, do którego należy. W związku z tym zapytanie o łączność zajmuje stały czas. Wyzwaniem jest aktualizacja tabeli po usunięciu krawędzi.

Grafy acykliczne (lasy)

Kiedy krawędź u - v zostanie usunięta w lesie , drzewo zawierające tę krawędź jest dzielone na dwa drzewa : jedno z nich zawiera u , a drugie zawiera v . Tabela jest aktualizowana w następujący sposób.

Przeskanuj drzewo zaczynając od u (używając dowolnego algorytmu skanowania drzewa, takiego jak DFS ).
Przeskanuj drzewo zaczynając od v .
Wykonaj powyższe dwie procedury równolegle, tj. albo używając dwóch równoległych procesów, albo przeplatając ich kroki (wykonaj krok pierwszego skanu, następnie krok drugiego skanu, następnie krok pierwszego skanu, itd.).
Załóżmy, że pierwszym skanem, który się kończy, jest skan z u (więc wiemy, że drzewo zawierające u jest mniejsze). Przypisz nową nazwę komponentu do każdego węzła w poddrzewie u .

Ponieważ zawsze zmieniamy nazwę mniejszego składnika podrzędnego, zamortyzowany czas operacji usuwania wynosi ${\ Displaystyle O (\ log (n))}$ .

Wykresy ogólne

Kiedy krawędź jest usuwana z ogólnego wykresu, nie wiemy, czy jej składowa pozostaje pojedynczym składowym (połączonym innymi krawędziami), czy też jest rozbita na dwie składowe. Używamy więc dwóch procesów, które działają równolegle (lub w sposób przeplatany). Proces A sprawdza, czy usunięcie krawędzi powoduje uszkodzenie komponentu, a jeśli tak, to oba procesy zostają zatrzymane. Proces B sprawdza, czy usunięcie krawędzi nie psuje komponentu, do którego należy, a jeśli tak się nie dzieje, oba procesy ponownie się zatrzymują.

Proces A: jest podobny do przypadku wykresu acyklicznego: istnieją dwa podprocesy, które skanują z obu końców usuniętej krawędzi. Jeśli jeden z podprocesów zakończy się przed dotarciem do drugiego końca, oznacza to, że komponent zostanie podzielony na dwa podkomponenty, a nazwa mniejszego podkomponentu zostanie zaktualizowana, tak jak poprzednio. Zatem amortyzowany czas operacji usuwania wynosi ponownie ${\ Displaystyle O (\ log (n))}$ .

Proces B: wykorzystuje strukturę wszerz (BFS) , która jest inicjowana w następujący sposób. Wybrano wierzchołek r i od niego zaczyna się BFS. Jedynym wierzchołkiem na poziomie 0 jest r . Wszystkie wierzchołki w odległości i od korzenia leżą na poziomie i . Jeśli G nie jest spójny, rozpoczyna się nowe skanowanie w jakimś nieprzeskanowanym wierzchołku v , v jest umieszczane na poziomie 1, a sztuczna krawędź łączy v z pierwiastkiem r ; wszystkie wierzchołki w odległości i od v znajdują się teraz na poziomie i +1 itd. Sztuczne krawędzie są wprowadzane w celu utrzymania wszystkich połączonych komponentów w jednej strukturze BFS i są używane tylko w tym celu. Oczywiście sztuczne krawędzie są używane tylko w procesie B.

Struktura ma następujące właściwości. Wierzchołek v na poziomie i , i >0, ma tylko trzy rodzaje krawędzi: krawędzie wsteczne , które łączą go z poziomem i −1 (jest co najmniej jedna taka krawędź, która może być sztuczna), krawędzie lokalne , które łączą go z innymi krawędzie na poziomie i (takich krawędzi jest zero lub więcej) lub krawędzie przednie , które łączą ją z krawędziami na poziomie i +1 (takich krawędzi jest zero lub więcej). Tak więc dla każdego wierzchołka v utrzymujemy trzy zestawy krawędzi (wsteczny, lokalny i przedni).

Gdy krawędź u - v zostanie usunięta, są dwie możliwości: albo u i v są na tym samym poziomie, albo na poziomach, których liczba różni się o 1.

Przypadek 1: zarówno u, jak i v są na tym samym poziomie. W takim przypadku usunięcie krawędzi nie może zmienić komponentów. Krawędź jest po prostu usuwana ze zbioru lokalnych krawędzi u i v , a proces B zostaje zatrzymany (a zatem proces A również zostaje zatrzymany). Nasza struktura BFS jest nadal aktualna.

Przypadek 2

u i v są na różnych poziomach. Bez utraty ogólności załóżmy, że u jest na poziomie i -1, a v na poziomie i ; stąd krawędź powinna zostać usunięta z przodu ( u ) i z tyłu ( v ).

Przypadek 2.1: Jeśli nowy wstecz ( v ) nie jest pusty, to składowe się nie zmieniły: istnieją inne krawędzie, które łączą v wstecz. Proces B zostaje zatrzymany (i proces A również zostaje zatrzymany).
Przypadek 2.2: Jeśli nowy reverse( v ) jest pusty, to v nie jest już połączony z poziomem i −1, a więc jego odległość od pierwiastka nie jest już i ; musi to być co najmniej i +1. Dodatkowo mogą istnieć inne wierzchołki, połączone z v , których odległość od korzenia wzrasta w wyniku usunięcia. Aby obliczyć zaktualizowane odległości, używamy kolejki Q, która początkowo zawiera tylko wierzchołek v .

Podczas gdy Q nie jest puste:

w := usuń z kolejki (Q)
Usuń w z jego poziomu (powiedzmy j ) i umieść go na następnym poziomie ( j +1).
Zaktualizuj lokalnych sąsiadów:
- Dla każdej krawędzi w − x w local( w ), usuń ją z local( x ) i umieść w forward( x ).
- wstecz( w ) := lokalnie ( w )
Zaktualizuj przyszłych sąsiadów:
- Dla każdej krawędzi w - x w forward( w ), usuń ją z reverse( x ) i umieść w local( x ); jeśli nowy wstecz ( x ) jest pusty, wstaw x do kolejki Q.
- lokalny( w ) := do przodu ( w )
- do przodu( w ) := pusty zbiór
Jeśli nowy wstecz ( w ) jest pusty, wstaw ponownie w do kolejki Q.

Jeśli usunięcie krawędzi nie uszkodzi żadnego komponentu i jesteśmy w przypadku 2.2, to ostatecznie procedura zostanie zatrzymana. W tym przypadku łatwo zauważyć, że struktura BFS jest utrzymana poprawnie. Jeśli jego usunięcie spowoduje uszkodzenie komponentu, procedura nie zatrzyma się sama. Jednak proces A, rozpoznając przerwę, zatrzyma się i zatrzymają się oba procesy. W tym przypadku wszystkie zmiany dokonane w strukturze BFS są ignorowane i wracamy do struktury BFS, którą mieliśmy tuż przed usunięciem, z wyjątkiem tego, że usunięta krawędź jest teraz zastępowana przez sztuczną krawędź. Oczywiście w tym przypadku v jest teraz korzeniem drzewa, które zawiera nowy komponent i być może dodatkowe komponenty poprzez inne sztuczne krawędzie. Ponadto nie ma krawędzi łączących potomków $v$ z dowolnymi wierzchołkami, które nie są potomkami $v$ , z wyjątkiem sztucznej krawędzi ${\ displaystyle uv}$ .

za każdym razem, gdy w procedurze przetwarzana jest krawędź, jeden z jej punktów końcowych spada o jeden poziom. Ponieważ najniższym poziomem, jaki może osiągnąć wierzchołek w przebiegach zakończonych przez proces B, jest ${\ Displaystyle | V | -1}$ , koszt na krawędź jest ograniczony przez ${\ Displaystyle 2 | V |}$ . Stąd amortyzowany czas na operację usunięcia wynosi ${\ Displaystyle O (n)}$ .

W pełni dynamiczna łączność

Grafy acykliczne (lasy)

Las może być reprezentowany za pomocą kolekcji drzew ciętych przez Linki lub drzew tras Eulera . Wtedy problem łączności dynamicznej można łatwo rozwiązać, ponieważ dla każdych dwóch węzłów x,y, x jest połączony z y wtedy i tylko wtedy, gdy FindRoot(x)=FindRoot(y). Zamortyzowany czas aktualizacji i czas zapytania to O(log( n )).

Wykresy ogólne

Ogólny graf może być reprezentowany przez jego rozpinający się las - las, który zawiera drzewo dla każdego połączonego elementu grafu. Nazywamy ten rozpinający las F . Samo F może być reprezentowane przez las drzew Eulera .

Operacje Query i Insert są realizowane przy użyciu odpowiednich operacji na drzewach ET reprezentujących F . Trudną operacją jest Usuń, aw szczególności usunięcie krawędzi, która jest zawarta w jednym z drzew rozpinających F . To rozbija drzewo rozpinające na dwa drzewa, ale możliwe jest, że łączy je inna krawędź. Wyzwaniem jest szybkie znalezienie takiej zastępczej krawędzi, jeśli taka istnieje. Wymaga to bardziej złożonej struktury danych. Poniżej opisano kilka takich struktur.

Struktura poziomu

Każdej krawędzi na wykresie przypisany jest poziom . Niech L = lg n . Poziom każdej krawędzi wstawionej do wykresu jest inicjowany na L i może spadać w kierunku 0 podczas operacji usuwania.

Dla każdego i między 0 a L , zdefiniuj Gi jako podgraf składający się z krawędzi na poziomie i lub niższym, a Fi jako las rozpinający Gi . Nasz wcześniejszy las F nazywa się teraz FL . Zachowamy malejący ciąg lasów FL ⊇ ... ⊇ F 0.

Operacje

Operacje Query i Insert używają tylko największego lasu FL . Mniejsze podgrafy są sprawdzane tylko podczas operacji usuwania, aw szczególności podczas usuwania krawędzi, która jest zawarta w jednym z drzew rozpinających FL .

usuniemy taką krawędź e = x − y , to najpierw usuniemy ją z FL i ze wszystkich mniejszych lasów rozpinających, do których należy, czyli z każdego Fi o poziomie i ≥ ( e ). Następnie szukamy krawędzi zastępczej.

Zacznij od najmniejszego lasu rozpinającego, który zawierał e , a mianowicie Fi z i = poziom ( e ). Krawędź e należy do pewnego drzewa T ⊆ Fi . Po usunięciu e drzewo T zostaje rozbite na dwa mniejsze drzewa: Tx zawierające węzeł x i Ty zawierające węzeł y . Krawędź Gi jest krawędzią zastępczą wtedy i tylko wtedy, gdy łączy węzeł w Tx z węzłem w Ty . Załóżmy wlog, że Tx jest mniejszym drzewem (tj. zawiera co najwyżej połowę węzłów drzewa T ; rozmiar każdego poddrzewa możemy określić za pomocą adnotacji dodanej do drzew Eulera).

Najpierw zmniejszamy poziom każdej krawędzi Tx o 1. Następnie zapętlamy wszystkie krawędzie ε z poziomem i i co najmniej jednym węzłem w Tx :

Jeśli drugi węzeł ε znajduje się w Ty , to zostanie znaleziona krawędź zastępcza! Dodaj tę krawędź do Fi i do wszystkich lasów zawierających do FL i zakończ. Rozciągające się lasy są naprawione. Zauważ, że aby zapłacić za to wyszukiwanie, zmniejszamy poziom krawędzi odwiedzanych podczas wyszukiwania.
Jeśli drugi węzeł ε znajduje się w Tx , to nie jest to krawędź zastępcza i aby „ukarać” go za marnowanie naszego czasu, obniżamy jego poziom o 1.

Analiza

Poziom każdej krawędzi zmniejszy się co najwyżej lg n razy. Dlaczego? Ponieważ z każdym spadkiem wpada w drzewo, którego rozmiar jest co najwyżej o połowę mniejszy od jego drzewa na poprzednim poziomie. Tak więc na każdym poziomie i liczba węzłów w każdym połączonym komponencie wynosi co najwyżej 2 ⁱ . Stąd poziom krawędzi jest zawsze co najmniej 0.

$Znalezienie każdej krawędzi,$ poziom jest zmniejszony, zajmuje na drzewie ET) W sumie każda wstawiona krawędź zajmuje ${\ Displaystyle O (\ lg ^ {2} n)}$ czasu, zanim zostanie usunięta, więc amortyzowany czas usunięcia wynosi ${\ styl wyświetlania O(\lg ^{2}n)}$ . Pozostała $(\ lg n)}$ usuwania również zajmuje $⁡$ musimy usunąć krawędź co ${$ $poziomów ,$ z każdego poziomu trwa przy użyciu operacji ET

W sumie zamortyzowany czas na aktualizację wynosi ${\ Displaystyle O (\ lg ^ {2} n)}$ . Czas na zapytanie można poprawić do ${\ Displaystyle O (\ lg n / \ lg \ lg n)}$ .

Jednak w najgorszym przypadku czas na aktualizację może wynosić ${\ displaystyle O (n)}$ . Pytanie, czy można poprawić czas w najgorszym przypadku, było kwestią otwartą, dopóki nie zostało pozytywnie rozwiązane przez strukturę Cutset.

Struktura Cutset

Mając dany wykres G(V,E) i podzbiór T⊆V, zdefiniuj zbiór przekrojów(T) jako zbiór krawędzi łączących T z V\T. Struktura zbioru przekrojów to struktura danych, która bez przechowywania całego grafu w pamięci może szybko znaleźć krawędź w zestawie przekrojów, jeśli taka krawędź istnieje.

Zacznij od nadania numeru każdemu wierzchołkowi. Załóżmy, że istnieje n wierzchołków; wtedy każdy wierzchołek może być reprezentowany przez liczbę z lg( n ) bitami. Następnie każdej krawędzi nadaj liczbę, będącą konkatenacją liczb jej wierzchołków - liczbę z 2 bitami lg( n ).

Dla każdego wierzchołka v oblicz i zachowaj xor( v ), który jest xorem liczb wszystkich przylegających do niego krawędzi.

Teraz dla każdego podzbioru T⊆V można obliczyć xor(T) = xor wartości wszystkich wierzchołków w T. Rozważmy krawędź e = u − v , która jest wewnętrzną krawędzią T (tj. zarówno u , jak i v są w T). Liczba e jest podwójnie zawarta w xor(T) - raz dla u i raz dla v . Ponieważ xor każdej liczby z samą sobą wynosi 0, e znika i nie wpływa na xor(T). Zatem xor(T) jest w rzeczywistości xorem wszystkich krawędzi w cutset(T). Istnieje kilka opcji:

Jeśli xor(T)=0, możemy śmiało odpowiedzieć, że cutset(T) jest pusty.
Jeśli xor(T) jest liczbą rzeczywistej krawędzi e , to prawdopodobnie e jest jedyną krawędzią w cutset(T) i możemy zwrócić e . Możemy również odczytać punkty końcowe e z liczby e , dzieląc ją na skrajne lewe bity lg( n ) i skrajne prawe bity lg( n ).
Trzecia opcja polega na tym, że xor(T) jest liczbą różną od zera, która nie reprezentuje rzeczywistej krawędzi. Może się to zdarzyć tylko wtedy, gdy w cutset(T) są dwie lub więcej krawędzi, ponieważ w takim przypadku xor(T) jest xor kilku liczb krawędzi. W takim przypadku zgłaszamy „niepowodzenie”, ponieważ wiemy, że zestaw elementów ciętych zawiera krawędzie, ale nie możemy zidentyfikować żadnej pojedynczej krawędzi.

Naszym celem jest teraz obsłużenie tej trzeciej opcji.

Najpierw utwórz sekwencję poziomów lg( n ) struktur zbioru przekrojów, z których każda zawiera mniej więcej połowę krawędzi z górnego poziomu (tj. dla każdego poziomu wybierz każdą krawędź z górnego poziomu z prawdopodobieństwem 1/2). Jeśli na pierwszym poziomie xor(T) zwróci niedozwoloną wartość, co oznacza, że cutset(T) ma dwie lub więcej krawędzi, to jest szansa, że na następnym poziomie, który zawiera mniej krawędzi, xor(T) zwróci poprawną wartość, ponieważ cutset(T) będzie zawierał pojedynczą krawędź. Jeśli xor(T) nadal zwraca niedozwoloną wartość, przejdź do następnego poziomu itd. Ponieważ liczba krawędzi maleje, istnieją dwa przypadki:

Dobrym przypadkiem jest to, że ostatecznie znajdujemy poziom, w którym cutset(T) zawiera pojedynczą krawędź; następnie zwracamy tę krawędź i kończymy.
Zły przypadek polega na tym, że w końcu znajdujemy poziom, w którym cutset(T) nie zawiera żadnych krawędzi; następnie zgłaszamy „niepowodzenie”, ponieważ wiemy, że w zestawie cięć znajdują się krawędzie, ale nie możemy zidentyfikować żadnej pojedynczej krawędzi.

Można udowodnić, że prawdopodobieństwo sukcesu wynosi co najmniej 1/9.

Następnie utwórz zbiór niezależnych wersji C lg( n ) struktury poziomów, gdzie C jest stałą. W każdej wersji wykonaj niezależną losową redukcję krawędzi z poziomu na poziom. Wypróbuj każde zapytanie w każdej z wersji, aż jedno z nich się powiedzie. Prawdopodobieństwo, że wszystkie wersje zakończą się niepowodzeniem, wynosi co najwyżej:

{\ Displaystyle (1-1/9) ^ {C \ lg {n}} = 2 ^ {- 0,17C \lg {n}}=n^{-0,17C}}

Poprzez odpowiedni dobór C możemy dowolnie zbliżyć prawdopodobieństwo niepowodzenia do zera.

Operacje

Możemy dodać strukturę cutset do dynamicznej struktury łączności.

Operacje Insert i Delete na strukturze cutset są wykonywane dokładnie w ten sam sposób: wstawiona/usunięta krawędź jest poddawana operacji XOR w obu jej punktach końcowych.

Kiedy krawędź jest usuwana z lasu rozpinającego używanego dla dynamicznej struktury łączności, struktura cutset jest używana do znalezienia zastępczej krawędzi.

Analiza

Pojedyncza struktura zbioru fragmentów wymaga tylko pamięci O ( n lg n ) — tylko jednej liczby z 2 lg n bitów dla każdego z n wierzchołków. Nie musimy zachowywać samych krawędzi. W przypadku gęstych grafów jest to znacznie tańsze niż przechowywanie całego wykresu w pamięci.

Musimy zachować wersje lg( n ), z których każda zawiera poziomy lg( n ). W związku z tym całkowite zapotrzebowanie na pamięć wynosi ${\ Displaystyle O (n \ lg ^ {3} n)}$ .

W najgorszym przypadku czas zapytania wynosi O (polylog( n )). Kontrastuje to ze strukturą Poziomu , w której czas zapytania wynosi O (polylog( n )) amortyzowany, ale czas w najgorszym przypadku to O ( n ).

Dynamiczna łączność offline

Jeśli kolejność usuwania krawędzi jest znana z wyprzedzeniem, możemy rozwiązać problem dynamicznej łączności w log(n) na zapytanie. Jeśli uda nam się utrzymać las o maksymalnej rozpiętości, w którym krawędzie są uporządkowane według czasu ich usunięcia, wiemy, że kiedy usuniemy część lasu, nie ma możliwej krawędzi, która mogłaby ją zastąpić. Gdyby istniała krawędź, która łączy te same dwa komponenty, co usunięta krawędź, to ta druga krawędź byłaby częścią lasu o maksymalnym rozpiętości zamiast krawędzi, którą usunęliśmy. To sprawia, że operacja usuwania jest banalna: wystarczy podzielić drzewo na dwie części, jeśli krawędź do usunięcia jest częścią naszego lasu, lub zignorować operację w przeciwnym razie.

Dodanie krawędzi jest nieco bardziej skomplikowane. Jeśli dodamy krawędź edge e od u do v, to jeśli u i v nie są połączone, to ta krawędź będzie częścią lasu o maksymalnej rozpiętości. Jeśli są połączone, chcemy dodać u->v do naszego lasu, jeśli może to poprawić nasz las o maksymalnej rozpiętości. Aby to zrobić, musimy szybko sprawdzić, która krawędź ma najmniejszy czas usuwania na ścieżce od u do v. Jeśli czas usuwania tej krawędzi następuje po czasie usuwania e, to e nie może poprawić naszego lasu o maksymalnym rozpiętości. W przeciwnym razie drugą krawędź należy usunąć i zastąpić e.

Wymaga to od nas wykonania następujących operacji: dodania krawędzi, wycięcia krawędzi i zapytania o minimalną krawędź na ścieżce, co można dość łatwo wykonać za pomocą drzewa ciętego łącza w log(n) na operację.

Zobacz też

Zobacz także: Thorup, M. (2000). Niemal optymalna, w pełni dynamiczna łączność z wykresami . Materiały z trzydziestego drugiego dorocznego sympozjum ACM poświęconego teorii obliczeń - STOC '00. P. 343. doi : 10.1145/335305.335345 . ISBN 1581131844 .