Poniższe rozważania dotyczą jedynie grafów nieskierowanych.
Dwuspójna składowa to taki największy zbiór krawędzi, że każda krawędź jest
w cyklu z pewną inną z tego zbioru. A bardziej zrozumiale, jest to taka część
grafu, że między każdą parą wierzchołków istnieją dwie rozłączne (bez wspólnych
krawędzi) drogi. Przy znajdowaniu dwuspójnych składowych określa się
przynależność krawędzi grafu do odpowiedniej składowej; nie można tego
zrobić z wierzchołkami, ponieważ jeden wierzchołek może należeć do kilku
składowych.
Punkt artykulacji to taki wierzchołek, którego usunięcie rozspójnia graf.
Warto zauważyć, że taki wierzchołek (i tylko taki) może należeć jednocześnie
do kilku dwuspójnych składowych.
Mostem nazywamy taką krawędź, której usunięcie rozspójnia graf. Warto zauważyć,
że końce mostu są punktami artykulacji.
Można spotkać się z jeszcze inną definicją dwuspójnej składowej.
Zdefiniujmy sobie relację na krawędziach: dwie krawędzie są w relacji gdy
są równe lub istnieje cykl zawierający obie. Taka relacja jest relacją
równoważności, a klasami abstrakcji są właśnie dwuspójne składowe.
Według tej definicji most jest sam w sobie dwuspójną składową (jako
jednoelementowa klasa abstrakcji). I własńie to zakłada przedstawiony przeze
mnie poniżej algorytm na znajdowanie składowych (więc się nie zdziwcie). Można
ten fakt wykorzystać do znajdowania mostów w grafie, ale myślę, że podany
przeze mnie inny sposób (też poniżej) jest znacznie prostszy.
Bardzo ważną i przydatną rzeczą w poniższych algorytmach jest funkcja (tablica)
Low. Właściwie to "wyliczenie" jej załatwia natychmiastowo problem
znajdowania mostów i punktów artykulacji (z dwuspójnymi składowymi trza się
będzie jeszcze trochę pomęczyć).
Znajdowanie Low opiera się na przeszukiwaniu w głąb. Niezbędna
będzie numeracja pre-order, więc przyjmijmy, że D[v] będzie oznaczać
numerek w tej numeracji wierzchołka v.
Zatem konkretniej. Przypuśćmy, że zapuściliśmy DFSa i doszliśmy do wierzchołka
v. Żeby obliczyć Low dla niego to musimy rozpatrzyć pewne
wartości dla sąsiadujących z nim wierzchołków w: Low[w] jeżeli
wierzchołka w jeszcze nie odwiedziliśmy naszym DFSem, D[w] jeżeli
wierzchołek w już odwiedziliśmy, ale (!!!) nie przeszliśmy bezpośrednio
z niego w DFSie do v (czyli w nie jest ojcem v
w drzewie przeszukiwania w głąb). Teraz jedynie bierzemy najmniejszą z powyższych
wartości i z samego D[v] i to właśnie ona jest szukaną wartością
Low[v].
Ta w miarę formalna definicja może nie być do końca jasna, więc już tłumaczę.
Jeżeli od wierzchołka v jesteśmy w stanie dojść do już odwiedzonego
wierzchołka u inną drogą niż tą którą doszliśmy z u do v
w naszym DFSie, to bierzemy pod uwagę wartość D[u]. I najmniejsza
z tych wartości to właśnie Low[v]. Chyba, że z v nie można
dojść do żadnego odwiedzonego wcześniej wierzchołka, to wtedy
Low[v]=D[v].
W praktyce znajdowanie funkcji (tablicy) Low może wyglądać następująco:
{
N - liczba wierzcholkow
D[1..N] - tablica numeracji pre-order
P[1..N] - tablica poprzednikow (tzn. do wierzch. i-tego przeszlismy z wierzch. P[i])
Low[1..N] - tablica szukanej funkcji Low
}
procedure Visit(v, father: Integer);
{dodatkowym parametrem jest wierzch., z ktorego przyszlismy}
begin
P[v]:=father;
D[v]:=time; {przydzielenie numerka w numeracji pre-order}
Inc(time);
Low[v]:=D[v]; {Low[v] nie moze byc wieksze niz D[v]}
for i:=Nieghbour(v) do {petla po sasiadach wierzch. v}
if i<>father then {nie rozwazamy sasiada, z ktorego przyszlismy}
if D[i]=-1 then {jesli wierzch. i jest nieodwiedzony}
begin
Visit(i,v); {przechodzimy rekurencyjnie do wierzch. i}
if Low[v]>Low[i] then {oraz badamy Low tego wierzcholka}
Low[v]:=Low[i];
end else {jesli wierzch. i byl juz odwiedzony}
if Low[v]>D[i] then {badamy jego numer pre-order}
Low[v]:=D[i];
end;
procedure DFS;
begin
for i:=1 to N do
D[i]:=-1; {oznaczamy wszystkie wierzcholki jako nieodwiedzone}
time:=1; {zmienna potrzebna do numeracji}
for i:=1 to N do
if D[i]=-1 then {jesli wierzch. i jest niodwiedzony to ...}
Visit(i,-1); {przechodzimy do wierzch. i}
end;
No. Teraz jak znamy już funkcję Low znalezienie punktów artykulacji
nie jest już wielkim problemem. Otóż wierzchołek v jest punktem artykulacji
gdy: jeżeli jest korzeniem w drzewie DFS (P[v]=-1), to ma więcej
niż jednego syna; jeżeli nie jest korzeniem, to dla któregoś z jego synów w
w drzewie DFS spełniony jest warunek Low[w]>=D[v].
A teraz któtkie wytłumaczenie (dla zainteresowanych). Low[w] to jest taki
"najmniejszy" wierzchołek, do którego można dotrzeć z w inną drogą niż
przyszliśmy. Założyliśmy, że w jest synem v w drzewie/lesie
przeszukiwania w głąb, czyli to właśnie z v przyszliśmy. A skoro
Low[w]>=D[v] to nie jesteśmy w stanie z w dojść
do przodków v w drzewie/lesie inną drogą niż przez v
(bo v ma przecież większy numer od swoich przodków).
Więc gdybyśmy usunęli v to rozpspójnili byśmy graf, zatem jest on
punktem artykulacji.
To rozważanie jednak nie dotyczy korzenia drzewa/lasu przeszukiwania w głąb,
bo przecież nie można przejść do jego przodków (skoro ich nie ma), a wcale
nie musi być punktem artykulacji. Tutaj warto zauważyć, że jeżeli korzeń
ma kilku synów, to leży on na jedynej drodze łączącej tych synów. Gdyby było
inaczej, to jeden z tych synów byłby potomkiem drugiego, zamiast być synem korzenia
(trochę zagmatwałęm, co?). Co za tym idzie usunięcie korzenia oddzieliłoby od
siebie jego synów i graf uległby rozspójnieniu.
Na jedną rzecz chciałbym zwrócić uwagę. Że drzewo DFS może być w ogólności lasem, czyli może być kilka korzeni. W przypadku grafów nieskierowanych (jakimi się teraz zajmujemy) jedno drzewo z lasu odpowiada jednej spójnej składowej.
Może jednak wyniknąć jeszcze jeden praktyczny problem. Mianowicie tablica P
określa nam ojców każdego wierzchołka w drzewie DFS, a my potrzebujemy synów.
Można zawsze przetłumaczyć jedną reprezentację drzewa na drugą, ale to jest
zbyt pracochłonne.
Możemy spojrzeć na problem odwrotnie: jeżeli dla pewnego wierzchołka v
o ojcu P[v] (ojciec nie może być korzeniem, czyli P[P[v]]<>-1)
spełniony jest warunek Low[v]>=D[P[v]] to P[v] jest
punktem artykulacji.
Ten problem można uniknąć jeżeli wyznaczanie punktów artykulacji zrobimy
podczas wykonywania DFSa.
Ze znajdowaniem mostów sprawa jest jeszcze prostsza. Po prostu każdy
wierzchołek v (o ile nie jest korzeniem), który ma Low[v]=D[v]
tworzy ze swoim ojcem (P[v]) most.
Tutaj z wytłumaczeniem będzie nieco łatwiej. Skoro Low[v]=D[v] to nie
można przejść do żadnego jego poprzednika w drzewie przeszukiwania w głąb (inną
drogą niż doszliśmy). Co za tym idzie z żadnym poprzednikiem nie leży w jednym
cyklu, w tym także ze swoim bezpośrednim poprzednikiem P[v].
Zatem krawędź v-P[v] nie leży w żadnym cyklu, a skoro tak to nie może
należeć do żadnej dwuspójnej składowej, więc jest mostem.
Warto zauważyć, że mostów w grafie może być co najwyżej V-1, gdzie V jest liczbą wierzchołków w grafie. Ale to tylko taka praktyczna uwaga o niewielkim znaczeniu.
Ze znajdowaniem dwuspójnych składowych już się zaczyna pewien problem. Nie jest to takie łatwe jak znajdowanie mostów czy punktów artykulacji. Algorytm należy wykonywać podczas wykonywania DFSa i obliczania funkcji Low, przy użyciu pewnej dodatkowej struktury.
Bardzo przydatną rzeczą do znajdowania dwuspójnych składowych będzie stos.
Otóż podczas wykonywania DFSa (razem z obliczaniem Low) odkładamy wszystkie
napotkane krawędzie na stos. Kładziemy nie tylko te, które ewidentnie "przeszliśmy"
(przechodząc z wierzchołka do wierzchołka), ale także te, które wykorzystaliśmy
do "podejrzenia" czy jakiś wierzchołek już został odwiedzony i zaprowadziły
nas do poprzednika w drzewie/lesie przeszukiwania w głąb (czyli do wierzchołka
o mniejszym numerze pre-order).
Przypuśćmy, że doszliśmy naszym DFSem do pewnego wierzchołka v i jednym
z jego nieodwiedzonych następników jest w. Zatem przechodzimy rekurencyjnie
do w (odkładamy v-w na sotos), z niego też chodzimy sobie dalej
(odkładając różne inne krawędzie) i w końcu rekurencyjnie wrócimy do v
(standardowa procedura w przypadku DFSa). Jeżeli wtedy się okaże, że
Low[w]>=D[v] to znaczy, że v jest punktem artykulacji
(no, nie zawsze, ale tutaj akurat nie ma to znaczenia), który oddziela
dwuspójną składową zawierającą krawędź v-w od pozostałej części grafu
(no, też nie tak do końca). Objawia się to tym, że na stosie są wszystkie
krawędzie tej składowej, oddzielone od pozostałych krawędzią v-w (która,
jako że odłożona najwcześniej, jest najgłębiej stosu). Wystarczy jedynie zdjąć te
krawędzie i już.
Przed chwilą napisałem, że wierzchołek v oddziela nam dwuspójną składową
od reszty grafu, co nie jest prawdą. W rzeczywistości oddziela nam kilka całych
składowych (w tym także tą zawierającą krawędź v-w)od reszty.
Na szczęście w praktyce nie musimy się tym przejmować, ponieważ pozostałe składowe
"obsłużymy" zanim wrócimy do wierzchołka v i ich krawędzie znikną ze stosu.
Z własnego doświadczenia wiem, że opis teoretyczny tego algorytmu nie ma szans być przejrzysty i zrozumiały. Dopiero po zobaczeniu kodu wszystko się rozjaśnia. Dlatego postanowiłem na poparcie moich pokrętnych wywodów pokazać programik. Wynikiem jego działania jest tablica C[e], w której zapisane są numery dwuspójnych składowych, do których są dane krawędzie przypisane.
{
N - liczba wierzcholkow
D[1..N] - tablica numeracji pre-order
Low[1..N] - tablica funkcji Low
C[krawedzie] - tablicy przynaleznosci krawedzi do dwuspojnych skladowych
}
procedure Visit(v, father: Integer);
{dodatkowym parametrem jest wierzch., z ktorego przyszlismy}
begin
D[v]:=time; {przydzielenie numerka w numeracji pre-order}
Inc(time);
Low[v]:=D[v]; {Low[v] nie moze byc wieksze niz D[v]}
for i:=Nieghbour(v) do {petla po sasiadach wierzch. v}
if i<>father then {nie rozwazamy sasiada, z ktorego przyszlismy}
if D[i]=-1 then {jesli wierzch. i jest nieodwiedzony}
begin
Put_On_Stack(v<->i); {odkladamy krawedz, po ktorej przejdziemy na stos}
Visit(i,v); {przechodzimy rekurencyjnie do wierzch. i}
if Low[v]>Low[i] then {oraz badamy Low tego wierzcholka}
Low[v]:=Low[i];
if Low[i]>=D[v] then {wykryto dwuspojna skladowa}
begin
Inc(No); {rozpatrujemy skladowa o kolejnym numerze}
repeat
Get_From_Stack(e); {zdejmij ze stosu kolejna krawedz skladowej}
C[e]:=No; {oznacza, ze krawedz nalezy do skladowej o numerze No}
until e=v<->i;
end;
end else {jesli wierzch. i byl juz odwiedzony}
begin
if D[v]>D[i] then {jesli i jest poprzednikiem v w drzewie}
Put_On_Stack(v<->i); {odkladamy "podgladana" krawedz}
if Low[v]>D[i] then {badamy numer pre-order wierzch. i}
Low[v]:=D[i];
end;
end;
procedure FindConstituent;
begin
for i:=1 to N do
D[i]:=-1; {oznaczamy wszystkie wierzcholki jako nieodwiedzone}
time:=1; {zmienna potrzebna do numeracji pre-order}
No:=0; {zmienna potrzebna do numeracji skladowych}
for i:=1 to N do
if D[i]=-1 then {jesli wierzch. i jest nieodwiedzony to ...}
Visit(i,-1); {przechodzimy do wierzch. i}
end;
Algorytm znajdowania punktów artykulacji, mostów i dwuspójnych składowych sprowadza się całkowicie do wykonania algorytmu DFS (z pewnymi dodatkowymi czynnościami). Wymaga to kilkukrotnego (ale ograniczonego przez stałą) przejrzenia każdej krawędzi, czyli algorytm(y) działa(ją) w czasie O(E) (o ile została zastosowana sensowna reprezentacja grafu).