Русская Википедия:Колесо (теория графов)

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

В теории графов колесом W_n называется граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла. Числовое обозначение колёс в литературе не устоялось — некоторые авторы используют n для обозначения длины цикла, так что их W_n означает граф W_n+1 по определению выше. Колесо может быть определено также, как Шаблон:Не переведено 3 (n-1)-угольной пирамиды.

Представление в виде множества

Пусть задано множество вершин {1,2,3,…,v}. Множество рёбер графа-колеса можно представить в виде множества {{1,2},{1,3},…,{1,v},{2,3},{3,4},…,{v-1,v},{v,2}}.

Свойства

Колеса являются планарными графами, а потому имеют единственное вложение в плоскость. Любое колесо является графом Халина. Они самодвойственны — двойственный граф любого колеса изоморфен самому колесу. Любой максимальный планарный граф, отличный от K₄ = W₄, содержит в качестве подграфа либо W₅, либо W₆.

В колесе всегда имеется гамильтонов цикл и число циклов в W_n равно <math>n^2-3n+3</math> (Шаблон:OEIS).

Файл:CyclesW4.svg 7 циклов в колесе W4.

Для нечётных значений n W_n является совершенным графом с хроматическим числом 3 — вершины цикла можно выкрасить в два цвета, а центральная вершина будет иметь третий цвет. Для чётного n W_n колесо имеет хроматическое число 4 и (при n ≥ 6) не будет совершенным графом. W₇ — это единственное колесо, являющееся графом единичных расстояний на евклидовой плоскости.

Хроматический многочлен колеса W_n равен:

<math>P_{W_n}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).</math>

В теории матроидов есть два особо важных вида матроидов — колеса и вихри, и оба вида являются производными от графов-колес. Матроид k-колёса — это Шаблон:Не переведено 3 колеса W_k+1, а матроид k-вихря получается из матроида k-колеса путём объявления внешнего цикла (обода) таким же независимым множеством, как и его остовные деревья.

Колесо W₆ даёт контрпример гипотезе Пола Эрдёша в теории Рамсея — он высказал предположение, что полный граф имеет наименьшее число Рамсея среди всех графов с тем же хроматическим числом. Однако Фаудри и МакКей (Faudree, McKay, 1993) показали, что для W₆ число Рамсея равно 17, в то время как для полного графа K₄, с тем же хроматическим числом, число Рамсея равно 18. Таким образом, для любого графа G с 17 вершинами либо сам G, либо его дополнение содержит W₆ как подграф, в то время как ни граф Пэли, имеющий 17 вершин, ни его дополнение не содержат K₄.