Гамильтонов путь

Путь в графе, который посещает каждую вершину ровно один раз

Гамильтонов цикл вокруг сети из шести вершин

Примеры гамильтоновых циклов на квадратной сетке графа 8x8

В математической области теории графов гамильтонов путь (или трассируемый путь ) — это путь в неориентированном или ориентированном графе, который посещает каждую вершину ровно один раз. Гамильтонов цикл (или гамильтонов контур ) — это цикл , который посещает каждую вершину ровно один раз. Гамильтонов путь, который начинается и заканчивается в соседних вершинах, может быть завершен путем добавления еще одного ребра для формирования гамильтонова цикла, а удаление любого ребра из гамильтонова цикла дает гамильтонов путь. Вычислительные задачи определения того, существуют ли такие пути и циклы в графах, являются NP-полными ; подробности см. в задаче о гамильтоновом пути .

Гамильтоновы пути и циклы названы в честь Уильяма Роуэна Гамильтона , который изобрел икосиановую игру , теперь также известную как головоломка Гамильтона , которая заключается в поиске гамильтонова цикла в графе ребер додекаэдра . Гамильтон решил эту задачу, используя икосиановое исчисление , алгебраическую структуру, основанную на корнях из единицы, имеющую много общего с кватернионами (также изобретенными Гамильтоном). Это решение не обобщается на произвольные графы.

Несмотря на то, что они были названы в честь Гамильтона, гамильтоновы циклы в многогранниках также изучались годом ранее Томасом Киркманом , который, в частности, привел пример многогранника без гамильтоновых циклов. ^[1] Еще раньше гамильтоновы циклы и пути в конном графе шахматной доски , конный тур , изучались в 9 веке в индийской математике Рудратой , и примерно в то же время в исламской математике аль -Адли ар-Руми . В Европе 18 века конные туры были опубликованы Авраамом де Муавром и Леонардом Эйлером . ^[2]

Определения

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

Гамильтонов цикл , гамильтонов контур , вершинный тур или цикл графа — это цикл , который посещает каждую вершину ровно один раз. Граф, содержащий гамильтонов цикл, называется гамильтоновым графом .

Аналогичные понятия можно определить для направленных графов , где каждое ребро (дугу) пути или цикла можно проследить только в одном направлении (т. е. вершины соединены стрелками, а ребра прослеживаются «от хвоста к голове»).

Гамильтоново разложение — это рёберное разложение графа на гамильтоновы контуры.

Лабиринт Гамильтона — это тип логической головоломки, цель которой — найти уникальный гамильтонов цикл в заданном графе. ^{[3] [4]}

Примеры

Ортографические проекции и диаграммы Шлегеля с гамильтоновыми циклами вершин пяти платоновых тел – только октаэдр имеет эйлеров путь или цикл, расширяя свой путь с помощью пунктирного пути

• в
• т
• е

• Полный граф с более чем двумя вершинами является гамильтоновым.
• Каждый циклический граф является гамильтоновым
• Каждый турнир имеет нечетное число гамильтоновых путей ( Rédei 1934)
• Каждое платоново тело , рассматриваемое как граф, является гамильтоновым ^[5]
• Граф Кэли конечной группы Коксетера является гамильтоновым (для получения дополнительной информации о гамильтоновых путях в графах Кэли см. гипотезу Ловаса ).
• Графы Кэли на нильпотентных группах с циклическим коммутатором являются гамильтоновыми. ^[6]
• Граф переворота выпуклого многоугольника или, что то же самое, граф вращения бинарных деревьев является гамильтоновым. ^{[7] [8]}

Характеристики

Граф Гершеля — наименьший возможный полиэдральный граф , не имеющий гамильтонова цикла. Показан возможный гамильтонов путь.

Любой гамильтонов цикл можно преобразовать в гамильтонов путь, удалив одно из его ребер, но гамильтонов путь можно расширить до гамильтонова цикла, только если его конечные точки смежны.

Все гамильтоновы графы являются двусвязными , но двусвязный граф не обязательно является гамильтоновым (см., например, граф Петерсена ). ^[9]

Эйлеров граф G ( связный граф, в котором каждая вершина имеет четную степень) обязательно имеет эйлеров цикл, замкнутый маршрут, проходящий через каждое ребро G ровно один раз. Этот цикл соответствует гамильтонову циклу в линейном графе L ( G ) , поэтому линейный граф каждого эйлерова графа является гамильтоновым. Линейные графы могут иметь другие гамильтоновы циклы, которые не соответствуют эйлеровым циклам, и, в частности, линейный граф L ( G ) каждого гамильтонова графа G сам является гамильтоновым, независимо от того, является ли граф G эйлеровым. ^[10]

Турнир (с более чем двумя вершинами) является гамильтоновым тогда и только тогда, когда он сильно связан .

Число различных гамильтоновых циклов в полном неориентированном графе на n вершинах равно ⁠( н – 1)!/2⁠ а в полном ориентированном графе на n вершинах равно ( n – 1)! . Эти подсчеты предполагают, что циклы, которые одинаковы за исключением своей начальной точки, не учитываются отдельно.

