В математической области теории графов , A гамильтон путь (или прослеживаем путь ) представляет собой путь в неориентированном или ориентированном графе , что посещения каждой вершина ровно один раз. Гамильтонов цикл (или гамильтонов цикл ) является гамильтонов путь , который является циклом . Определение того, существуют ли такие пути и циклы в графах, - это проблема гамильтонова пути , которая является NP-полной .
Гамильтоновы пути и циклы названы в честь Уильяма Роуэна Гамильтона, который изобрел икозианскую игру , теперь также известную как головоломка Гамильтона , которая включает в себя поиск гамильтонова цикла в графе ребер додекаэдра . Гамильтон решил эту проблему, используя исчисление икози , алгебраическую структуру, основанную на корнях из единицы, во многом похожую на кватернионы (также изобретенные Гамильтоном). Это решение не распространяется на произвольные графы.
Несмотря на то, что они названы в честь Гамильтона, гамильтоновы циклы в многогранниках годом ранее изучал Томас Киркман , который, в частности, привел пример многогранника без гамильтоновых циклов. [1] Еще раньше, гамильтоновые циклы и пути в графе рыцарской на шахматной доске , в турне рыцаря , были изучены в 9 - м века в индийской математике по Радрату , и примерно в то же время в исламской математике по аль-Адли ар-Рого . В Европе 18 века рыцарские туры были опубликованы Авраамом де Муавром и Леонардом Эйлером . [2]
Определения
Гамильтон путь или прослеживаем путь является путем , который посещение каждой вершины графа ровно один раза. Граф, содержащий гамильтонов путь, называется отслеживаемым графом . Граф является гамильтоновым связным, если для каждой пары вершин существует гамильтонов путь между двумя вершинами.
Гамильтонов цикл , гамильтонов цикл , вершина тур или график цикла является цикл , что каждая вершина посещения ровно один раз. Граф, содержащий гамильтонов цикл, называется гамильтоновым графом .
Аналогичные понятия могут быть определены для ориентированных графов , где каждое ребро (дугу) пути или цикла можно проследить только в одном направлении (т. Е. Вершины соединены стрелками, а ребра прослеживаются «хвост к голове»).
Гамильтоново разложение является ребром разложения графа в гамильтоновые цепи.
Гамильтон лабиринт представляет собой тип логической головоломки , в которой цель состоит в том, чтобы найти уникальный гамильтонов цикл в данном графе. [3] [4]
Примеры
- Полный граф с более чем двумя вершинами гамильтонова
- Каждый граф цикла является гамильтоновым
- В каждом турнире есть нечетное количество гамильтоновых путей ( Rédei 1934).
- Каждое платоновое тело , рассматриваемое как граф, является гамильтоновым [5]
- Граф Кэли конечной группы Кокстера является гамильтоновым (Для получения дополнительной информации о гамильтоновых путях в графах Кэли см. Гипотезу Ловаса .)
Характеристики
Любой гамильтонов цикл можно преобразовать в гамильтонов путь, удалив одно из его ребер, но гамильтонов путь можно продолжить до гамильтонова цикла, только если его концы смежны.
Все гамильтоновы графы двусвязны , но двусвязный граф не обязательно должен быть гамильтоновым (см., Например, граф Петерсена ). [6]
Эйлерова графа G (а связный граф , в котором каждая вершина имеет даже степень) обязательно имеет тур Эйлера, закрытую прогулку , проходящий через каждое ребро G ровно один раз. Этот тур соответствует гамильтоновому циклу в линейном графе L ( G ), поэтому линейный граф каждого эйлерова графа является гамильтоновым. Линейные графы могут иметь другие гамильтоновы циклы, которые не соответствуют эйлеровым турам, и, в частности, линейный граф L ( G ) каждого гамильтонова графа G сам является гамильтоновым, независимо от того, является ли граф G эйлеровым. [7]
Турнир (с более чем двумя вершинами) гамильтонова тогда и только тогда , когда оно сильно связано .
Количество различных гамильтоновых циклов в полном неориентированном графе на n вершинах равноа в полном ориентированном графе на n вершинах -. Эти подсчеты предполагают, что циклы, одинаковые, за исключением их начальной точки, не учитываются отдельно.
Теорема Бонди – Хватала
Лучшая вершина степени характеристика гамильтоновых графов была представлена в 1972 году Бонди - Chvátal теоремы, обобщающей более ранние результаты, Г. А. Дирак (1952) и Øystein руды . Обе теоремы Дирака и Оре также могут быть выведены из теоремы Поза (1962). Гамильтоничность широко изучалась по отношению к различным параметрам, таким как плотность графа , прочность , запрещенные подграфы и расстояние среди других параметров. [8] Теоремы Дирака и Оре в основном утверждают, что граф является гамильтоновым, если у него достаточно ребер .
Бонди-Chvátal теорема действует на закрывающем клы ( G ) граф G с п вершинами, полученным путем многократного добавления нового краем иу , соединяющим несмежной пару вершин U и V с deg ; ( v ) + deg ; ( U ) ≥ н пока больше не будет найдено пар с этим свойством.
- Теорема Бонди – Хватала (1976). Граф является гамильтоновым тогда и только тогда, когда его замыкание гамильтоново.
Поскольку полные графы являются гамильтоновыми, все графы с полным замыканием являются гамильтоновыми, что является содержанием следующих более ранних теорем Дирака и Оре.
- Теорема Дирака (1952). Простой граф с п вершинами ( ) гамильтонова, если каждая вершина имеет степень или выше.
- Теорема Оре (1960). Простой граф с п вершинами ( ) является гамильтоновым, если для каждой пары несмежных вершин сумма их степеней равна n или больше.
Следующие теоремы можно рассматривать как направленные версии:
- Гуила-Хоуири (1960). Сильно соединен простой ориентированный граф с п вершинами гамильтоновы , если каждая вершина имеет полную большую степень , чем или равный п .
- Мейниэль (1973). Сильно соединен простой ориентированный граф с п вершинами гамильтонова , если сумма полных степеней каждой пары различных несмежных вершин больше или равно .
Число вершин необходимо удвоить, потому что каждое неориентированное ребро соответствует двум направленным дугам, и, таким образом, степень вершины в ориентированном графе в два раза больше степени в неориентированном графе.
- Рахман – Кайкобад (2005). Простой граф с п вершинами имеет гамильтонов путь , если для каждого несмежных пар вершин сумма их степеней и их наименьшей длины пути больше , чем п . [9]
Вышеупомянутая теорема может распознавать только существование гамильтонова пути в графе, но не гамильтонова цикла.
Многие из этих результатов имеют аналоги для сбалансированных двудольных графов , в которых степени вершин сравниваются с числом вершин на одной стороне двудольного графа, а не с числом вершин во всем графе. [10]
Существование гамильтоновых циклов в плоских графах
- Теорема (Уитни, 1931)
- Четырехсвязная планарная триангуляция имеет гамильтонов цикл.
- Теорема (Тутте, 1956).
- Четырехсвязный планарный граф имеет гамильтонов цикл.
Полином гамильтонова цикла
Алгебраическое представление гамильтоновых циклов данного взвешенного орграфа (чьи дуги имеют веса из определенного основного поля) - это многочлен гамильтонова цикла его взвешенной матрицы смежности, определяемой как сумма произведений весов дуг гамильтоновых циклов орграфа . Этот многочлен не является тождественным нулем как функция от весов дуг тогда и только тогда, когда орграф гамильтонов. Связь между вычислительными сложностями вычисления этого и вычисления перманента была показана в Kogan (1996) .
Смотрите также
- Гипотеза Барнетта , открытая проблема гамильтоничности кубических двудольных многогранных графов
- Эйлеров путь , путь через все ребра в графе
- Теорема Флейшнера о гамильтоновых квадратах графов
- Код Грея
- Теорема Гринберга, дающая необходимое условие для того, чтобы планарные графы имели гамильтонов цикл
- Гамильтониан проблемы путь , вычислительная задача нахождения гамильтоновых путей
- Гипогамильтонов граф , негамильтонов граф, в котором каждый подграф с удаленными вершинами является гамильтоновым
- Рыцарский тур , гамильтонов цикл в рыцарском графе
- Обозначения LCF для гамильтоновых кубических графов .
- Гипотеза Ловаса о том, что вершинно-транзитивные графы гамильтоновы
- Панциклический граф , графы с циклами любой длины, включая гамильтонов цикл
- Семь мостов Кенигсберга
- Показатель краткости , числовая мера того, насколько далеко от гамильтониана могут быть графы в семье.
- Змея в коробке , самый длинный индуцированный путь в гиперкубе
- Алгоритм Штейнгауза – Джонсона – Троттера для поиска гамильтонова пути в пермутоэдре
- Субгамильтонов граф , подграф плоского гамильтонова графа
- Гипотеза Тэта (теперь известная ложная) о том, что 3-регулярные многогранные графы являются гамильтоновыми
- Проблема коммивояжера
Заметки
- ^ Биггс, NL (1981), "TP Киркман, математик", Бюллетень Лондонского математического общества , 13 (2): 97-120, DOI : 10,1112 / БЛМ / 13.2.97 , MR 0608093.
- ^ Уоткинс, Джон Дж. (2004), «Глава 2: Рыцарские туры», Across the Board: The Mathematics of Chessboard Problems , Princeton University Press, стр. 25–38, ISBN 978-0-691-15498-5.
- ^ де Руйтер, Йохан (2017). Лабиринты Гамильтона - Руководство для новичков .
- ^ Фридман, Эрих (2009). «Гамильтоновы лабиринты» . Дворец головоломок Эриха . Архивировано 16 апреля 2016 года . Проверено 27 мая 2017 года .
- ^ Гарднер, М. «Математические игры: о замечательном сходстве между икосианской игрой и башнями Ханоя». Sci. Амер. 196, 150–156, май 1957 г.
- ^ Эрик Вайнштейн. «Двусвязный граф» . Wolfram MathWorld.
- ^ Балакришнан, Р .; Ранганатан К. (2012), «Следствие 6.5.5», Учебник теории графов , Springer, стр. 134, ISBN 9781461445296.
- ^ Гулд, Рональд Дж. (8 июля 2002 г.). «Успехи в гамильтоновой проблеме - обзор» (PDF) . Университет Эмори . Проверено 10 декабря 2012 .
- ^ Рахман, MS; Кайкобад, М. (апрель 2005 г.). «О гамильтоновых циклах и гамильтоновых путях». Письма об обработке информации . 94 : 37–41. DOI : 10.1016 / j.ipl.2004.12.002 .
- ^ 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 .
- Тур Эйлера и циклы Гамильтона