PROFILPELAJAR.COM

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

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

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

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

Свойства

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

В колесе всегда имеется гамильтонов цикл и число циклов в W_n равно $n^{2}-3n+3$ (последовательность A002061 в OEIS).

7 циклов в колесе W₄.

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

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

P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).

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

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

Примечания

↑ Weisstein, Eric W. Wheel Graph (англ.) на сайте Wolfram MathWorld.
↑ Richard J. Trudeau. Introduction to Graph Theory. — Corrected, enlarged republication. — New York: Dover Pub. — С. 56. — ISBN 978-0-486-67870-2. Архивировано 5 мая 2019 года.
↑ Fred Buckley, Frank Harary. On the euclidean dimension of a wheel // Graphs and Combinatorics. — 1988. — Т. 4, вып. 1. — С. 23–30. — doi:10.1007/BF01864150.
↑ Ralph J. Faudree, Brendan D. McKay. A conjecture of Erdős and the Ramsey number r(W₆) // J. Combinatorial Math. and Combinatorial Comput. — 1993. — Т. 13. — С. 23–31.