Ś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