Граф Хершеля

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

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


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

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

Граф Хершеля планарен — его можно нарисовать на плоскости без пересечения рёбер. Он также вершинно 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. 1 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. Архивировано 14 декабря 2021 года.
  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.