График пути - Path graph
| График пути | |
|---|---|
 Граф путей на 6 вершинах
| |
| Вершины | п |
| Края | п - 1 |
| Радиус | ⌊ n / 2⌋ |
| Диаметр | п - 1 |
| Автоморфизмы | 2 |
| Хроматическое число | 2 |
| Хроматический индекс | 2 |
| Спектр | {2 cos ( k π / ( n + 1)); k = 1, ..., n } |
| Характеристики |
Единичное расстояние Двудольный граф Дерево |
| Обозначение | |
| Таблица графиков и параметров | |
В математической области теории графов , А путь графа или линейный граф представляет собой график , чьи вершины могут быть перечислены в следующем порядке : V 1 , V 2 , ..., v п такие , что ребра являются { v я , v я + 1 } , где i = 1, 2,…, n - 1. Эквивалентно, путь, по крайней мере, с двумя вершинами, является связным и имеет две конечные вершины (вершины со степенью 1), в то время как все остальные (если есть) имеют степень 2.
Пути часто играют важную роль в качестве подграфов других графов, и в этом случае они называются путями в этом графе. Путь - это особенно простой пример дерева , и на самом деле пути - это именно те деревья, в которых ни одна вершина не имеет степени 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.