Loading AI tools
Z Wikipedii, wolnej encyklopedii
Ś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ą)[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 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.