В математической области теории графов , А путь графа или линейный граф представляет собой график , чьи вершины могут быть перечислены в следующем порядке : V 1 , V 2 , ..., v п такие , что ребра являются { v я , v я + 1 } , где i = 1, 2,…, n - 1. Эквивалентно, путь по крайней мере с двумя вершинами является связным и имеет две конечные вершины (вершины со степенью 1), в то время как все остальные (если есть) имеют степень 2.
График пути | |
---|---|
Вершины | п |
Края | п - 1 |
Радиус | ⌊ n / 2⌋ |
Диаметр | п - 1 |
Автоморфизмы | 2 |
Хроматическое число | 2 |
Хроматический индекс | 2 |
Спектр | {2 cos ( k π / ( n + 1)); k = 1, ..., n } |
Характеристики | Единичное расстояние Двудольный граф Дерево |
Обозначение | |
Таблица графиков и параметров |
Пути часто важны в своей роли как подграфы других графов, и в этом случае они называются путями в этом графе. Путь - это особенно простой пример дерева , и на самом деле пути - это именно те деревья, в которых ни одна вершина не имеет степени 3 или более. Объединение непересекающихся путей называется линейным лесом .
Пути - это фундаментальные понятия теории графов, описанные во вводных разделах большинства текстов по теории графов. См., Например, Bondy and Murty (1976), Gibbons (1985) или Diestel (2005).
Как диаграммы Дынкина
В алгебре графы путей выглядят как диаграммы Дынкина типа A. Таким образом, они классифицируют корневую систему типа A и группу Вейля типа A, которая является симметрической группой .
Смотрите также
Рекомендации
- Бонди, JA ; Мурти, USR (1976). Теория графов с приложениями . Северная Голландия. С. 12–21 . ISBN 0-444-19451-7.
- Дистель, Рейнхард (2005). Теория графов (3-е изд.). Тексты для выпускников по математике , т. 173, Springer-Verlag. С. 6–9. ISBN 3-540-26182-6.