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

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

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

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

Определения [ править ]

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

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

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

Гамильтоново разложение является ребром разложения графа в гамильтоновые цепи.

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

Примеры [ править ]

Вышеупомянутое как двумерный планарный граф
  • полный граф с более чем двумя вершинами гамильтонова
  • каждый граф цикла является гамильтоновым
  • в каждом турнире есть нечетное количество гамильтоновых путей ( Rédei 1934)
  • каждое платоновое тело , рассматриваемое как граф, является гамильтоновым [5]
  • граф Кэли конечной группы Кокстера гамильтонова (Для получения дополнительной информации о гамильтоновых путей в графах Кэли, см гипотезу Lovász .)

Свойства [ править ]

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

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

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

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

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

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

Теорема Бонди – Хватала [ править ]

Лучшая вершина степени характеристика гамильтоновых графов была представлена в 1972 году Бонди - Chvátal теоремы, обобщающей более ранние результаты, Г. А. Дирак (1952) и Øystein руды . Обе теоремы Дирака и Оре также могут быть выведены из теоремы Поза (1962). Гамильтоничность широко изучалась по отношению к различным параметрам, таким как плотность графа , прочность , запрещенные подграфы и расстояние среди других параметров. [8] Теоремы Дирака и Оре в основном утверждают, что граф является гамильтоновым, если у него достаточно ребер .

Бонди-Chvátal теорема действует на закрывающем клы ( G ) граф G с п вершинами, полученным путем многократного добавления нового краем иу , соединяющим несмежной пару вершин U и V с deg ; ( v ) + deg ; ( U ) ≥ н пока больше не будет найдено пар с этим свойством.

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

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

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

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

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

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

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

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

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

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

Теорема (Уитни, 1931)
Четырехсвязная планарная триангуляция имеет гамильтонов цикл.
Теорема (Тутте, 1956).
Четырехсвязный планарный граф имеет гамильтонов цикл.

Многочлен гамильтонова цикла [ править ]

Алгебраическое представление гамильтоновых циклов данного взвешенного орграфа (чьи дуги имеют веса из определенного основного поля) - это многочлен гамильтонова цикла его взвешенной матрицы смежности, определяемой как сумма произведений весов дуг гамильтоновых циклов орграфа . Этот многочлен не является тождественным нулем как функция от весов дуг тогда и только тогда, когда орграф гамильтонов. Связь между вычислительными сложностями вычисления этого и вычисления перманента была показана в Kogan (1996) .

См. Также [ править ]

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

Заметки [ править ]

  1. ^ Биггс, NL (1981), "TP Киркман, математик", Бюллетень Лондонского математического общества , 13 (2): 97-120, DOI : 10,1112 / БЛМ / 13.2.97 , MR  0608093.
  2. ↑ Уоткинс, Джон Дж. (2004), «Глава 2: Рыцарские туры», Across the Board: The Mathematics of Chessboard Problems , Princeton University Press, стр. 25–38, ISBN 978-0-691-15498-5.
  3. ^ де Руйтер, Йохан (2017). Лабиринты Гамильтона - Руководство для новичков .
  4. ^ Фридман, Эрих (2009). «Гамильтоновы лабиринты» . Дворец головоломок Эриха . Архивировано 16 апреля 2016 года . Проверено 27 мая 2017 года .
  5. ^ Гарднер, М. «Математические игры: о замечательном сходстве между икосианской игрой и башнями Ханоя». Sci. Амер. 196, 150–156, май 1957 г.
  6. ^ Эрик Вайнштейн. «Двусвязный граф» . Wolfram MathWorld.
  7. ^ Balakrishnan, R .; Ранганатан К. (2012), «Следствие 6.5.5», Учебник теории графов , Springer, стр. 134, ISBN 9781461445296.
  8. ↑ Гулд, Рональд Дж. (8 июля 2002 г.). «Успехи в гамильтоновой проблеме - обзор» (PDF) . Университет Эмори . Проверено 10 декабря 2012 .
  9. ^ Рахман, MS; Кайкобад, М. (апрель 2005 г.). «О гамильтоновых циклах и гамильтоновых путях». Письма об обработке информации . 94 : 37–41. DOI : 10.1016 / j.ipl.2004.12.002 .
  10. ^ Moon, J .; Moser, Л. (1963), "О гамильтоновых графов двудольных", Израиль Журнал математики , 1 (3): 163-165, DOI : 10.1007 / BF02759704 , МР 0161332 

Ссылки [ править ]

  • Берже, Клод ; Гуила-Хоуири, А. (1962), Программирование, игры и транспортные сети , Нью-Йорк: Sons, Inc.
  • ДеЛеон, Мелисса (2000), «Исследование достаточных условий для гамильтоновых циклов» (PDF) , Rose-Hulman Undergraduate Math Journal , 1 (1), заархивировано из оригинала (PDF) 22 декабря 2012 г. , извлечено в 2005 г. 11–28.
  • Дирак, Г. А. (1952), "Некоторые теоремы о абстрактных графов", Труды Лондонского математического общества , третий Ser,. 2 : 69-81, DOI : 10,1112 / ПНИЛ / s3-2.1.69 , MR  0047308.
  • Гамильтон, Уильям Роуэн (1856 г.), «Меморандум о новой системе корней единства», Philosophical Magazine , 12 : 446.
  • Гамильтон, Уильям Роуэн (1858 г.), «Счет икозианского исчисления», Труды Королевской ирландской академии , 6 : 415–416.
  • Мейниэль, М. (1973), «Неудовлетворительное условие существования схемы Hamiltonien dans un graphe orienté», Журнал комбинаторной теории , серия B, 14 (2): 137–147, DOI : 10.1016 / 0095-8956 (73) 90057-9 , MR  0317997.
  • Руда, Øystein (1960), "Замечание о контурах Гамильтон", Американский Математический Месячный , 67 (1): 55, DOI : 10,2307 / 2308928 , JSTOR  2308928 , MR  0118683.
  • Pósa, L. (1962), "Теорема о линиях Гамильтона", Magyar Tud. Акад. Мат. Kutató Int. Közl. , 7 : 225–226, MR  0184876.
  • Уитни, Хесслер (1931), "Одна теорема о графов", Анналы математики , второй серии 32 (2): 378-390, DOI : 10,2307 / 1968197 , JSTOR  1968197 , МР  1503003.
  • Тутте, WT (1956), "Теорема о плоских графах", Trans. Амер. Математика. Soc. , 82 : 99-116, DOI : 10,1090 / s0002-9947-1956-0081471-8.
  • Коган, Григорий (1996), «Вычислительный перманент над полями характеристикой 3: где и почему становится трудно», тридцать седьмым ежегодный симпозиум по Основе информатики (РПДА '96) : 108-114, да : 10.1109 / SFCS.1996.548469 , ISBN 0-8186-7594-2

Внешние ссылки [ править ]

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