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

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

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

В математической области теории графов гамильтонов путь (или трассируемый путь ) — это путь в неориентированном или ориентированном графе, который посещает каждую вершину ровно один раз. Гамильтонов цикл (или гамильтонов контур ) — это цикл , который посещает каждую вершину ровно один раз. Гамильтонов путь, который начинается и заканчивается в соседних вершинах, может быть завершен путем добавления еще одного ребра для формирования гамильтонова цикла, а удаление любого ребра из гамильтонова цикла дает гамильтонов путь. Вычислительные задачи определения того, существуют ли такие пути и циклы в графах, являются 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) \geq n$ до тех пор, пока не будет найдено больше пар с этим свойством.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

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

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

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

[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.