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

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

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

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

Нехай задано множину вершин {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- колеса — це графові матроїди колеса 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.