Silnie połączony komponent - Strongly connected component

Wykres z zaznaczonymi silnie połączonymi komponentami
Odpowiednie tematy na
Łączność wykresu

W matematycznej teorii grafów skierowanych mówi się, że graf jest silnie powiązany, jeśli każdy wierzchołek jest osiągalny z każdego innego wierzchołka. W silnie powiązane elementy arbitralnej skierowane wykresu tworzą przegrodę do subgraphs które same są silnie ze sobą połączone. Możliwe jest przetestowanie silnej spójności grafu lub znalezienie jego silnie powiązanych składników w czasie liniowym (czyli Θ( V  +  E )).

Definicje

Skierowane wykres nazywany jest mocno połączony , jeśli istnieje ścieżka w każdym kierunku, pomiędzy każdą parą wierzchołków grafu. Oznacza to, że ścieżka istnieje od pierwszego wierzchołka w parze do drugiego, a inna ścieżka istnieje od drugiego wierzchołka do pierwszego. W grafie skierowanym G, który sam może nie być silnie połączony, mówi się , że para wierzchołków u i v jest ze sobą silnie związana, jeśli między nimi istnieje ścieżka.

Binarna relacja bycia silnie związany jest relacją równoważności , a indukowane subgraphs swoich klas równoważności nazywane są silnie powiązane komponenty . Równoważnie silnie związany składnik grafu skierowanego G jest podgrafem, który jest silnie powiązany i jest maksymalny z tą właściwością: żadne dodatkowe krawędzie ani wierzchołki z G nie mogą być zawarte w podgrafie bez naruszenia jego właściwości bycia silnie powiązanym. Zbiór silnie połączonych składowych tworzy podział zbioru wierzchołków G .

Żółty skierowany graf acykliczny jest kondensacją niebieskiego grafu skierowanego. Powstaje przez skrócenie każdego silnie połączonego składnika niebieskiego wykresu w pojedynczy żółty wierzchołek.

Jeśli każdy silnie związany komponent zamówienia do jednego wierzchołka otrzymaną Wykres jest skierowany acykliczny wykres The kondensacji z G . Graf skierowany jest acykliczny wtedy i tylko wtedy, gdy nie ma silnie powiązanych podgrafów z więcej niż jednym wierzchołkiem, ponieważ cykl skierowany jest silnie powiązany i każdy nietrywialny silnie powiązany składnik zawiera co najmniej jeden skierowany cykl.

Algorytmy

Algorytmy czasu liniowego oparte na DFS

Kilka algorytmów opartych na przeszukiwaniu wgłębnym oblicza silnie połączone komponenty w czasie liniowym .

  • Algorytm Kosaraju używa dwóch przejść pierwszego poszukiwania głębokości . Pierwszy, w oryginalnym grafie, służy do wyboru kolejności, w której zewnętrzna pętla wyszukiwania o drugiej głębokości najpierw testuje wierzchołki pod kątem już odwiedzonych i rekursywnie je eksploruje, jeśli nie. Drugie przeszukiwanie pierwszej głębokości odbywa się na grafie transpozycji oryginalnego grafu, a każda eksploracja rekurencyjna znajduje jeden nowy silnie powiązany składnik. Jego nazwa pochodzi od S. Rao Kosaraju , który go opisał (ale nie opublikował swoich wyników) w 1978 roku; Micha Sharir opublikował ją później w 1981 roku.
  • Algorytm silnie powiązanych komponentów Tarjana , opublikowany przez Roberta Tarjana w 1972 r., wykonuje pierwsze wyszukiwanie w jednym przejściu. Utrzymuje stos wierzchołków, które zostały zbadane przez wyszukiwanie, ale jeszcze nie zostały przypisane do komponentu, i oblicza „niskie liczby” każdego wierzchołka (numer indeksu najwyższego przodka osiągalnego w jednym kroku od potomka wierzchołka), który używa do określenia, kiedy zestaw wierzchołków powinien zostać usunięty ze stosu do nowego komponentu.
  • Silny algorytm komponent ścieżki oparte wykorzystuje głębokość pierwszego wyszukiwania, jak algorytm Tarjan, ale z dwóch stosów. Jeden ze stosów jest używany do śledzenia wierzchołków, które nie zostały jeszcze przypisane do komponentów, podczas gdy drugi śledzi bieżącą ścieżkę w drzewie wyszukiwania głębokości. Pierwsza wersja tego algorytmu w czasie liniowym została opublikowana przez Edsgera W. Dijkstra w 1976 roku.

Chociaż algorytm Kosaraju jest koncepcyjnie prosty, algorytm Tarjana i algorytm oparty na ścieżce wymaga tylko jednego wyszukiwania w głąb, a nie dwóch.

