Колесо (теория графов)

В теории графов колесом W_n называется граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла. Числовое обозначение колёс в литературе не устоялось — некоторые авторы используют n для обозначения длины цикла, так что их W_n означает граф W_n+1 по определению выше. Колесо может быть определено также, как 1-скелет (n-1)-угольной пирамиды.

Примеры графов-колёс
Вершин	n
Рёбер	2(n − 1)
Диаметр	2 при n>4 1 при n=4
Обхват	3
Хроматическое число	3 при нечётном n, 4 при чётном n
Свойства	гамильтонов двойственный планарный
Обозначение	Wn
Медиафайлы на Викискладе

Представление в виде множества

Пусть задано множество вершин {1,2,3,…,v}. Множество рёбер графа-колеса можно представить в виде множества {{1,2},{1,3},…,{1,v},{2,3},{3,4},…,{v-1,v},{v,2}}.

Свойства

Колеса являются планарными графами, а потому имеют единственное вложение в плоскость. Любое колесо является графом Халина. Они самодвойственны — двойственный граф любого колеса изоморфен самому колесу. Любой максимальный планарный граф, отличный от K₄ = W₄, содержит в качестве подграфа либо W₅, либо W₆.

В колесе всегда имеется гамильтонов цикл и число циклов в W_n равно $n^{2}-3n+3$ (последовательность A002061 в OEIS).

7 циклов в колесе W4.

Для нечётных значений n W_n является совершенным графом с хроматическим числом 3 — вершины цикла можно выкрасить в два цвета, а центральная вершина будет иметь третий цвет. Для чётного n W_n колесо имеет хроматическое число 4 и (при n ≥ 6) не будет совершенным графом. W₇ — это единственное колесо, являющееся графом единичных расстояний на евклидовой плоскости.

Хроматический многочлен колеса W_n равен:

$P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).$

В теории матроидов есть два особо важных вида матроидов — колеса и вихри, и оба вида являются производными от графов-колес. Матроид k-колёса — это графовый матроид колеса W_k+1, а матроид k-вихря получается из матроида k-колеса путём объявления внешнего цикла (обода) таким же независимым множеством, как и его остовные деревья.

Колесо W₆ даёт контрпример гипотезе Пола Эрдёша в теории Рамсея — он высказал предположение, что полный граф имеет наименьшее число Рамсея среди всех графов с тем же хроматическим числом. Однако Фаудри и МакКей (Faudree, McKay, 1993) показали, что для W₆ число Рамсея равно 17, в то время как для полного графа K₄, с тем же хроматическим числом, число Рамсея равно 18. Таким образом, для любого графа G с 17 вершинами либо сам G, либо его дополнение содержит W₆ как подграф, в то время как ни граф Пэли, имеющий 17 вершин, ни его дополнение не содержат K₄.