Osiągalność (teoria grafów)

Osiągalność (teoria grafów) – relacja dwuargumentowa określona na zbiorze wierzchołków danego grafu skierowanego G = (V, E), gdzie V jest skończonym zbiorem wierzchołków i E jest skończonym zbiorem krawędzi (które są parami wierzchołków) tego grafu. Relacja osiągalności zachodzi dla pary (x,y) (x,y ∊ V) wtedy i tylko wtedy, gdy istnieje ścieżka w grafie G prowadząca od wierzchołka x do wierzchołka y. Wówczas mówimy, że wierzchołek y jest osiągalny z wierzchołka x w grafie G.

Algorytmy

Z relacją osiągalności wiąże się problem decyzyjny następującej postaci: mając daną trójkę (G, x, y), gdzie G jest grafem skierowanym (G = (V, E)) oraz x i y (x,y ∊ V) są wierzchołkami tego grafu, odpowiedzieć na pytanie, czy w grafie G wierzchołek y jest osiągalny z wierzchołka x. Wiadomo, że ten problem jest w klasie NL (znany jest algorytm o złożoności pamięciowej Ο(log(n)) dla niedeterministycznej maszyny Turinga).

Przynależność do klasy NL

Przyjmujemy na wejściu algorytmu niedeterministycznego dane w postaci (G, x, y). Używamy zmiennej pomocniczej v zainicjowanej wartością x. W każdym kroku korzystając z niedeterminizmu wybieramy kolejny wierzchołek grafu sąsiedni z v, który przypisujemy do v. Jeżeli wybrany wierzchołek v = y to algorytm kończy się i zwraca odpowiedź pozytywną, w przeciwnym razie powtarzany jest krok poprzedni. Formalnie, algorytm powinien zawierać również licznik wykonanych kroków, w przypadku gdy licznik przekroczy całkowitą liczbę wierzchołków grafu G algorytm kończy się z odpowiedzią negatywną .

Algorytmy dla maszyn deterministycznych

Algorytm Floyda-Warshalla lub algorytm Dijkstry może zostać wykorzystany w celu sprawdzenia istnienia ścieżki pomiędzy dowolnymi dwoma wierzchołkami grafu skierowanego. Wymienione algorytmy oprócz odpowiedzi na pytanie czy istnieje ścieżka dają również informacje na temat długości najkrótszej ścieżki co wiąże się z wyższą złożonością obliczeniową i pamięciową.

Przeszukiwanie wszerz lub w głąb pozwala sprawdzić istnienie ścieżki ze złożonością liniową ze względu na liczbę krawędzi.

Możliwe są ogólne algorytmy o złożoności pamięciowej Ο(log²(n)) (twierdzenie Savitcha), a także algorytmy o złożoności pamięciowej Ο(log(n)) działające dla szczególnych przypadków.

Zobacz też

• Ścieżka (teoria grafów)
• Graf skierowany

Bibliografia

• Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, 1994. ISBN 0-201-53082-1.