Składowa silnie spójna
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
Silnie spójna składowa (SSS) grafu skierowanego G to taki maksymalny podgraf H, a jednocześnie jego spójna składowa, taka, że pomiędzy każdymi dwoma jej wierzchołkami istnieje ścieżka.
Innymi słowy, w silnie spójnej składowej da się dojść z każdego jej wierzchołka do każdego innego.
Dla grafu nieskierowanego każda spójna składowa będzie silnie spójna.
Spis treści |
Zastosowanie [edytuj]
Silnie spójne składowe mają zastosowanie przy de-cyklizacji grafu (usunięciu cykli) - graf silnie spójnych składowych(tzn. graf w którym wierzchołki odpowiadają silnie spójnym składowym, a krawędź istnieje pomiędzy wierzchołkami w.t.w. gdy w wejściowym grafie istniała między silnie spójnymi składowymi) jest acykliczny.
Algorytm [edytuj]
- Dla grafu nieskierowanego, wystarczy wyznaczyć jego spójne składowe. Będą one tożsame z silnie spójnymi składowymi. Można to zrobić, przechodząc drzewo algorytmem DFS, za każdym razem oznaczając wierzchołki połączone krawędzią jednym numerem.
- Dla grafu skierowanego algorytm jest bardziej złożony:
- Obliczamy tabelę czasów przetworzenia Post-order wierzchołków, algorytmem przeszukiwania w głąb (DFS)
- Wywołujemy algorytm DFS dla grafu transponowanego (tj. grafu z odwróconymi zwrotami krawędzi) w kolejności malejących czasów przetworzenia wierzchołków, zapisanych w tablicy Post-order. Wszystkie wierzchołki w jednym drzewie przeszukiwania w głąb należą do jednej silnie spójnej składowej.
W obu przypadkach złożoność czasowa wynosi O(E), pamięciowa O(E+V)
