В математической области теории графов граф путей (или линейный граф ) — это граф , вершины которого могут быть перечислены в порядке v 1 , v 2 , …, v n так, что ребра имеют вид { v i , v i +1 } где я знак равно 1, 2, …, n - 1 . Эквивалентно, путь как минимум с двумя вершинами является связным и имеет две конечные вершины (вершины, имеющие степень 1), в то время как все остальные (если таковые имеются) имеют степень 2.
Пути часто играют важную роль в качестве подграфов других графов, и в этом случае они называются путями в этом графе. Путь — это особенно простой пример дерева , и на самом деле пути — это именно те деревья, в которых ни одна вершина не имеет степени 3 или более. Непересекающееся объединение путей называется линейным лесом .
Пути — это фундаментальные понятия теории графов, описанные во вводных разделах большинства текстов по теории графов. См., например, Бонди и Мерти (1976), Гиббонс (1985) или Дистель (2005).
В алгебре графы путей появляются как диаграммы Дынкина типа A. Таким образом, они классифицируют корневую систему типа A и группу Вейля типа A, которая является симметричной группой .