График колеса
| График колеса | |
|---|---|
 Несколько примеров колесных графов | |
| Вершины | п ≥ 4 |
| Края | 2( п - 1) |
| Диаметр | 2, если n > 4 1, если n = 4 |
| Обхват | 3 |
| Хроматическое число | 4, если n четное 3, если n нечетное |
| Спектр | |
| Характеристики | гамильтониан Самодвойственный Планарный |
| Обозначения | W н |
| Таблица графиков и параметров | |
В математической дисциплине теории графов граф -колесо — это граф, образованный соединением одной универсальной вершины со всеми вершинами цикла . Колесо графа с n можно определить как 1- скелет пирамиды ( n – 1 )-угольной вершинами также . Некоторые авторы [1] напишите W n для обозначения графа-колеса с n вершинами ( n ≥ 4 ); другие авторы [2] вместо этого используйте W n для обозначения графа-колеса с n + 1 вершиной ( n ≥ 3 ), который формируется путем соединения одной вершины со всеми вершинами цикла длины n . В оставшейся части статьи используются прежние обозначения.
Конструктор-конструктор
[ редактировать ]Учитывая набор вершин {1, 2, 3, …, v}, набор ребер колесного графа может быть представлен в обозначениях построителя множеств как {{1, 2}, {1, 3}, …, {1 , v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}}. [3]
Характеристики
[ редактировать ]Колесные графы являются плоскими графами и имеют уникальное планарное вложение. Точнее, каждый граф-колесо является графом Халина . Они самодуальны: планарный двойственный граф любого колесного графа является изоморфным графом . Каждый максимальный планарный граф, кроме K 4 = W 4 , содержит в качестве подграфа либо W 5 , либо W 6 .
В графе колеса всегда существует гамильтонов цикл и существуют циклов в W n (последовательность A002061 в OEIS ).
Для нечетных значений n . W n представляет собой идеальный граф с хроматическим числом 3: вершинам цикла можно присвоить два цвета, а центральной вершине — третий цвет Для четного W n n имеет хроматическое число 4 и (когда n ≥ 6) не является идеальным. W 7 — единственный граф-колесо, представляющий собой граф единичных расстояний на евклидовой плоскости. [4]
Хроматический многочлен колесного графа W n равен:
В теории матроидов два особенно важных специальных класса матроидов — это матроиды колес и матроиды вихрей , оба производные от колесных графов. Матроид k -колеса — это графический матроид колеса W k+1 , тогда как матроид k -вихря получается из k -колеса путем рассмотрения внешнего цикла колеса, а также всех его остовных деревьев как независимый.
Колесо W6 W6 послужило контрпримером к гипотезе Пола Эрдеша о теории Рамсея : он предположил, что полный граф имеет наименьшее число Рамсея среди всех графов с одинаковым хроматическим числом, но Фаудри и Маккей (1993) показали, что число имеет Рамсея. номер 17, тогда как полный граф с тем же хроматическим числом K 4 имеет число Рамсея 18. [5] То есть для каждого 17-вершинного графа G , либо G либо его дополнение содержат W 6 в качестве подграфа, в то время как ни 17-вершинный граф Пэли , ни его дополнение не содержат копию K 4 .
Ссылки
[ редактировать ]- ^ Вайсштейн, Эрик В. «Колесо графика» . Математический мир .
- ^ Розен, Кеннет Х. (2011). Дискретная математика и ее приложения (7-е изд.). МакГроу-Хилл. п. 655 . ISBN 978-0073383095 .
- ^ Трюдо, Ричард Дж. (1993). Введение в теорию графов (Исправленное, расширенное издание. Под ред.). Нью-Йорк: Паб Dover. п. 56. ИСБН 978-0-486-67870-2 . Проверено 8 августа 2012 г.
- ^ Бакли, Фред; Харари, Фрэнк (1988), «О евклидовом измерении колеса», Graphs and Combinatorics , 4 (1): 23–30, doi : 10.1007/BF01864150 , S2CID 44596093 .
- ^ Фаудри, Ральф Дж .; Маккей, Брендан Д. (1993), «Гипотеза Эрдёша и число Рамсея r ( W 6 )» , J. Combinatorial Math. и комбинаторные вычисления. , 13 : 23–31 .