Osiągalność

W teorii grafów osiągalność odnosi się do możliwości przedostania się z jednego wierzchołka do drugiego w obrębie grafu. Wierzchołek $s}$ osiągnąć wierzchołek (i $)$ osiągalny z , jeśli istnieje sekwencja sąsiednich wierzchołków (tj. $spacer$ ) , która jest s ${$ zaczyna się $displaystyle$ i kończy na $t}$ .

W grafie nieskierowanym osiągalność pomiędzy wszystkimi parami wierzchołków można określić poprzez identyfikację połączonych elementów grafu. Dowolna para wierzchołków takiego grafu może stykać się ze sobą wtedy i tylko wtedy, gdy należą do tego samego połączonego elementu; dlatego na takim wykresie osiągalność jest symetryczna ( osiąga $jeśli$$osiąga$$displaystyle s} ,$ t $displaystyle t}$ ) . Połączone elementy grafu nieskierowanego można zidentyfikować w czasie liniowym. Pozostała część tego artykułu skupia się na trudniejszym problemie określania osiągalności parami w a graf skierowany (który, nawiasem mówiąc, nie musi być symetryczny).

Definicja

W przypadku wykresu skierowanego , z zestawem wierzchołków i zestawem krawędzi , $relacja$ osiągalności $G}$$, mi )$ ( V $)$$($ V jest domknięciem przechodnim ${\ displaystyle (s, t)$ czyli zbiorem wszystkich uporządkowanych par $}$ wierzchołków $w którym$${\ displaystyle v_ {0}= s, v_ {1}, v_ {2}, ..., v_ {k} = t}$ ciąg wierzchołków tak, że krawędź ${ \displaystyle (v_{i-1},v_{i})}$ jest dla wszystkich mi $\displaystyle E}$${\ Displaystyle 1 \ równoważnik i \ równoważnik k$ }

Jeśli jest $acykliczny , to$ jego relacja osiągalności jest porządkiem ; w ten sposób można zdefiniować dowolny porządek częściowy, na przykład jako relację osiągalności jego redukcji przechodniej . Godną uwagi konsekwencją tego jest to $s}$$są$ antysymetryczne, jeśli $mogą$ osiągnąć , to wiemy, że nie mogą osiągnąć $displaystyle$ . Intuicyjnie, gdybyśmy mogli podróżować od $do$ t $.$$z$ powrotem do $temu ,$ wówczas zawierałby cykl , jest acykliczny Jeżeli $skierowany,$ ale nie acykliczny (tj. zawiera co najmniej jeden cykl), wówczas jego relacja osiągalności będzie odpowiadać zamówieniu w przedsprzedaży , a nie porządkowi częściowemu.

Algorytmy

Algorytmy określania osiągalności dzielą się na dwie klasy: te, które wymagają przetwarzania wstępnego i te, które tego nie wymagają.

Jeśli masz tylko jedno (lub kilka) zapytań do wykonania, bardziej efektywne może być rezygnacja z używania bardziej złożonych struktur danych i bezpośrednie obliczenie osiągalności żądanej pary. Można to osiągnąć w czasie liniowym przy użyciu algorytmów, takich jak przeszukiwanie wszerz lub iteracyjne przeszukiwanie w pierwszej kolejności w głąb .

Jeśli będziesz zadawać wiele zapytań, możesz zastosować bardziej wyrafinowaną metodę; dokładny wybór metody zależy od charakteru analizowanego wykresu. $zaledwie$ możemy stworzyć strukturę danych, która będzie następnie odpowiadać na zapytania dotyczące osiągalności na dowolnej parze wierzchołków w . Poniżej opisano trzy różne algorytmy i struktury danych dla trzech różnych, coraz bardziej wyspecjalizowanych sytuacji.

Algorytm Floyda-Warshalla

Algorytm Floyda – Warshalla można zastosować do obliczenia domknięcia przechodniego dowolnego skierowanego grafu, co daje podstawę do relacji osiągalności zgodnie z powyższą definicją.

Algorytm wymaga $V | ^ {3})$ i w $displaystyle$ najgorszy przypadek. Algorytm ten nie jest zainteresowany wyłącznie osiągalnością, ponieważ oblicza także najkrótszą odległość ścieżki pomiędzy wszystkimi parami wierzchołków. W przypadku grafów zawierających cykle ujemne najkrótsze ścieżki mogą być niezdefiniowane, ale nadal można zauważyć osiągalność między parami.

Algorytm Thorupa

