Граф пути

Эта статья о семействе графов. Чтобы узнать о путях как частях произвольных графов, см. «Путь (теория графов)» .

Не путать с линейным графиком .

Граф пути
Граф путей на 6 вершинах
Вершины	н
Края	п - 1
Радиус	⌊ n / 2⌋
Диаметр	п - 1
Автоморфизмы	2
Хроматическое число	2
Хроматический индекс	2
Спектр	$\{2\cos \left({\frac {k\pi }{n+1}}\right);$$k=1,\cdots ,n\}$
Характеристики	Расстояние единицы Двудольный граф Дерево
Обозначения	П н
Таблица графиков и параметров

В математической области теории графов граф путей (или линейный граф ) — это граф которого , вершины могут быть перечислены в порядке v ₁ , v ₂ , …, v _n так, что ребра имеют вид { v _i , v _{i +1} } где я знак равно 1, 2, …, n - 1 . Эквивалентно, путь как минимум с двумя вершинами является связным и имеет две конечные вершины (вершины, имеющие степень 1), в то время как все остальные (если таковые имеются) имеют степень 2.

Пути часто играют важную роль в качестве подграфов других графов, и в этом случае они называются путями в этом графе. Путь — это особенно простой пример дерева , и на самом деле пути — это именно те деревья, в которых ни одна вершина не имеет степени 3 или более. путей Непересекающееся объединение называется линейным лесом .

Пути — это фундаментальные понятия теории графов, описанные во вводных разделах большинства текстов по теории графов. См., например, Бонди и Мерти (1976), Гиббонс (1985) или Дистель (2005).

Как

В алгебре графы путей появляются как диаграммы Дынкина типа A. Таким образом, они классифицируют корневую систему типа A и группу Вейля типа A, которая является симметричной группой .

См. также

• Путь (теория графов)
• Гусеница дерево
• Полный график
• Нулевой график
• Декомпозиция пути
• Цикл (теория графов)

Ссылки

• Бонди, JA ; Мурти, USR (1976). Теория графов с приложениями . Северная Голландия. стр. 12–21 . ISBN  0-444-19451-7 .
• Дистель, Рейнхард (2005). Теория графов (3-е изд.). Тексты для аспирантов по математике , вып. 173, Шпрингер-Верлаг. стр. 6–9. ISBN  3-540-26182-6 .

Внешние ссылки

• Вайсштейн, Эрик В. «Граф пути» . Математический мир .