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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Приклади графів-коліс
Декілька прикладів графів
Вершинn
Ребер2(n − 1)
Діаметр2 коли n>4
1 коли n=4
Обхват3
Хроматичне число3 при n є непарним
4 коли n є парним
Спектр
Властивостігамільтонів
двоїстий
планарний
ПозначенняWn

У теорії графів колесом 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).

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

Для непарних значень 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.

Примітки

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