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