W przypadku digrafów planarnych dostępna jest znacznie szybsza metoda, opisana przez Mikkela Thorupa w $spędzeniu$ osiągalności na wykresie planarnym w czasie po ${\ Displaystyle O (n \ log {n})}$ czas przetwarzania wstępnego w celu utworzenia struktury danych ${\ Displaystyle O (n \ log {n})}$ rozmiar. Algorytm ten może również dostarczać przybliżone najkrótsze odległości ścieżek, a także informacje o trasie.

${\ displaystyle v$$,$ tak że każda ścieżka z wierzchołka do dowolnego innego wierzchołka musi przechodzić przez co najmniej jedną z nich: v separatory powiązane z $w}$ { $displaystyle$ . Poniżej znajduje się zarys sekcji związanych z osiągalnością.

$pod$$uwagę$ graf , algorytm rozpoczyna się od zorganizowania wierzchołków w warstwy, zaczynając od . Warstwy są budowane naprzemiennie, najpierw biorąc pod uwagę wszystkie wierzchołki osiągalne z poprzedniego kroku (zaczynając od $,$ a następnie wszystkie wierzchołki, które docierają do poprzedniego kroku, aż wszystkie wierzchołki zostaną przypisane do warstwy. . Dzięki konstrukcji warstw każdy wierzchołek pojawia się co najwyżej w dwóch warstwach i na każdej skierowanej ścieżce lub dipath w $1 {\$$L_ {i + 1}$ warstwach i $displaystyle$ } Niech $displaystyle$$utworzoną warstwą$ najniższą wartością , że $}$ .

$_$ jako seria ${\ Displaystyle G_ {i} = r_ {i} \ Puchar L_ {i} \ Puchar L_ {i + 1}} i$ gdzie ${\ displaystyle r_ {i}}$ jest skróceniem wszystkich poprzednich poziomów ${\ displaystyle L_ {0} \ ldots L_ {i-1}}$ w jeden wierzchołek. Ponieważ każda diścieżka pojawia $ja {\ displaystyle G_$ w co najwyżej dwóch kolejnych warstwach i ponieważ każda ${ i$ utworzona przez dwie kolejne warstwy, każda diścieżka pojawia się w całości w co najmniej jednej ${\ displaystyle G_ {i}}$ (i nie więcej niż 2 kolejne takie wykresy)

Dla każdego $co$$wierzchołki$ trzy separatory, które po usunięciu dzielą wykres na trzy składowe, z których każda . Ponieważ $separatorach$ daje łącznie do 6 diścieżek na wszystkich Niech ${\ displaystyle S}$ będzie tym zestawem dipathów. Dowód na to, że takie separatory zawsze można znaleźć, jest powiązany z twierdzeniem Liptona i Tarjana o separatorach planarnych , a separatory te można lokalizować w czasie liniowym.

Dla każdego $charakter$ zapewnia naturalne indeksowanie jego $.$ końca ścieżki Dla każdego wierzchołka $w$$lokalizujemy$ pierwszy wierzchołek w osiągalny dla $}$ wierzchołek w Q $displaystyle Q}$$displaystyle$$v$ , który sięga do ${\ displaystyle v}$ . Oznacza to, że patrzymy na to, jak wcześnie $możemy$$dotrzeć$ do $i$ jak daleko możemy pozostać w nadal wrócić do $\ displaystyle v} }$ . Informacje te są przechowywane $z$ . Następnie dla dowolnej pary wierzchołków $i$ może osiągnąć w $displaystyle$$}$ ${\ displaystyle w}$ przez $\ displaystyle Q}$${$ , jeśli łączy się z ${\ displaystyle Q}$ wcześniej niż ${\ displaystyle w}$ łączy się z ${\ displaystyle Q$ .

$jest oznaczony jak powyżej$ każdego kroku rekurencji, . Ponieważ ta rekurencja $przechowywanych$ łącznie dodatkowych informacji $odpowiedniego$ tego momentu logarytmiczne zapytanie o czas osiągalności jest tak proste, jak przejrzenie każdej pary etykiet pod kątem wspólnego, . Oryginalny artykuł pracuje następnie nad dostrojeniem czasu zapytania do ${\ Displaystyle O (1)}$ .

$razy$ dzieli wierzchołki w taki sposób, że każdy wierzchołek jest rozpatrywany tylko . Faza separatora algorytmu dzieli wykres na elementy, które mają co najwyżej $.$ , co daje logarytmiczną głębokość rekurencji Na każdym poziomie rekurencji wystarczy praca liniowa, aby zidentyfikować separatory i możliwe połączenia między wierzchołkami. Ogólny wynik to $n \ log n)}$$dodatkowymi$ z informacjami przechowywanymi dla każdego wierzchołka.

Algorytm Kamedy

$Odpowiedni dwuznak$ metody Kamedy z $i$ .

Ten sam wykres co powyżej po uruchomieniu algorytmu Kamedy, pokazujący etykiety DFS dla każdego wierzchołka