Теорема Бонди–Хватала

Лучшая характеристика степени вершин гамильтоновых графов была предоставлена ​​в 1972 году теоремой Бонди – Хватала , которая обобщает более ранние результаты Г. А. Дирака (1952) и Ойстейна Оре . Обе теоремы Дирака и Оре также могут быть выведены из теоремы Посы (1962). Гамильтоновость широко изучалась в отношении различных параметров, таких как плотность графа , прочность , запрещенные подграфы и расстояние среди других параметров. ^[11] Теоремы Дирака и Оре в основном утверждают, что граф является гамильтоновым, если он имеет достаточно ребер .

Теорема Бонди–Хватала применима к замыканию cl( G ) графа G с n вершинами, полученному путем многократного добавления нового ребра uv, соединяющего несмежную пару вершин u и v с deg( v ) + deg( u ) ≥ n до тех пор, пока не будет найдено больше пар с этим свойством.

Теорема Бонди–Хватала (1976)  —  Граф является гамильтоновым тогда и только тогда, когда его замыкание гамильтоново.

Поскольку полные графы являются гамильтоновыми, все графы, замыкание которых является полным, являются гамильтоновыми, что является содержанием следующих более ранних теорем Дирака и Оре.

Теорема Дирака (1952)  —  Простой граф с n вершинами ( ) является гамильтоновым, если каждая вершина имеет степень или выше. ${\displaystyle n\geq 3}$ ${\displaystyle {\tfrac {n}{2}}}$

Теорема Оре (1960)  —  Простой граф с n вершинами () является гамильтоновым, если для каждой пары несмежных вершин сумма их степеней равна n или больше. ${\displaystyle n\geq 3}$

Следующие теоремы можно рассматривать как направленные версии:

Гуила–Хуири (1960)  —  Сильно связный простой ориентированный граф с n вершинами является гамильтоновым, если каждая вершина имеет полную степень, большую или равную n .

Мейниел (1973)  —  Сильно связный простой ориентированный граф с n вершинами является гамильтоновым, если сумма полных степеней каждой пары различных несмежных вершин больше или равна ${\displaystyle 2n-1}$

Число вершин необходимо удвоить, поскольку каждое неориентированное ребро соответствует двум направленным дугам, и, таким образом, степень вершины в ориентированном графе в два раза превышает степень в неориентированном графе.

Рахман– Кайкобад (2005)  —  Простой граф с n вершинами имеет гамильтонов путь, если для каждой пары несмежных вершин сумма их степеней и длина их кратчайшего пути больше n . ^[12]

Приведенная выше теорема может распознать только существование гамильтонова пути в графе, но не гамильтонова цикла.

Многие из этих результатов имеют аналоги для сбалансированных двудольных графов , в которых степени вершин сравниваются с числом вершин на одной стороне двудольного графа, а не с числом вершин во всем графе. ^[13]

Существование гамильтоновых циклов в планарных графах

Теорема  —  4-связная плоская триангуляция имеет гамильтонов цикл. ^[14]

Теорема  —  4-связный планарный граф имеет гамильтонов цикл. ^[15]

Гамильтонов циклический полином

Алгебраическое представление гамильтоновых циклов заданного взвешенного орграфа (дугам которого назначены веса из некоторого основного поля) — это полином гамильтонового цикла его взвешенной матрицы смежности, определяемой как сумма произведений весов дуг гамильтоновых циклов орграфа. Этот полином не является тождественно нулем как функция весов дуг тогда и только тогда, когда орграф является гамильтоновым. Связь между вычислительной сложностью его вычисления и вычислением перманента была показана Григорием Коганом. ^[16]

Смотрите также

• Гипотеза Барнетта , открытая проблема гамильтоновости кубических двудольных полиэдральных графов
• Эйлеров путь — путь через все ребра графа.
• Теорема Флейшнера о гамильтоновых квадратах графов
• Код Грея
• Теорема Гринберга, дающая необходимое условие для того, чтобы планарные графы имели гамильтонова цикла
• Задача о гамильтоновых путях , вычислительная задача нахождения гамильтоновых путей
• Гипогамильтонов граф — негамильтонов граф, в котором каждый подграф с удаленной вершиной является гамильтоновым.
• Конный обход , гамильтонов цикл в конном графе
• Обозначение LCF для гамильтоновых кубических графов .
• Гипотеза Ловаса о том, что вершинно-транзитивные графы являются гамильтоновыми
• Панциклический граф , графы с циклами любой длины, включая гамильтонов цикл
• Пансвязность , усиление как панцикличности, так и гамильтоновой связности
• Семь мостов Кёнигсберга
• Показатель краткости , численная мера того, насколько далеки от гамильтоновых могут быть графы в семействе.
• Змея в коробке , самый длинный индуцированный путь в гиперкубе
• Алгоритм Штейнхауза–Джонсона–Троттера для нахождения гамильтонова пути в пермутоэдре
• Субгамильтонов граф , подграф планарного гамильтонова графа
• Гипотеза Тейта (теперь известная как ложная) о том, что 3-регулярные полиэдральные графы являются гамильтоновыми
• Задача коммивояжера

