В теории графов , разделе математики , граф Гершеля — двудольный неориентированный граф с 11 вершинами и 18 рёбрами. Это полиэдральный граф (граф выпуклого многогранника ) и наименьший полиэдральный граф, не имеющий гамильтонова цикла — цикла, проходящего через все его вершины. Он назван в честь британского астронома Александра Стюарта Гершеля из-за исследований Гершеля гамильтоновых циклов в полиэдральных графах (но не этого графа).
Граф Гершеля имеет три вершины степени четыре (три синие вершины, выровненные вертикально в центре иллюстрации) и восемь вершин степени три. Каждые две различные вершины степени четыре имеют двух общих соседей степени три, образуя цикл из четырех вершин с этими общими соседями. Существует три таких цикла, проходящих через шесть из восьми вершин степени три (красные на иллюстрации). Еще две вершины степени три (синие) не участвуют в этих циклах из четырех вершин; вместо этого каждая из них смежна с тремя из шести красных вершин. [1]
Граф Гершеля является многогранным графом ; это означает, что он является планарным графом , который можно нарисовать на плоскости так, чтобы ни одно из его ребер не пересекалось, и что он имеет 3 вершинно-связный граф: удаление любых двух его вершин оставляет связный подграф . [1] Это двудольный граф : когда он раскрашен пятью синими и шестью красными вершинами, как показано на рисунке, каждое ребро имеет одну красную конечную точку и одну синюю конечную точку. [2]
Он имеет двугранную симметрию порядка 6 , для всего 12 членов его группы автоморфизмов . Вершины степени четыре могут быть переставлены произвольно, давая шесть перестановок, и, кроме того, для каждой перестановки вершин степени четыре существует симметрия, которая сохраняет эти вершины неподвижными и обменивает пары вершин степени три. [1]
По теореме Штейница , каждый планарный и 3-вершинно-связный граф имеет выпуклый многогранник с графом в качестве его скелета . [3] Поскольку граф Гершеля обладает этими свойствами, [1] его можно представить таким образом выпуклым многогранником, девятигранник, имеющий многогранник, имеет девять четырехугольников в качестве своих граней. [4] Это можно выбрать так, чтобы каждый автоморфизм графа соответствовал симметрии многогранника, в этом случае три грани будут ромбами или квадратами, а остальные шесть будут воздушными змеями . [1]
Двойственный многогранник — это выпрямленная треугольная призма , которая может быть образована как выпуклая оболочка середин ребер треугольной призмы . При построении таким образом он имеет три квадратных грани на тех же плоскостях, что и квадратные грани призмы, две равносторонние треугольные грани на плоскостях треугольных концов призмы и еще шесть равнобедренных треугольных граней. Этот многогранник обладает тем свойством, что его грани не могут быть пронумерованы таким образом, чтобы последовательные числа появлялись на соседних гранях, и таким образом, чтобы первое и последнее числа также находились на соседних гранях, потому что такая нумерация обязательно соответствовала бы гамильтонову циклу в графе Гершеля. Многогранные нумерации граней такого типа используются в качестве «счетчиков жизней спиндауна» в игре Magic: The Gathering для отслеживания жизней игроков путем поворота многогранника на соседнюю грань всякий раз, когда теряется жизнь. Карта в игре, Лич, позволяет игрокам вернуться из почти потерянного состояния с одной жизнью к их начальному числу жизней. Поскольку двойной многогранник для графа Гершеля не может быть пронумерован таким образом, чтобы этот шаг соединял смежные грани, Константинидес и Константинидес (2018) называют каноническую реализацию этого двойного многогранника «возмездием Лича». [5]
Как двудольный граф с нечетным числом вершин, граф Гершеля не содержит гамильтонова цикла (цикла ребер, проходящего через каждую вершину ровно один раз). Ведь в любом двудольном графе любой цикл должен чередоваться между вершинами по обе стороны от двудольного графа, и, следовательно, должен содержать равное количество вершин обоих типов и иметь четную длину. Таким образом, цикл, проходящий один раз через каждую из одиннадцати вершин, не может существовать в графе Гершеля. Граф называется гамильтоновым, если он содержит гамильтонов цикл, поэтому граф Гершеля не является гамильтоновым. Он имеет наименьшее число вершин, наименьшее число ребер и наименьшее число граней среди всех негамильтоновых полиэдральных графов. [6] Существуют и другие полиэдральные графы с 11 вершинами и без гамильтоновых циклов (в частности, граф Голднера–Харари ) [7], но ни один из них не имеет меньшего числа ребер. [6]
Все вершины графа Гершеля, кроме трех, имеют степень три. Граф называется кубическим или 3-регулярным , если все его вершины имеют степень три. PG Tait предположил [8] , что полиэдральный 3-регулярный граф должен быть гамильтоновым; это было опровергнуто, когда WT Tutte предоставил контрпример, граф Tutte , который намного больше графа Гершеля. [9] Уточнение гипотезы Tait, гипотеза Barnette о том, что каждый двудольный 3-регулярный полиэдральный граф является гамильтоновым, остается открытым. [10]
Каждый максимальный планарный граф , не имеющий гамильтонова цикла, имеет граф Гершеля в качестве минора . Предполагается, что граф Гершеля является одним из трех минорно-минимальных негамильтоновых 3-вершинно-связных графов. Два других — это полный двудольный граф и граф, образованный путем разбиения графа Гершеля и на две симметричные половины трехвершинными сепараторами и последующего объединения одной половины из каждого графа. [11]
Граф Гершеля также представляет собой пример полиэдрального графа, для которого медиальный граф не имеет гамильтонова разложения на два непересекающихся по ребрам гамильтоновых цикла. Медиальный граф графа Гершеля является 4- регулярным графом с 18 вершинами, по одной на каждое ребро графа Гершеля; две вершины являются смежными в медиальном графе, когда соответствующие ребра графа Гершеля являются последовательными на одной из его граней. [12] Он является 4-вершинно-связанным и, по сути, 6-рёберно-связанным . Здесь граф является -вершинно-связанным или -рёберно-связанным, если удаление менее вершин или ребер (соответственно) не может сделать его несвязным. Плоские графы не могут быть 6-рёберно-связанными, потому что они всегда имеют вершину степени не более пяти, а удаление соседних ребер свяжет граф. Терминология «по существу 6-ребристо-связанный» означает, что этот тривиальный способ разъединения графа игнорируется, и невозможно разъединить граф на два подграфа, каждый из которых имеет по крайней мере две вершины, удалив пять или меньше ребер. [13]
Граф Гершеля назван в честь Александра Стюарта Гершеля , британского астронома, который написал раннюю статью об икосиановой игре Уильяма Роуэна Гамильтона . Это головоломка, включающая нахождение гамильтоновых циклов на многограннике, обычно правильном додекаэдре . Граф Гершеля описывает наименьший выпуклый многогранник , который может быть использован вместо додекаэдра, чтобы получить игру, не имеющую решения. Статья Гершеля описывала решения для икосиановой игры только на графах правильного тетраэдра и правильного икосаэдра ; она не описывала граф Гершеля. [14] Название «граф Гершеля» впервые появляется в учебнике по теории графов Джона Адриана Бонди и USR Murty , опубликованном в 1976 году. [15] Сам граф был описан ранее, например, HSM Coxeter . [4]
