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