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

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

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

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

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

Определения

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

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

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

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

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

Примеры

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

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

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

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

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

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

Число различных гамильтоновых циклов в полном неориентированном графе с $n$ вершинами равно $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ ( 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\geq 3$ ) является гамильтоновым, если для каждой пары несмежных вершин сумма их степеней равна $n$ или больше.

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

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

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

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

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

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

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

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

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

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

Полином гамильтонового цикла

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

См. также

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

Примечания

^ Биггс, Н.Л. (1981), «Т. П. Киркман, математик», Бюллетень Лондонского математического общества , 13 (2): 97–120, doi : 10.1112/blms/13.2.97 , MR 0608093 .
^ Уоткинс, Джон Дж. (2004), «Глава 2: Путешествия рыцаря», Через доску: математика задач на шахматной доске , Princeton University Press, стр. 25–38, ISBN 978-0-691-15498-5 .
^ де Рюитер, Йохан (2017). Лабиринты Гамильтона – Руководство для начинающих .
^ Фридман, Эрих (2009). «Гамильтоновы лабиринты» . Дворец головоломок Эриха . Архивировано из оригинала 16 апреля 2016 года . Проверено 27 мая 2017 г.
^ Гарднер, М. «Математические игры: о поразительном сходстве между Икосианской игрой и ханойскими башнями». наук. амер. 196, 150–156, май 1957 г.
^ Гадерпур, Э.; Моррис, Д.В. (2014). «Графы Кэли на нильпотентных группах с циклическим коммутантом гамильтоновы». Ars Mathematica Contemporanea . 7 (1): 55–72. arXiv : 1111.6216 . дои : 10.26493/1855-3974.280.8d3 . S2CID 57575227 .
^ Лукас, Джоан М. (1987), «Граф вращения бинарных деревьев является гамильтоновым», Journal of Algorithms , 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
^ Эрик Вайнштейн. «Двусвязный граф» . Вольфрам Математический мир.
^ Балакришнан, Р.; Ранганатан, К. (2012), «Следствие 6.5.5», Учебник по теории графов , Springer, стр. 134, ISBN 9781461445296 .
^ Гулд, Рональд Дж. (8 июля 2002 г.). «Достижения по гамильтоновой проблеме – обзор» (PDF) . Университет Эмори. Архивировано из оригинала (PDF) 13 июля 2018 г. Проверено 10 декабря 2012 г.
^ Рахман, М.С.; Кайкобад, М. (апрель 2005 г.). «О гамильтоновых циклах и гамильтоновых путях». Письма об обработке информации . 94 : 37–41. дои : 10.1016/j.ipl.2004.12.002 .
^ Мун, Дж.; Мозер, Л. (1963), «О гамильтоновых двудольных графах», Израильский журнал математики , 1 (3): 163–165, doi : 10.1007/BF02759704 , MR 0161332 , S2CID 119358798
^ Уитни, Хасслер (1931), «Теорема о графах», Annals of Mathematics , Second Series, 32 (2): 378–390, doi : 10.2307/1968197 , JSTOR 1968197 , MR 1503003
^ Тутте, WT (1956), «Теорема о плоских графах», Trans. амер. Математика. Соц. , 82 : 99–116, doi : 10.1090/s0002-9947-1956-0081471-8
^ Коган, Григорий (1996). «Вычисление перманентов по полям характеристики 3: где и почему это становится трудным». Материалы 37-й конференции по основам информатики . стр. 108–114. дои : 10.1109/SFCS.1996.548469 . ISBN 0-8186-7594-2 . S2CID 39024286 .

Ссылки

Берже, Клод ; Гуила-Уири, А. (1962), Программирование, игры и транспортные сети , Нью-Йорк: Sons, Inc.
ДеЛеон, Мелисса (2000), «Исследование достаточных условий для гамильтоновых циклов» (PDF) , студенческий математический журнал Роуз-Халман , 1 (1), заархивировано из оригинала (PDF) 22 декабря 2012 г. , получено в 2005 г. 11-28 .
Дирак, Джорджия (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, doi : 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. Есть. Мэтт. Исследования Int. , 7 : 225–226, МР 0184876 .

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

[1] Биггс, Н.Л. (1981), «Т. П. Киркман, математик», Бюллетень Лондонского математического общества , 13 (2): 97–120, doi : 10.1112/blms/13.2.97 , MR 0608093 .

[2] Уоткинс, Джон Дж. (2004), «Глава 2: Путешествия рыцаря», Через доску: математика задач на шахматной доске , Princeton University Press, стр. 25–38, ISBN 978-0-691-15498-5 .

[3] де Рюитер, Йохан (2017). Лабиринты Гамильтона – Руководство для начинающих .

[4] Фридман, Эрих (2009). «Гамильтоновы лабиринты» . Дворец головоломок Эриха . Архивировано из оригинала 16 апреля 2016 года . Проверено 27 мая 2017 г.

[5] Гарднер, М. «Математические игры: о поразительном сходстве между Икосианской игрой и ханойскими башнями». наук. амер. 196, 150–156, май 1957 г.

[6] Гадерпур, Э.; Моррис, Д.В. (2014). «Графы Кэли на нильпотентных группах с циклическим коммутантом гамильтоновы». Ars Mathematica Contemporanea . 7 (1): 55–72. arXiv : 1111.6216 . дои : 10.26493/1855-3974.280.8d3 . S2CID 57575227 .

[7] Лукас, Джоан М. (1987), «Граф вращения бинарных деревьев является гамильтоновым», Journal of Algorithms , 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] Эрик Вайнштейн. «Двусвязный граф» . Вольфрам Математический мир.

[10] Балакришнан, Р.; Ранганатан, К. (2012), «Следствие 6.5.5», Учебник по теории графов , Springer, стр. 134, ISBN 9781461445296 .

[11] Гулд, Рональд Дж. (8 июля 2002 г.). «Достижения по гамильтоновой проблеме – обзор» (PDF) . Университет Эмори. Архивировано из оригинала (PDF) 13 июля 2018 г. Проверено 10 декабря 2012 г.

[12] Рахман, М.С.; Кайкобад, М. (апрель 2005 г.). «О гамильтоновых циклах и гамильтоновых путях». Письма об обработке информации . 94 : 37–41. дои : 10.1016/j.ipl.2004.12.002 .

[13] Мун, Дж.; Мозер, Л. (1963), «О гамильтоновых двудольных графах», Израильский журнал математики , 1 (3): 163–165, doi : 10.1007/BF02759704 , MR 0161332 , S2CID 119358798

[14] Уитни, Хасслер (1931), «Теорема о графах», Annals of Mathematics , Second Series, 32 (2): 378–390, doi : 10.2307/1968197 , JSTOR 1968197 , MR 1503003

[15] Тутте, WT (1956), «Теорема о плоских графах», Trans. амер. Математика. Соц. , 82 : 99–116, doi : 10.1090/s0002-9947-1956-0081471-8

[16] Коган, Григорий (1996). «Вычисление перманентов по полям характеристики 3: где и почему это становится трудным». Материалы 37-й конференции по основам информатики . стр. 108–114. дои : 10.1109/SFCS.1996.548469 . ISBN 0-8186-7594-2 . S2CID 39024286 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]