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

В математической области теории графов , 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. ↑ Watkins, John J. (2004), «Глава 2: Knight's Tours», 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 .
  • Тур Эйлера и циклы Гамильтона