Osiągalność (teoria grafów) – relacja dwuargumentowa między wierzchołkami danego grafu skierowanego. Niech G = (V, E) oznacza graf skierowany, gdzie V jest skończonym zbiorem wierzchołków, a E jest skończonym zbiorem krawędzi, czyli uporządkowanych par wierzchołków tego grafu. Wtedy 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 Ο(log2(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

Przypisy

Bibliografia

Kategoria:Teoria grafów Kategoria:Dwuczłonowe relacje matematyczne