Ścieżka (teoria grafów)

Ścieżka – ścieżką łączącą ${\displaystyle v_{0}}$ z ${\displaystyle v_{n}}$ o długości n nazywa się ciąg wierzchołków ${\displaystyle (v_{0},v_{1},...,v_{n})}$ taki, że dla każdego ${\displaystyle k\in \{0,1,\dots ,n-1\}}$ istnieje krawędź z ${\displaystyle v_{k}}$ do ${\displaystyle v_{k+1}}$ (w przypadku grafu nieskierowanego możemy mówić, że ${\displaystyle v_{k},v_{k+1}}$ sąsiadują z sobą)^[1]. 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 ${\displaystyle 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^[2].

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

Przypisy