Примечания

1. Биггс, Н. Л. (1981), «TP Kirkman, математик», Бюллетень Лондонского математического общества , 13 (2): 97–120, doi :10.1112/blms/13.2.97, MR  0608093.
2. Уоткинс, Джон Дж. (2004), «Глава 2: Ход конем», Across the Board: Математика шахматных задач , Princeton University Press, стр. 25–38, ISBN 978-0-691-15498-5.
3. де Рюитер, Йохан (2017). Лабиринты Гамильтона – Руководство для начинающих .
4. Фридман, Эрих (2009). «Гамильтоновы лабиринты». Erich's Puzzle Palace . Архивировано из оригинала 16 апреля 2016 года . Получено 27 мая 2017 года .
5. Гарднер, М. «Математические игры: о замечательном сходстве между икосианской игрой и ханойскими башнями». Sci. Amer. 196, 150–156, май 1957 г.
6. Ghaderpour, E.; Morris, DW (2014). «Графы Кэли на нильпотентных группах с циклическим коммутатором являются гамильтоновыми». Ars Mathematica Contemporanea . 7 (1): 55–72. arXiv : 1111.6216 . doi :10.26493/1855-3974.280.8d3. S2CID  57575227.
7. Лукас, Джоан М. (1987), «Граф вращения бинарных деревьев является гамильтоновым», Журнал алгоритмов , 8 (4): 503–535, doi :10.1016/0196-6774(87)90048-4
8. Уртадо, Ферран ; Ной, Марк (1999), «Граф триангуляций выпуклого многоугольника и дерево триангуляций», Computational Geometry , 13 (3): 179–188, doi : 10.1016/S0925-7721(99)00016-4
9. Эрик Вайнштейн. «Двусвязный граф». Wolfram MathWorld.
10. Балакришнан, Р.; Ранганатан, К. (2012), «Следствие 6.5.5», Учебник теории графов, Springer, стр. 134, ISBN 9781461445296.
11. Gould, Ronald J. (8 июля 2002 г.). «Advances on the Hamiltonian Problem – A Survey» (PDF) . Университет Эмори. Архивировано из оригинала (PDF) 2018-07-13 . Получено 2012-12-10 .
12. Рахман, М. С.; Кайкобад, М. (апрель 2005 г.). «О гамильтоновых циклах и гамильтоновых путях». Information Processing Letters . 94 : 37–41. doi :10.1016/j.ipl.2004.12.002.
13. Мун, Дж.; Мозер, Л. (1963), «О гамильтоновых двудольных графах», Israel Journal of Mathematics , 1 (3): 163–165, doi :10.1007/BF02759704, MR  0161332, S2CID  119358798
14. Уитни, Хасслер (1931), «Теорема о графах», Annals of Mathematics , вторая серия, 32 (2): 378–390, doi :10.2307/1968197, JSTOR  1968197, MR  1503003
15. Tutte, WT (1956), «Теорема о планарных графах», Trans. Amer. Math. Soc. , 82 : 99–116, doi : 10.1090/s0002-9947-1956-0081471-8
16. Коган, Григорий (1996). «Вычисление постоянных над полями характеристики 3: где и почему это становится трудным». Труды 37-й конференции по основам информатики . стр. 108–114. doi :10.1109/SFCS.1996.548469. ISBN 0-8186-7594-2. S2CID  39024286.

Ссылки

• Берж, Клод ; Гуила-Хуири, А. (1962), Программирование, игры и транспортные сети , Нью-Йорк: Sons, Inc.
• ДеЛеон, Мелисса (2000), «Исследование достаточных условий для гамильтоновых циклов» (PDF) , Rose-Hulman Undergraduate Math Journal , 1 (1), архивировано из оригинала (PDF) 2012-12-22 , извлечено 2005-11-28.
• Дирак, GA (1952), «Некоторые теоремы об абстрактных графах», Труды Лондонского математического общества , 3-я серия, 2 : 69–81, doi :10.1112/plms/s3-2.1.69, MR  0047308.
• Гамильтон, Уильям Роуэн (1856), «Меморандум относительно новой системы корней единства», Philosophical Magazine , 12 : 446.
• Гамильтон, Уильям Роуэн (1858), «Изложение икосианского исчисления», Труды Королевской Ирландской академии , 6 : 415–416.
• Мейниэль, М. (1973), «Достаточное условие существования контура Гамильтона в графической ориентации», Журнал комбинаторной теории , серия B, 14 (2): 137–147, номер документа : 10.1016/0095-8956 (73)90057-9 , МР  0317997.
• Оре, Эйстейн (1960), «Заметка о схемах Гамильтона», The American Mathematical Monthly , 67 (1): 55, doi :10.2307/2308928, JSTOR  2308928, MR  0118683.
• Поса, Л. (1962), «Теорема о линиях Гамильтона», Magyar Tud. Акад. Мат. Кутато Междунар. Кёзл. , 7 : 225–226, МР  0184876.

Внешние ссылки

• Вайсштейн, Эрик В. «Гамильтонов цикл». Математический мир .
• Цикл Эйлера и циклы Гамильтона