Ustal, czy wykres jest częściowo połączony czy nie

Question

Graf skierowany G = (V, E) ma być częściowo połączony, jeśli dla wszystkich par wierzchołków u, v w V mamy u -> v lub v -> Ścieżka. Podaj skuteczny algorytm do ustalenia, czy pół-G jest podłączony

Answer 1

Trivial O(V^3) rozwiązaniem mogłoby być wykorzystanie floyd warshal wszystkim do wszystkich najkrótsza droga, ale to overkill (pod względem czasu złożoności).

Można to zrobić w O(V+E).

Zastrzeżenie:

DAG jest częściowo połączony topologicznej rodzaju dla każdego i nie istnieje krawędź (vi,vi+1)

Dowód:

względu DAG z topologicznej sortowania v1,v2,...,vn:

Jeśli nie ma krawędzi (vi,vi+1) dla niektóre i, to nie ma też ścieżki (vi+1,vi) (ponieważ jest to topologiczny rodzaj DAG), a wykres nie jest częściowo połączony.

Jeżeli dla każdej i istnieje krawędź (vi,vi+1), to dla każdej i,j (ivi- > VI + 1 > ...- > vj-1- > vj, a wykres jest częściowo połączone.

z tego możemy uzyskać algorytm.

1. Znajdź Maksymalne SCC na wykresie
2. Budowanie SCC graf G „= (U, E”) w taki sposób, U jest zbiorem SCC E'= {(V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E)
3. Czy sortowanie topologiczne na G '
4. Sprawdź, czy dla każdego i istnieje krawędź Vi, Vi + 1.

Poprawność Dowód:

Jeżeli wykres jest pół podłączone do pary (v1,v2), tak że istnieje ścieżka v1->...->v2 - Niech V1, V2 być ich SCC. Istnieje ścieżka od V1 do V2, a więc również od v1 do v2, ponieważ wszystkie węzły w V1 i V2 są silnie połączone.

Jeśli algorytm ustąpił prawdy, to dla dwóch podanych węzłów v1, v2 - są w SCC V1 i V2. Istnieje ścieżka od V1 do V2 (bez utraty ogólności), a więc również od v1 do v2.

---

marginesie również co pół połączony wykres ma pierwiastek (Vertex r który prowadzi do wszystkich wierzchołków)

Dowód:
Zakłada się, że nie jest głównym. Zdefiniuj #(v) = |{u | there is a path from v to u}| (liczba węzłów, które mają ścieżkę od v do nich).
Wybierz a taki, że #(a) = max{#(v) | for all v}.
a nie jest katalogiem głównym, więc istnieje jakiś węzeł u, który nie ma ścieżki od a do niego. Ponieważ wykres jest częściowo połączony, oznacza to, że istnieje ścieżka u->...->a. Ale to oznacza #(u) >= #(a) + 1 (wszystkie węzły są dostępne od a, a także u).
Sprzeczność z maksymą #(a), a więc istnieje root.

Answer 2

Solitain Amita opisał całkowicie najbardziej efektywne podejście. Mogę tylko dodać, że można zastąpić krok 4, sprawdzając, czy istnieje więcej niż jedna kolejność topologiczna G '. Jeśli tak, to wykres nie jest częściowo połączony. W przeciwnym razie wykres jest częściowo połączony. Można to łatwo włączyć do Kahn's algorithm w celu znalezienia kolejności topologicznej wykresu.

Kolejne mniej wydajne rozwiązanie działające w systemie kwadratowym jest następujące.

Najpierw skonstruuj inny wykres G *, który jest odwrotnością oryginalnego wykresu. Następnie dla każdego wierzchołka v G, uruchamiasz DFS z vw G i traktujesz zestaw osiągalnych węzłów jako R_v. Jeśli R_v! = V (G), uruchom inny DFS z v w G * i niech zbiór dostępnych węzłów to R _v. Jeśli związek R_v i R _v nie jest V (G), wówczas wykres nie jest częściowo połączony.