Algorytmy oparte na osiągalności

Poprzednie algorytmy czasu liniowego opierały się na wyszukiwaniu w głąb, które jest ogólnie uważane za trudne do zrównoleglenia. Fleischer i in. w 2000 roku zaproponował podejście dziel i zwyciężaj oparte na zapytaniach osiągalności , a takie algorytmy są zwykle nazywane algorytmami SCC opartymi na osiągalności . Ideą tego podejścia jest wybranie losowego wierzchołka obrotu i zastosowanie zapytań o osiągalność do przodu i do tyłu z tego wierzchołka. Te dwa zapytania dzielą zestaw wierzchołków na 4 podzbiory: wierzchołki, do których dotarły oba, albo jedno z wyszukiwań, albo żadne. Można pokazać, że silnie połączony komponent musi być zawarty w jednym z podzbiorów. Podzbiór wierzchołków osiągnięty przez oba wyszukiwania tworzy silnie połączone komponenty, a algorytm następnie powtarza się w pozostałych 3 podzbiorach.

Wykazano, że oczekiwany sekwencyjny czas działania tego algorytmu wynosi O( n  log  n ), współczynnik O(log  n ) większy niż w przypadku algorytmów klasycznych. Paralelizm wynika z tego, że: (1) zapytania o osiągalność mogą być łatwiej zrównoleglone (np. przez przeszukiwanie wszerz (BFS) i mogą być szybkie, jeśli średnica grafu jest mała); oraz (2) niezależność między podzadaniami w procesie dziel i zwyciężaj. Algorytm ten działa dobrze na grafach rzeczywistych, ale nie ma teoretycznej gwarancji równoległości (rozważ, jeśli graf nie ma krawędzi, algorytm wymaga O( n ) poziomów rekurencji).

Belloch i in. w 2016 r. pokazuje, że jeśli zapytania o osiągalność są stosowane w kolejności losowej, granica kosztu O( n  log  n ) nadal obowiązuje. Co więcej, zapytania mogą być następnie grupowane w sposób podwajający prefiksy (tj. zapytania 1, 2, 4, 8) i uruchamiane jednocześnie w jednej rundzie. Całkowity zakres tego algorytmu to log 2 n zapytań o osiągalność, co jest prawdopodobnie optymalnym równoległością, jaką można osiągnąć stosując podejście oparte na osiągalności.

Generowanie losowych silnie połączonych grafów

Peter M. Maurer opisuje algorytm generowania losowych silnie spójnych grafów, oparty na modyfikacji algorytmu silnego wzmacniania spójności , problem dodawania jak najmniejszej liczby krawędzi, aby graf był silnie spójny. W połączeniu z modelami Gilberta lub Erdősa-Rényiego z ponownym etykietowaniem węzłów, algorytm jest w stanie wygenerować dowolny silnie połączony graf na n węzłach, bez ograniczeń co do rodzajów struktur, które można wygenerować.

Aplikacje

Algorytmy znajdowania silnie powiązanych składowych mogą być wykorzystane do rozwiązywania problemów z 2 spełnialnością (układy zmiennych logicznych z ograniczeniami na wartości par zmiennych): jak wykazali Aspvall, Plass i Tarjan (1979) , instancja 2 spełnialności jest niesatysfakcjonowana, jeśli i tylko wtedy, gdy istnieje zmienna v taka, że v i jej uzupełnienie są zawarte w tym samym silnie powiązanym składniku grafu implikacji instancji.

Silnie powiązane komponenty są również używane do obliczania rozkładu Dulmage-Mendelsohna , klasyfikacji krawędzi grafu dwudzielnego , w zależności od tego, czy mogą one być częścią idealnego dopasowania na grafie.

Powiązane wyniki

Wykres skierowany jest silnie powiązany wtedy i tylko wtedy, gdy ma rozkład ucha , podział krawędzi na sekwencję ukierunkowanych ścieżek i cykli w taki sposób, że pierwszy podgraf w sekwencji jest cyklem, a każdy kolejny podgraf jest albo współdzielonym cyklem jeden wierzchołek z poprzednimi podwykresami lub ścieżka współdzieląca dwa punkty końcowe z poprzednimi podwykresami.

Zgodnie z twierdzeniem Robbinsa graf nieskierowany może być zorientowany w taki sposób, że staje się silnie powiązany wtedy i tylko wtedy, gdy jest połączony dwukrawędziowo . Jednym ze sposobów udowodnienia tego wyniku jest znalezienie rozkładu ucha na leżącym poniżej nieskierowanym wykresie, a następnie konsekwentne zorientowanie każdego ucha.

Zobacz też

Bibliografia

Linki zewnętrzne