Введение

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

В математической области теории графов, гамильтонов путь (или прослеживаемый путь) — это путь в неориентированном или ориентированном графе, который посещает каждую вершину ровно один раз. Гамильтонов цикл (или гамильтоновская цепь) — это цикл, который посещает каждую вершину ровно один раз. Гамильтонов путь, начинающийся и заканчивающийся в смежных вершинах, можно дополнить одним ребром, чтобы получить гамильтонов цикл, а удаление любого ребра из гамильтонова цикла приводит к гамильтонову пути. Вычислительные задачи определения существования таких путей и циклов в графах являются NP-полными; подробности см. в статье «Задача о гамильтоновом пути». Гамильтоновы пути и циклы названы в честь Уильяма Роуэна Гамильтона, который изобрел икозианскую игру, теперь также известную как головоломка Гамильтона, заключающуюся в поиске гамильтонова цикла в графе ребер додекаэдра. Гамильтон решил эту задачу, используя икозианский анализ — алгебраическую структуру, основанную на корнях из единицы, имеющую много общего с кватернионами (также изобретенными Гамильтоном). Это решение не обобщается на произвольные графы. Несмотря на то, что они названы в честь Гамильтона, гамильтоновы циклы в многогранниках также изучались годом ранее Томасом Киркманом, который, в частности, привел пример многогранника, не имеющего гамильтоновых циклов. Еще раньше гамильтоновы циклы и пути в рыцарском графе шахматной доски, известный как тур рыцаря, изучались в IX веке в индийской математике Рудратой и примерно в то же время в исламской математике аль-Адли ар-Руми. В Европе XVIII века туры рыцаря были опубликованы Авраамом де Муавром и Леонардом Эйлером.

Определения

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

Свойства

Любой гамильтонов цикл можно преобразовать в гамильтонов путь, удалив одно из его ребер, но гамильтонов путь можно расширить до гамильтонова цикла только в том случае, если его конечные вершины смежны. Все гамильтоновы графы бисвязны, но бисвязный граф не обязательно должен быть гамильтоновым (например, граф Петерсена). Эйлеров граф G (связный граф, в котором каждая вершина имеет четную степень) обязательно имеет эйлеров обход, замкнутый путь, проходящий по каждому ребру G ровно один раз. Этот обход соответствует гамильтонову циклу в линейном графе L(G), следовательно, линейный граф любого эйлерова графа является гамильтоновым. Линейные графы могут иметь и другие гамильтоновы циклы, не соответствующие эйлеровым обходам, и, в частности, линейный граф L(G) любого гамильтонова графа G сам по себе является гамильтоновым, независимо от того, является ли граф G эйлеровым. Турнир (с более чем двумя вершинами) является гамильтоновым тогда и только тогда, когда он сильно связен. Количество различных гамильтоновых циклов в полном ненаправленном графе на n вершинах равно , а в полном ориентированном графе на n вершинах равно (n – 1)!. Эти подсчеты подразумевают, что циклы, отличающиеся только начальной точкой, не считаются разными.

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

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