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

У теорії графів колесом W_n називається граф з n вершинами (n ≥ 4), утворений з'єднанням єдиної вершини з усіма іншими вершинами, які утворюють (n-1)-цикл. Існує неоднозначність при позначенні колеса в літературі — деякі автори використовують W_n, а деякі W_n+1. Колесо може бути визначено також, як 1-скелет (n-1)-кутної піраміди.

Приклади графів-коліс
Декілька прикладів графів
(Вершин)	n
(Ребер)	2(n − 1)
(Діаметр)	2 коли n>4 1 коли n=4
(Обхват)	3
Хроматичне число	3 при n є непарним 4 коли n є парним
Спектр	${\displaystyle \{2\cos(2k\pi /(n-1))^{1};}$ ${\displaystyle k=1,\ldots ,n-2\}}$${\displaystyle \cup \{1\pm {\sqrt {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 дорівнює ${\displaystyle n^{2}-3n+3}$ (послідовність A002061 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

]] 7 циклів у колесі W4.

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

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

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

.

У теорії матроїдів є два особливо важливих види матроїдів — колеса і вихор, і обидва види є похідними від графів-коліс. Матроїд k- колеса — це ^[en]колеса W_k+1, a матроїд k -вихору виходить з матроїда k-колеса шляхом оголошення зовнішнього циклу (обода) такою ж незалежною множиною, як і її кістякове дерево.

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

Примітки

1. Weisstein, Eric W. Wheel Graph(англ.) на сайті Wolfram MathWorld.
2. Richard J. Trudeau. Вступ теорія Графів. — Виправив, розширене перевидання. — New York : Dover Pub. — С. 56. — .
3. Fred Buckley, Frank Harary. На евклідовії розмірності колеса. — Графи та комбінаторики. — 1988. — Т. 4. — С. 23-30. — DOI:10.1007/BF01864150.
4. Ralph J. Faudree, Brendan D. McKay. Гіпотеза Ердше і Рамселя числа r(W₆). — J. Комбінаторної математики. — 1993. — Т. 13. — С. 23-31.