Ścieżka – ścieżką łączącą z o długości n nazywa się ciąg wierzchołków taki, że dla każdego istnieje krawędź z do (w przypadku grafu nieskierowanego możemy mówić, że 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 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
Przypisy
Linki zewnętrzne [dostęp 2026-01-17]. [dostęp 2026-01-17]. [dostęp 2026-01-17].
Kategoria:Teoria grafów