Silnie spójne składowe

_{Wielu zaś pierwszych będzie ostatnimi, a ostatnich pierwszymi(Mt 19,30)}

Definicja

Silnie spójną składową(SSS) grafu skierowanego G nazywamy maksymalny podgraf H, w którym istnieje ścieżka między każdą parą wierzchołków(innymi słowy: można dotrzeć z każdego wierzchołka do każdego należących do H). Pisząc ,,maksymalny" mam na myśli taki, że gdy dodamy dowolny inny podzbiór wierzchołków V nie należący do H, to zepsuje się w.w. warunek SSS.

Musimy zaobserwować pewną ważną rzecz, otóż o silnie spójnych składowych możemy mówić tylko i wyłącznie w przypadku grafu skierowanego! W grafie nieskierowanym to pojęcie zastępuje spójna składowa. Jaka jest różnica? Zobaczymy w poniższych przykładach.

Przyłady

Aby lepiej zrozumieć powyższą definicję pokażemy parę przykładów oraz je przeanalizujemy(nie wiem gdzie wy rysujecie takie ładne grafy więc rysowałem od ręki - wygląda jak wygląda liczy się wnętrze!):
1)

Jak widać na rysunku powyżej wierzchołki 1,2,3,4,6 tworzą jedną spójną składową, ponieważ możemy przejść między każdą parą a dodając którykolwiek z pozostałych wierzchołków już byśmy tego dokonać nie mogli. Analogicznie wierzchołki 5,7,8 także tworzą silnie spójną składową tego grafu! Słowo ,,maksymalna" w definicji NIE oznacza, ze SSS jest tylko jedna w grafie-ta największa!

2)

Należy uważać na takie sytuacje jak ta. Nie możemy powiedzieć, że wierzchołki 1,2,3 tworzą silnie spójną składową ponieważ po dodaniu do wierzchołków 1,2,3 wierzchołki 4,5,6,7 warunek SSS jest zachowany! Tak więc w tym przypadku cały graf tworzy jedną godzilla-wielką silnie spójną skłądową!

3)

Niech was nie zmyli definicja spojnych składowych w grafach nieskierowanych! W tym przypadku graf skierowany G nie posiada żadnej silnie spójnej składowej!

Znajdowanie SSS

Do wyszukania w grafie skierowanym silnie spójnych składowych posłuży nam dobrze znany DFS, a dokładniej dwukrotne jego użycie w odpowiedniej kolejności.

Kroki algorytmu:

1. Odpal najzwyklejszego w świecie DFSa na grafie skierowanym G zapamiętując czasy przetworzenia wierzchołków,
2. Przetransponuj graf G(czyli poprostu odwróć wszystkie krawędzie w grafie G, warto zauważyć, że silnie spójna składowa grafu G jest również silnie spójną składową grafu Grev),
3. Ponownie odpal DFSa ale tym razem na grafie Grev oraz w kolejności czasów przetworzenia(1.)(od najpóźniejszego),
4. Wszystkie wierzchołki, które odwiedzimy za pomocą jednego odpalenia należą do jednej silnie spójnej składowej,
5. Czynność powtarzamy aż do znalezienia wszystkich SSS czyli odwiedzenia wszystkich wierzchołków.

Pseudokod:
G - graf wejściowy, skierowany,
Grev - transponowany graf G, można to robić odrazu przy wczytywaniu lub dopiero przy jego użyciu,
V - ilość wierzchołków w grafie
czas[] - czasy przetworzenia wierzchołków
sss[] - tablica z naszymi wyliczonymi silnie spójnymi składowymi

for i=0 to V
    if(nie odwiedzony wierzchołek i)
        DFS(i);

numer=0;
w kolejności nierosnących czasów odwiedzenia rób:
    if(nie odwiedzony wierzchołek i)
        DFSrev(i,numer++)

I DFSy:

temp_czas=0;

void DFS(v)
{
visited[v]=true;
dla kazdego x sąsiada v w grafie G
    if( x nie odwiedzony)
        DFS(x);
temp_czas++;
czas[v]=temp_czas;
}

void DFSrev(v,numer)
{
visited[v]=true;
**sss[v]=numer;**
dla kazdego x sąsiada v w grafie Grev
    if(x nie odwiedzony)
        DFS(x,numer);
}

Po zakończeniu algorytmu każdy wierzchołek przyporządkowaną ma wartość sss[v] będącą numerem silnie spójnej składowej, do której ów należy.
Jak latwo zauważyć złożoność czasowa tego algorytmu to O(V+E) ponieważ tylko dwukrotnie odpalamy DFSa.

Wszystko jasne i klarowne bo i tak wszyscy zaklepali zadanie S z 1klasy, tak myślę, dziękuje.
aTah

O o
/¯__
| I'MMA FIRIN MAH LAZOR!!! BLAAAAAAAAAAAAARGHHHH!!!
\_¯