Jeszcze szybszą metodę wstępnego przetwarzania, zapoczątkowaną przez T. Kamedę w 1975 r., można zastosować, jeśli graf jest planarny , acykliczny i wykazuje również następujące dodatkowe właściwości: wszystkie wierzchołki 0- in Degree i wszystkie 0- stopnie zewnętrzne pojawiają się na tym samym powierzchni (często zakłada się, że jest to ściana zewnętrzna) i możliwe jest podzielenie granicy tej ściany na dwie części w taki sposób, że wszystkie wierzchołki o wartości 0 stopni zewnętrznych pojawiają się na jednej części, a wszystkie wierzchołki o wartości 0 stopni zewnętrznych na drugiej (tzn. dwa typy wierzchołków nie występują naprzemiennie).

Jeśli $właściwości$$n$ możemy wstępnie przetworzyć wykres tylko w $displaystyle O (\ log$ przechowywać tylko $czasie$ odpowiadając na zapytania o osiągalność dla dowolnej pary wierzchołków w za pomocą prostego porównania

Przetwarzanie wstępne obejmuje następujące kroki. Dodajemy nowy wierzchołek $z$$który$ ma krawędź do każdego wierzchołka o stopniu 0 cali i kolejny nowy wierzchołek z każdego wierzchołka o stopniu 0 stopni. Należy zauważyć, że właściwości pozwalają nam to zrobić przy zachowaniu płaskości, to znaczy po tych dodatkach nadal nie będzie żadnych przejść $krawędzi$ Dla każdego wierzchołka przechowujemy listę przylegań (zewnętrznych krawędzi) w kolejności zgodnej z planarnością grafu (na przykład zgodnie z ruchem wskazówek zegara w odniesieniu do osadzania grafu). Następnie inicjujemy licznik ${\ displaystyle i=n+1}$$i$ rozpocznij przemierzanie w głąb . Podczas tego przechodzenia lista sąsiedztwa każdego wierzchołka jest odwiedzana w razie potrzeby od lewej do prawej. $są usuwane ze stosu przejścia, są$$one$ oznaczane wartością a następnie są zmniejszane. Należy pamiętać, że $\$ zawsze oznaczony wartością $displaystyle n+1}$ i $oznaczony$ zawsze $jako$ . Następnie powtarzane jest przechodzenie w głąb, ale tym razem lista sąsiedztwa każdego wierzchołka jest odwiedzana od prawej do lewej.

Po zakończeniu $usuwane$ ich incydentalne krawędzie $są$$Każdy pozostały wierzchołek$$wartościami$ dwuwymiarową etykietę z od . Biorąc pod uwagę dwa wierzchołki $i$ ich etykiety, $\ displaystyle u}$${\ Displaystyle L (u) = (a_ {1}, a_ {2})}$ i ${\ Displaystyle L (v) = (b_ {1}, b_ {2 })}$ , mówimy, że ${\ Displaystyle L (u) <L (v)}$ wtedy i tylko wtedy, gdy ${\ displaystyle a_ {1} \ równoważnik b_ {1 }}$ , i istnieje co najmniej jeden składnik ${\$ który jest ściśle mniejszy niż ${\ displaystyle b_ {1}}$$displaystyle a_ {2} \$$}$ odpowiednio lub ${\ displaystyle b_ {2}} .$

Główny wynik tej metody stwierdza następnie, że jest osiągalny od ${\ displaystyle u}$$wtedy$ i tylko wtedy, gdy $\ displaystyle L (u) <L (v)}$$,$ co można w

Powiązane problemy

Powiązanym problemem jest rozwiązywanie zapytań o osiągalność z pewną liczbą $.$ wierzchołków Na przykład: „Czy wierzchołek $displaystyle s_ {1}, s_ {2}. ..,s_{k}}$$s$ osiągnąć wierzchołek $że$ wierzchołki są zawiodły i nie można ich już używać?” Podobny problem może uwzględniać awarie krawędzi, a nie awarie wierzchołków lub kombinację obu. Technika wyszukiwania wszerz działa równie dobrze w przypadku takich zapytań, ale zbudowanie wydajnej wyroczni jest bardziej wyzywający.

Innym problemem związanym z zapytaniami o osiągalność jest szybkie przeliczanie zmian w relacjach osiągalności w przypadku zmiany jakiejś części wykresu. Na przykład jest to istotny problem w przypadku wyrzucania elementów bezużytecznych , który musi zrównoważyć odzyskiwanie pamięci (aby można było ją ponownie przydzielić) z problemami związanymi z wydajnością działającej aplikacji.

Zobacz też

• Gammoid
• st -łączność