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

Шаблон:Граф Шаблон:Otheruses У теорії графів колесом 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$ (Шаблон: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»₄.