Ścieżka (teoria grafów)

Ś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 krawedź 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.

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ą bardzo ważnym elementem teorii grafów oraz wielu algorytmów.

Zobacz też

• droga (teoria grafów)
• cykl (teoria grafów)
• graf skierowany
• graf prosty