Wykres ścieżki

Ten artykuł dotyczy rodziny grafów. Informacje na temat ścieżek jako części dowolnych grafów można znaleźć w artykule Ścieżka (teoria grafów) .
Nie mylić z wykresem liniowym .

W matematycznej dziedzinie teorii grafów graf ścieżkowy (lub graf liniowy ) to graf , którego wierzchołki można wymienić w kolejności v 1 , v 2 , ..., v n tak, że krawędzie są { v i , v i + 1 }, gdzie i = 1, 2, ..., n − 1 . Równoważnie, ścieżka mająca co najmniej dwa wierzchołki jest spójna i ma dwa wierzchołki końcowe (wierzchołki stopnia 1), podczas gdy wszystkie pozostałe (jeśli istnieją) mają stopień 2.

Ścieżki często odgrywają ważną rolę jako podgrafy innych grafów, w takim przypadku nazywane są ścieżkami w tym grafie. Ścieżka jest szczególnie prostym przykładem drzewa , a w rzeczywistości ścieżki to dokładnie drzewa, w których żaden wierzchołek nie ma stopnia 3 lub wyższego. Rozłączna suma ścieżek nazywana jest lasem liniowym .