Silnie spójne składowe, punkty artykulacji oraz dwuspójność w grafach nieskierowanych
Nasze rozważania na tematy pewnej charakterystyki grafów zaczniemy od zagadnienia silni spójnych składowych ( Strongly Connected Components ) oraz ich pewnym zastosowaniom.
Silnie spójne składowe
Co kryje się pod tą, z początku enigmatyczną nazwą? Rozważmy graf skierowany o V wierzchołkach i E krawędziach. Chcielibyśmy dowiedzieć się , które “pola” wierzchołków są tak ułożone, że każdy jeden wierzchołek jest osiągalny z drugiego. I to wstępnie formalizuje nam definicję silnej spójnej składowej – mianowicie: silna spójna składowa to taki maksymalny podgraf grafu skierowanego, że każde 2 występujące w nim wierzchołki są dostępne jeden z drugiego. W szczególności, jeżeli istnieje bezpośrednia krawędź łącząca wierzchołek z nim samym, to jest on również definiowany jako silnia spójna składowa. Spróbujmy pokazać jak wygląda to na rysunku:
Obszary zamalowane tworzą silnie spójne składowe
Algorytm znajdowania silni spójnych składowych
Algorytm znajdowania takich maksymalnych podgrafów jest jednym z podstawowych zastosowań przeszukiwania “wgłąb” grafu (Depth-First-Search). Za pomocą tego algorytmu dokonamy podziału grafu na graf składowych. Taki podział może byc w wielu przypadkach bardzo dobrym wstępem do obliczenia bardziej złożonego problemu, w którym pewna właściwość jest zachowana dla zbioru wierzchołków z jednej składowej jak i każdego z tych wierzchołków z osobna. Pierwszym krokiem jaki należy wykonać jest znalezienie transpozycji grafu G , czyli określenie takiego grafu, że jeżeli w G istniała krawędź od u do v to w grafie Gt krawędź będzie odwrotnie skierowana tj. od v do u. Kolejnym krokiem jest za pomocą pierwszego przeszukiwania wgłąb grafu G znalezienie numeracji tzw post-order czyli czasu przetworzenie wierzchołka podczas przechodzenia grafu wgłąb. Następnym i zarazem ostatnim krokiem jest wykonanie DFSa na transponowanym grafie Gt, lecz rozważając wierzchołki w kolejności nierosnącej wartości czasu post-order. Poniżej przestawiam pseudokod wykonania całego algorytmu W zaprezentowanej przeze mnie metodzie będziemy “kolorować” wierzchołki należace do tej samej składowej.
n – liczba wierzchołków
postorder[0..n-1] – tablica numeracji postorder
colour[0..n-1] – kolor aktualnej składowej
visited[0..n-1] – tablica, czy dany wierzchołek był już odwiedzony
for i:=0 to n-1 visited_ := 0;
calculate_preorder( u , graph )
. . .visited :=1;
. . .foreach w adjacent to u
. . . . . .if not visited w
. . . . . . . . .calculate_preorder ( w, graph );
. . .preorder[time] := u;
. . .time:=time+1;
find_components( u, graph, c )
. . .visited := 1;
. . .colour := c;
. . .foreach w adjacent to u
. . . . . .if not visited w
. . . . . . . . .find_components( w, graph, c );
dfs ( )
. . . for i:=0 to n-1 visited_ := 0;
. . . time :=0;
. . . for i:=0 to n-1
. . . . . . if not visited i
. . . . . . . . . calculate_preorder( u , G );
. . . for i:=0 to n-1 visited_ := 0;
. . . c : = 0;
. . . for i:=n-1 downto 0
. . . . . . c := c+1;
. . . . . . if not visited preorder_
. . . . . . . . . find_components ( preorder_ , Gt , c )
Zastosowania
Mniej formalne podejście do tematu może wskazać nam przykładowe zastosowania użycia takiego algorytmu. Oprócz wspomnianej wyżej wstępnej minimalizacji pewnych bardziej skomplikowanych problemów , możemy zastanowić się nad strukturą lotnisk i lotów jakie proponują. Chodzi mianowicie o to, czy z pomocą dostępnych lotów możemy dostać się na każde inne lotnisko? Troche mniej przemawiającym do wyobraźni przykładem zastosowania powyższych właściwości grafu jest problem 2-MAX-SATISFIABLITY – czyli problem spełnialności pewnych dwuargumentowych formuł logicznych. Istnieje algorytm stwierdzający spełnialność takich formuł , który wykorzystuje silnie spójne składowe. Warto dodać , iż problem , który dotyczy już 3 argumentów tj dowolny 3-MAX-SATISFIABLITY jest już problemem klasy NP.
Punkty artykulacji oraz dwuspójność grafu
Zacznijmy od problemu bardzo nam współczesnemu. Przypuśćmy, że jesteśmy grupą terrorystyczną i planujemy atak na sieć komunikacyjną w pewnym mieście – pytanie brzmi , który węzeł powinniśmy wysadzić, żeby osiągnąć jak “najlepszy” rezultat – tj rozerwać (rozspójnić) atakowaną sieć.
Każdy wierzchołek w grafie nieskierowanym, którego usunięcie spowoduje rozspójnienie grafu nazywamy punktem artykulacji (Articulation point). Praktyczne podejście do tego zagadnienia podpowiada nam, iż jest ono znaczące w logistyce transportu. Ważnym jest, żeby rozpoznawać punkty , przez które musi przepłynąć cały ruch. Idąc dalej – graf , który jest bezpieczny na nasze teoretyczne zamachy ;-) , czyli taki, który nie zawiera punktów artykulacji nazywamy grafem dwuspójnym (Biconnected graph). Co więcej , aby rozspójnić nasz “bezpieczny” graf , należy “wysadzić” conajmniej 2 węzły. Rozszerzając nasze zagadnienie można wprowadzić pojęcie dwuspójnej składowej (Biconnected component) , czyli takiego maksymalnego podgrafu, który spełnia warunki dwuspójności. Bardziej formalnie - składowa dwuspójności to taki maksymalny podgraf, że każde dwie krawędzie tego podgrafu leżą na wspólnym cyklu prostym. Warto zauważyć, że taki podział rozpójnia nam graf nie ze względu na wierzchołki , ale na krawędzie!!! tj. w dwóch rozłącznych zbiorach dwuspójnych może wystąpić wspólny wierzchołek i co więcej ten wspólny wierzchołek jest punktem artykulacji! Spróbujmy skomentować dotychczasowe fakty rysunkiem:
Po krótkim zastanowienu się nasuwa nam się pewien wniosek – problem dwóspójności oraz silnie spójne składowe są do siebie bardzo zbliżone. I kłamstwem byłoby powiedzenie, że jest to nieprawda, lecz są pewne bardzo ważne różnice: silnie spójne składowe dotyczą grafów skierowanych, natomiast dwuspójność jest charakterystyką grafów nieskierowanych. Ważną różnicą z poziomu praktycznego jest sam algorytm znajdowania punktów artykulacji oraz dwuspójnych składowych. Jest on niestety o wiele bardziej skomplikowany niż ten prezentowany powyżej.
Algorytm znajdowania punktów artykulacji i dwuspójnych składowych.
Główna idea algorytmu opiera się na przechodzeniu drzewa przeszukiwania DFS wg numeracji pre-order czyli względem czasu odkrycia danego wierzchołka i odpowiedniej reakcja na krawędzie powracające do wierzchołka, który już odwiedziliśmy.
Schemat przechodzenia przez dany graf w celu znalezienia punktów artykulacji wyglądałby w ten sposób:
n – liczba wierzchołków
preorder[0..n-1] – tablica numeracji preorder
visited[0..n-1] – tablica informujaca nas czy dany wierzcholek juz byl odwiedzony
back[0..n-1] – tablica zawierajaca informacje o odleglosciach od poprzednikow
visit ( u, graph , time)
. . . preorder = time;
. . . back = time;
. . . visited = 1;
. . . foreach w adjacent to u
. . . . . . if not visited w
. . . . . . . . . visit ( w , graph, time+1);
. . . . . . . . . if back[w] < preorder
. . . . . . . . . . . . back = min ( back, back[w] );
. . . . . . . . . else if back[w]>=preorder
. . . . . . . . . . . . add u to list of articulation points
. . . . . . else
. . . . . . . . . back[w] = min ( preorder , back[w] ) ;
Powyższy pseudokod realizuje znajdowanie punktów artykulacji, w celu znalezienia dodatkowo zbioru wierzchołków dwuspójności należałoby lekko zmodyfikować powyższy algorytm dodając strukturę stosu i odkładając na niego krawędzie po których przechodzimy, w momencie natrafienia na punkt artykulacji zdejmujemy wszystkie krawędzie do momentu kiedy natrafimy na tą, do której właśnie doszliśmy.
Podsumowanie:
Zaprezentowaliśmy pewne sposoby na jakie można podzielić grafy skierowane i nieskierowane i pod jakim kątem można rozpatrywać pewne problemy. Na sam koniec wypadałoby wspomnieć o złożoności czasowej obu algorytmów. Oba są bardzo efektywne i zapewniają znalezienie rozwiązania w czasie O( V + E ) , gdzie V - l. wierzchołków, E - l. krawędzi. Naturalnie złożoność ta będzie prawdziwa o ile zastosujemy rozsądną reprezentację grafu (np. listową).
Aby dodawać komentarze musisz być zalogowany!