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

Приклади графів-коліс
Декілька прикладів графів
Вершин	n
Ребер	2(n − 1)
Діаметр	2 коли n>4 1 коли n=4
Обхват	3
Хроматичне число	3 при n є непарним 4 коли n є парним
Спектр	$\{2\cos(2k\pi /(n-1))^{1};$ $k=1,\ldots ,n-2\}$$\cup \{1\pm {\sqrt {n}}\}$
Властивості	гамільтонів двоїстий планарний
Позначення	Wn

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

Уявлення у вигляді множини

Нехай задано множину вершин {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}, a матроїд k -вихору виходить з матроїда k-колеса шляхом оголошення зовнішнього циклу (обода) такою ж незалежною множиною, як і її кістякове дерево.

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