WikiSort.ru - Не сортированное

Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь (путь в неориентированном или ориентированном графе, который проходит все вершины графа ровно один раз) или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны^[1].

Связь задач о гамильтоновом пути и гамильтоновом цикле

Существует простое отношение между задачами нахождения гамильтонова пути и нахождения гамильтонова цикла. В одном направлении, задача о гамильтоновом пути для графа эквивалентна задаче о гамильтоновом цикле в графе H, полученного из графа G путём добавления новой вершины и соединения её с со всеми вершинами графа G. Таким образом, поиск гамильтонова пути не может быть существенно медленнее (в худшем случае, как функция числа вершин), чем поиск гамильтонова цикла. В обратном направлении, задача о гамильтоновом цикле для графа G эквивалентна задаче о гамильтоновом пути в графе H полученном копированием одной вершины v графа G (в v'), то есть, вершина v' будет иметь ту же окрестность, что и v, и добавлением двух вспомогательных вершин степени один, одна из которых соединена с v, а другая с v'^[2]. Задача о гамильтоновом цикле является также частным случаем задачи коммивояжёра, полученной установкой всех расстояний между двумя пунктами в единицу, если они смежны, и двум в противном случае. После решения задачи коммивояжёра следует проверить, что полное расстояние равно n (если так, маршрут является гамильтоновым циклом, если же гамильтонова цикла нет, кратчайший путь будет длиннее этой величины).

Алгоритмы

Есть n! различных последовательностей вершин, которые могут быть гамильтоновыми путями в заданном графе с n вершинами (и их столько в полном графе), так что алгоритм полного перебора, который перебирает все возможные последовательности, был бы очень медленным. Ранний точный алгоритм нахождения гамильтонова цикла в ориентированном графе был алгоритмом перебора (алгоритм Мартелло)^[3]. Процедура поиска Франка Рубина ^[4] разбивает рёбра графа на три класса — те, которые должны быть на пути, те, которые пути принадлежать не могут, и рёбра, для которых решение не принято. В процессе поиска набор правил принятия решений классифицирует рёбра, для которых решение не принято, и определяет, остановиться или продолжить поиск. Алгоритм разбивает граф на компоненты, которые могут быть обработаны отдельно. Для решения задачи за время ${\displaystyle O(n^{2}2^{n})}$ может быть использован алгоритм динамического программирования Беллмана, Хелда и Карпа. В этом методе определяется для каждого набора S вершин и каждой вершины v из S, существует ли путь, проходящий через все вершины S и заканчивающийся в v. Для каждой пары (S,v) путь существует тогда и только тогда, когда v имеет соседнюю вершину w, такую что существует путь для ${\displaystyle (S\setminus v,w)}$ , который можно получить из уже полученной информации динамического программирования^[5][6].

Андреас Бьёрклунд даёт альтернативный подход, использующий принцип включения/исключения для сокращения числа перебираемых гамильтоновых циклов и задача подсчёта циклов может быть решена путём вычисления определителя некоторой матрицы. Используя этот метод он показал как решить задачу о гамильтоновом цикле для произвольных графов с n вершинами с помощью алгоритма Монте-Карло за время ${\displaystyle O(1{,}657^{n})}$ . Для двудольных графов этот алгоритм можно улучшить до времени o(1,415ⁿ)^[7].

Для графов с максимальной степенью три аккуратный поиск с возвратом может найти гамильтонов цикл (если таковой существует) за время ${\displaystyle O(1{,}251^{n})}$ ^[8].

Гамильтоновы пути и циклы можно найти с помощью SAT решателя.

Ввиду сложности решения задач о гамильтоновом пути и цикле на обычных компьютерах, они изучались для нестандартных моделей вычислений. Например, Леонард Адлеман показал, что задача о гамильтоновом пути могут быть решены с помощью ДНК-компьютера. Используя параллелелизм, свойственный химическим реакциям, задача может быть решена с помощью нескольких шагов химических реакций, линейно зависящих от числа вершин графа. Однако, это требует факториальное число молекул ДНК, участвующих в реакции^[9].

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

Сложность

Задача нахождения гамильтонова цикла или пути имеет сложность FNP^[en]. Аналогичная задача разрешимости — проверить, существует ли гамильтонов цикл или путь. Ориентированные и неориентированные задачи о гамильтоновом цикле являлись двумя из 21 NP-полных задач Карпа. Они остаются NP-полными даже для неориентированных планарных графов максимальной степени три^[11], для ориентированных планарных графов с полустепенью входа и выхода, не превосходящими двух^[12], для неориентированных планарных 3-регулярных двудольных графов без мостов, для 3-связных 3-регульных двудольных графов^[13], подграфов квадратной решётки^[14] и для кубических подграфов квадратной решётки^[15].

Однако, 4-связные планарные графы всегда гамильтоновы согласно результату Тата, а задача нахождиения гамильтонова цикла в этих графах может быть выполнена за линейное время^[16] путём вычисления так называемого пути Тата. Тат доказал этот результат, показав, что любой 2-связный планарный граф содержит путь Тата. Пути Тата, в свою очередь, можно вычислить за квадратичное время даже для 2-связных планарных графов^[17], что может быть использовано для поиска гамильтоновых циклов и длинных циклов в обобщённых планарных графах. .

Складывая всё вместе, остаётся открытой задача, всегда ли 3-связные 3-регулярные двудольные планарные графы должны содержать гамильтонов цикл и если должны, задача, ограниченная этими графами не будет NP-полной, см. статью «Гипотеза Барнетта».

В графах, в которых все вершины имеют нечётную степень, довод, связанный с леммой о рукопожатиях, показывает, что число гамильтоновых циклов через фиксированное ребро всегда чётно, так что если дан один гамильтонов цикл, то и другой должен существовать^[18]. Однако, поиск этого второго цикла не выглядит как простая вычислительная задача. Пападимитриу определил класс сложности PPA^[en], чтобы собрать вместе задачи, подобные этой^[19].

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.