Колесо (теорія графів): відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Створена сторінка: {{ Граф | name = Приклади графів-коліс | image = 300px | Wight = 350px | vertices = '''n''' | edges = 2('... |
Немає опису редагування |
||
Рядок 16:
У [[Теорія графів|теорії графів]] '''колесом''' '''W'''<sub>'''n'''</sub> називається граф з n вершинами (n ≥ 4), утворений з'єднанням єдиною вершини з усіма вершинами (n -1)- [[Граф-цикл|цикла]].
Числове позначення коліс в літературі не затрималось — деякі автори використовують '''n''' для позначення довжини циклу, так що їх '''W'''<sub>'''n'''</sub> означає граф '''W'''<sub>'''n+1'''</sub> за визначенням вище<ref>{{mathworld | urlname = WheelGraph | title= Wheel Graph}}</ref>. Колесо може бути визначено також, як {{не перекладено|n-скелет|1-скелет||n-skeleton}} (n -1) - вугільної [[Піраміда (геометрія)|піраміди]].
== Уявлення у вигляді множини ==
Нехай задано множину вершин {1,2,3,...,v}. Безліч ребер графа-колеса можна представити у {{не перекладено |Форма запису множини|вигляді множини||set-builder notation}} {{1,2},{1,3},...,{1,v},{2,3},{3,4},...,{v-1,v},{v,2}}<ref>
{{книга
| автор = Richard J. Trudeau
| заголовок = Introduction to теорія Графів
|year=1993
| видавництво = Dover Pub
| місце =New York
| isbn=978-0-486-67870-2
| сторінки =56
| url=http://store.doverpublications.com/0486678709.html
| видання=Corrected, enlarged republication
| accessdate=8 August 2012
}}</ref>.
== Властивості ==
Колеса є [[ Планарний граф | планарними графами ]], а тому мають єдине вкладення в площину. Будь колесо є [[Граф Халіна|графом Халіна]]. Вони самодвойственны — [[ двоїстий граф ]] будь-якого колеса ізоморфне самому колесу. Будь максимальний планарний граф, відмінний від '''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]]
|}
Для непарних значень ''n''' '''W'''<sub>'''n'''</sub> [[Досконалий граф|досконалим графом]] з [[Хроматичне число|хроматичним числом]] 3 — вершини циклу можна пофарбувати у два кольори, а центральна вершина буде мати третій колір. Для парного '''n''' '''W'''<sub>'''n'''</sub> колесо має [[хроматичне число]] 4 і (при n ≥ 6) не буде досконалим графом. '''W'''<sub>7</sub> — це єдине колесо, що є [[Граф одиничних відстаней|графом одиничних відстаней]] на евклідової площини.
<ref>
{{стаття
| автор = Fred Buckley, Frank Harary
| заголовок = On the евклідовому dimension of a wheel
| видання = Graphs and Комбінаторики
| том = 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>.
| |||
