Ścieżka (teoria grafów)

Ścieżka – ś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 – ś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ą ważnym elementem teorii grafów oraz wielu algorytmów.

Zobacz też

• osiągalność (teoria grafów)
• droga (teoria grafów)
• cykl (teoria grafów)
• graf skierowany
• graf prosty