Ścieżka (teoria grafów)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Ścieżka - w teorii grafów ścieżką łączącą v_0 z v_n o długości n nazywa się ciąg wierzchołków (v_0, v_1, ... , v_n) taki, że dla każdego k \in [0, 1, \dots, n-1] istnieje krawędź z v_k do v_{k+1} (w przypadku grafu nieskierowanego możemy mówić, że v_k, v_{k+1} sąsiadują z sobą). Często przez ścieżkę rozumiemy również dodatkowo ciąg (czasami zbiór) krawędzi łączących kolejne wierzchołki w ciągu wierzchołków ścieżki. Ciąg tych krawędzi posiada zawsze n wyrazów, stąd określenie "długość", co jest najbardziej widoczne w przypadku szczególnego przypadku ścieżek bez powtarzających się wierzchołków (tzw. dróg).

Ścieżka prosta - to ścieżka w której nie ma powtarzających się wierzchołków[1].

W przypadku grafu (krawędzi) ważonych, należy odróżnić pojęcie długości od odległości (to jest sumy wag krawędzi łączących kolejne wierzchołki w ścieżce - być może liczone wielokrotnie).

Ścieżki są ważnym elementem teorii grafów oraz wielu algorytmów.

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. Thomas H. Cormen: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2001, s. 114. ISBN 83-204-2665-0.