Колесо (теорія графів)
У теорії графів колесом Wn називається граф з n вершинами (n ≥ 4), утворений з'єднанням єдиної вершини з усіма іншими вершинами, які утворюють (n-1)-цикл. Існує неоднозначність при позначенні колеса в літературі — деякі автори використовують Wn, а деякі Wn+1[1]. Колесо може бути визначено також, як 1-скелет (n-1)-кутної піраміди. Уявлення у вигляді множиниНехай задано множину вершин {1,2,3,…,v}. Множину ребер графу-колеса можна представити у вигляді множини {{1,2},{1,3},...,{1,v},{2,3},{3,4},...,{v-1,v},{v,2}}[2]. ВластивостіКолеса є планарними графами, а тому мають єдине вкладення в площину. Будь-яке колесо є графом Халіна. Вони двоїстні — двоїстий граф будь-якого колеса ізоморфне самому колесу. Будь-який максимальний планарний граф, відмінний від K4 = W4 підграфу або W5, або W6. У колесі завжди є гамільтонів цикл і кількість циклів Wn дорівнює (послідовність A002061 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).
Для непарних значень n,Wn є досконалим графом хроматичним числом 3 — вершини циклу можна пофарбувати у два кольори, а центральна вершина буде мати третій колір. Для парного n,Wn колесо має хроматичне число 4 і (при n ≥ 6) не буде досконалим графом. W7 — це єдине колесо, що є графом одиничних відстаней на евклідовій площини. [3]. Хроматичний многочлен колеса Wn дорівнює: . У теорії матроїдів є два особливо важливих види матроїдів — колеса і вихор, і обидва види є похідними від графів-коліс. Матроїд k- колеса — це графові матроїди [en]колеса Wk+1, a матроїд k -вихору виходить з матроїда k-колеса шляхом оголошення зовнішнього циклу (обода) такою ж незалежною множиною, як і її кістякове дерево. Колесо W6 є прикладом у гіпотезі Пол Ердеша(теорії Рамсея) — він висловив припущення, що повний граф має найменше число Рамсея серед всіх графів з тим же хроматичним числом. Однак Фаудри і МакКей (Faudree, McKay, 1993) показали, що для W6 число Рамсея дорівнює 17, в той час як для повного графу K4, з тим же хроматичним числом, число Рамсея дорівнює 18. [4]. Таким чином, для будь-якого графу G з 17 вершинами або сам G, або його доповнення містить W6 як підграф, в той час як граф Пелі, має 17 вершин, ні його доповнення не містять «K»4. Примітки
|