Граф Хершеля

В теории графов граф Хершеля — это двудольный неориентированный граф с 11 вершинами и 18 рёбрами, наименьший негамильтонов полиэдральный граф. Граф назван по имени британского астронома А. С. Хершеля, написавшего раннюю работу по поводу игры «Икосиан» Уильяма Роуэна Гамильтона — граф Хершеля даёт наименьший выпуклый многогранник, для которого игра не имеет решения. Однако статья Хершеля описывает решения для игры «Икосиан» только для тетраэдра и икосаэдра, и не описывает граф Хершеля[1].

Граф Хершеля
Назван в честь А. С. Хершель
Вершин 11
Рёбер 18
Радиус 3
Диаметр 4
Обхват 4
Автоморфизмы 12 (D6)
Хроматическое число 2
Хроматический индекс 4
Свойства

полиэдральный
планарный
двудольный


совершенный
 Медиафайлы на Викискладе

Свойства

Граф Хершеля планарен — его можно нарисовать на плоскости без пересечения рёбер. Он также вершинно 3-связен — удаление любых двух вершин оставляет подграф связным. Поэтому, по теореме Штайница граф Голднера — Харари является полиэдральным графом — существует выпуклый многогранник (эннеаэдр), имеющий граф Хершеля в качестве своего скелета[2]. Граф Хершеля является также двудольным — его вершины можно разбить на два подмножества из пяти и шести вершин так, что каждое ребро имеет конечные вершины в обоих множествах (красные и синие подмножества на рисунке).

Как и любой другой двудольный граф, граф Хершеля является совершенным — хроматическое число любого порождённого подграфа равно размеру наибольшей клики этого подграфа. Граф имеет хроматический индекс 4, обхват 4, радиус 3 и диаметр 4.

Гамильтоновость

Поскольку граф является двудольным и имеет нечётное число вершин, он не содержит гамильтонов цикл (цикл из рёбер, который проходит через каждую вершину в точности один раз). В любом двудольном графе любой цикл должен попеременно проходить оба множества вершин, а потому, должен содержать равное число вершин обоих типов и иметь чётную длину. Таким образом, цикл, проходящий через каждую из одиннадцати вершин, существовать не может. Граф является минимальным негамильтоновым полиэдральным графом, как бы ни измерялся размер графа — по числу вершин, рёбер или граней[3]. Существует другой полиэдральный граф с 11 вершинами, не имеющий гамильтоновых циклов (а именно, граф Голднера — Харари[4]), но нет графа с меньшим (либо равным) числом рёбер[2].

Все вершины графа Хершеля, за исключением трёх, имеют степень три. Гипотеза Тейта[5] утверждает, что полиэдральный граф, в котором любая вершина имеет степень три должен быть гамильтоновым, но она опровергнута контрпримером, который привёл Татт, много большим графом Татта[6]. Обновление гипотезы Татта, гипотеза Барнетте, что любой двудольный 3-регулярный полиэдральный граф является гамильтоновым, остаётся открытой[7].

Граф Хершеля даёт также пример полиэдрального графа, для которого срединный граф не может быть разбит на два непересекающихся по рёбрам гамильтонова цикла. Серединным графом графа Хершеля является 4-регулярный граф с 18 вершинами, по одной для каждого ребра графа Хершеля. Две вершины смежны в срединном графе, если соответствующие рёбра графа Хершеля идут последовательно на одной из его граней[8].

Алгебраические свойства

Граф Хершеля не вершинно-транзитивен и его полная группа автоморфизмов изоморфна диэдрической группе 12 порядка, группе симметрий правильного шестиугольника, включающей как вращения, так и отражения. Любую перестановку его вершин четвёртой степени можно представить автоморфизмом графа, и существует ещё нетривиальный автоморфизм, переставляющий оставшиеся вершины, не затрагивая вершины четвёртой степени.

Характеристический многочлен графа Хершеля равен .

Примечания

  1. A. S. Herschel. Sir Wm. Hamilton's Icosian Game // The Quarterly Journal of Pure and Applied Mathematics. — 1862. Т. 5. С. 305.
  2. H. S. M. Coxeter. Regular Polytopes. — Dover, 1973. — С. 8.
  3. David Barnette, Ernest Jucovič. Hamiltonian circuits on 3-polytopes // Journal of Combinatorial Theory. — 1970. Т. 9, вып. 1. С. 54—59. doi:10.1016/S0021-9800(70)80054-0.
  4. Weisstein, Eric W. Goldner-Harary Graph (англ.) на сайте Wolfram MathWorld.
  5. P. G. Tait. Listing's Topologie // Philosophical Magazine (5th ser.). — 1884. Т. 17. С. 30—46.. Перепечатано в Scientific Papers, Vol. II, стр. 85—98.
  6. W. T. Tutte. On Hamiltonian circuits // Journal of the London Mathematical Society. — 1946. Т. 21, вып. 2. С. 98—101. doi:10.1112/jlms/s1-21.2.98.
  7. Robert Samal. Barnette's conjecture. — the Open Problem Garden, 11 June 2007.
  8. J. A. Bondy, R. Häggkvist. Edge-disjoint Hamilton cycles in 4-regular planar graphs // Aequationes Mathematicae. — 1981. Т. 22, вып. 1. С. 42—45. doi:10.1007/BF02190157.

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.