Колесо (теорія графів): відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
|||
Рядок 34:
== Властивості ==
Колеса є [[ Планарний граф | планарними графами ]], а тому мають єдине вкладення в площину. Будь-яке колесо є {{не перекладено|Граф Халіна|графом Халіна||Halin graph}}. Вони двоїстні — [[ двоїстий граф ]] будь-якого колеса ізоморфне самому колесу. Будь-який максимальний планарний граф, відмінний від '''K'''<sub>4 </sub> = '''W'''<sub>4</sub> подграфа або '''W'''<sub>5</sub>, або '''W'''<sub>6</sub>.
У колесі завжди є [[Гамільтонів граф|гамільтонів цикл]] і кількість циклів '''W'''<sub>'''n'''</sub> дорівнює <math>n^2-3n+3</math> ({{OEIS|id=A002061}}).
Рядок 55:
[[Хроматичне число|Хроматичний многочлен]] колеса '''W<sub>n</sub>''' дорівнює:
<center><math>P_{W_n}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).</math></center>.
У теорії [[Матроїд|матроїдов]] є два особливо важливих виду матроідов — '''колеса''' і '''вихор''', і обидва види є похідними від графів-коліс. Матроїд '''k'''- колеса — це {{не перекладено | Графовий матроїд | графові матроїди ||graphic
Колесо ''W''<sub>6</sub> дає приклад гіпотезі [[Ердеш Пал|Пол Эрдеша]] у {{не перекладено|Теорія Рамсея|теорії Рамсея||Ramsey theory}} — він висловив припущення, що повний граф має найменше число Рамсея серед всіх графів з тим же хроматичним числом. Однак Фаудри і МакКей (Faudree, McKay, 1993) показали, що для ''W''<sub>6</sub> число Рамсея дорівнює 17, в той час як для повного графа ''K''<sub>4</sub>, з тим же хроматичним числом, число Рамсея дорівнює 18.
<ref>{{стаття
| |||