Перегляд вихідного коду сторінки Колесо (теорія графів)

{{ Граф 
| name = Приклади графів-коліс
| image = [[Файл:Wheel graphs.svg|300px]]| edges  = 2(''n'' − 1)
| image_caption = Декілька прикладів графів
| girth    = 3
| diameter = 2 коли ''n>4''<br>1 коли ''n''=4
| vertices = ''n''
| edges = 2(''n'' &minus; 1)
| chromatic_number = 3 при ''n'' є непарним<br/>4 коли ''n'' є парним
| spectrum = <math>\{2 \cos(2 k \pi / (n-1))^1; </math><br><math>k = 1, \ldots, n - 2\}</math><math>\cup \{1 \pm \sqrt{n}\}</math>
|properties = [[Гамільтонів граф|гамільтонів]]<br />[[Двоїстий граф|двоїстий]]<br />[[Планарний граф|планарний]]
| notation = ''W''<sub>''n''</sub>
}}
{{Otheruses}}
У [[Теорія графів|теорії графів]] '''колесом''' '''W'''<sub>'''n'''</sub> називається граф з n вершинами (n ≥ 4), утворений з'єднанням єдиної вершини з усіма іншими вершинами, які утворюють (n-1)-[[Циклічний граф|цикл]]. Існує неоднозначність при позначенні колеса в літературі&nbsp;— деякі автори використовують '''W'''<sub>'''n'''</sub>, а деякі '''W'''<sub>'''n+1'''</sub><ref>{{mathworld | urlname = WheelGraph | title= Wheel Graph}}</ref>. Колесо може бути визначено також, як [[N-скелет|1-скелет]] (n-1)-кутної [[Піраміда (геометрія)|піраміди]].

== Уявлення у вигляді множини ==
Нехай задано множину вершин {1,2,3,…,v}. Множину ребер графу-колеса можна представити у [[Нотація побудови множини|вигляді множини]] {{1,2},{1,3},...,{1,v},{2,3},{3,4},...,{v-1,v},{v,2}}<ref>
{{книга
| автор = Richard J. Trudeau
| заголовок = Вступ теорія Графів
|year=1993
| видавництво = Dover Pub
| Wight = 350px
| vertices = '''n'''

| місце =New York
| isbn=978-0-486-67870-2
| сторінки =56
| url=http://store.doverpublications.com/0486678709.html
| видання=Виправив, розширене перевидання
| accessdate=8 August 2012
}}</ref>.

== Властивості ==
Колеса є [[ Планарний граф | планарними графами]], а тому мають єдине вкладення в площину. Будь-яке колесо є [[Граф Халіна|графом Халіна]]. Вони двоїстні&nbsp;— [[ двоїстий граф ]] будь-якого колеса ізоморфне самому колесу. Будь-який максимальний планарний граф, відмінний від '''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}}).
{| class="wikitable"
|[[Файл:CyclesW4.svg|320px]]]]<br/>7 циклів у колесі ''W''<sub>4</sub>.
|}
Для непарних значень ''n'',''W''<sub>''n''</sub> є [[Досконалий граф|досконалим графом]] [[Хроматичне число|хроматичним числом]] 3&nbsp;— вершини циклу можна пофарбувати у два кольори, а центральна вершина буде мати третій колір. Для парного ''n'',''W''<sub>''n''</sub> колесо має [[хроматичне число]] 4 і (при n ≥ 6) не буде досконалим графом. ''W''<sub>7</sub>&nbsp;— це єдине колесо, що є [[Граф одиничних відстаней|графом одиничних відстаней]] на евклідовій площини.
<ref>
{{книга
| автор = Fred Buckley, Frank Harary
| заголовок = На евклідовії розмірності колеса
| видання = Графи та комбінаторики
| том = 4
| випуск = 1
| рік = 1988
| doi = 10.1007/BF01864150
| сторінки = 23-30
}}</ref>.

[[Хроматичне число|Хроматичний многочлен]] колеса '''W<sub>n</sub>''' дорівнює:
<center><math>P_{W_n}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).</math></center>.
У теорії [[Матроїд|матроїдів]] є два особливо важливих види матроїдів&nbsp;— '''колеса''' і '''вихор''', і обидва види є похідними від графів-коліс. Матроїд '''k'''- колеса&nbsp;— це {{не перекладено | Графовий матроїд | графові матроїди ||graphic matroid}}колеса ''W''<sub>''k+1''</sub>, a матроїд '' k ''-вихору виходить з матроїда ''k''-колеса шляхом оголошення зовнішнього циклу (обода) такою ж незалежною множиною, як і її [[Кістякове дерево|кістякове дерево]].

Колесо ''W''<sub>6</sub> є прикладом у гіпотезі [[Ердеш Пал|Пол Ердеша]]([[Теорія Рамсея|теорії Рамсея]])&nbsp;— він висловив припущення, що повний граф має найменше число Рамсея серед всіх графів з тим же хроматичним числом. Однак Фаудри і МакКей (Faudree, McKay, 1993) показали, що для ''W''<sub>6</sub> число Рамсея дорівнює 17, в той час як для повного графу ''K''<sub>4</sub>, з тим же хроматичним числом, число Рамсея дорівнює 18.
<ref>{{книга
| автор = Ralph J. Faudree, Brendan D. McKay
| заголовок = Гіпотеза Ердше і Рамселя числа ''r''(''W''<sub>6</sub>)
| url = http://cs.anu.edu.au/people/Brendan.McKay/papers/wheels.ps.gz
| видання = J. Комбінаторної математики <!-- comment to prevent DOI bot from breaking the journal name again -->
| том = 13
| рік = 1993
| сторінки = 23-31
}}</ref>. Таким чином, для будь-якого графу G з 17 вершинами або сам ''G'', або його доповнення містить W<sub>6</sub> як підграф, в той час як [[граф Пелі]], має 17 вершин, ні його доповнення не містять «K»<sub>4</sub>.

== Примітки ==
{{примітки}}

{{rq|checktranslate}}

[[Категорія:Параметричні сімейства графів]]
[[Категорія:Планарні графи]]