Задача о гамильтоновом пути

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Задача о гамильтоновом цикле является также частным случаем задачи коммивояжёра, полученной установкой всех расстояний между двумя пунктами в единицу, если они смежны, и двум в противном случае. После решения задачи коммивояжёра следует проверить, что полное расстояние равно n (если так, маршрут является гамильтоновым циклом, если же гамильтонова цикла нет, кратчайший путь будет длиннее этой величины).

Алгоритмы[править | править код]

Есть n! различных последовательностей вершин, которые могут быть гамильтоновыми путями в заданном графе с n вершинами (и их столько в полном графе), так что алгоритм полного перебора, который перебирает все возможные последовательности, был бы очень медленным.

Ранний точный алгоритм нахождения гамильтонова цикла в ориентированном графе был алгоритмом перебора (алгоритм Мартелло)[3].

Процедура поиска Франка Рубина[4] разбивает рёбра графа на три класса — те, которые должны быть на пути, те, которые пути принадлежать не могут, и рёбра, для которых решение не принято. В процессе поиска набор правил принятия решений классифицирует рёбра, для которых решение не принято, и определяет, остановиться или продолжить поиск. Алгоритм разбивает граф на компоненты, которые могут быть обработаны отдельно.

Для решения задачи за время может быть использован алгоритм динамического программирования Беллмана, Хелда и Карпа. В этом методе определяется для каждого набора S вершин и каждой вершины v из S, существует ли путь, проходящий через все вершины S и заканчивающийся в v. Для каждой пары (S,v) путь существует тогда и только тогда, когда v имеет соседнюю вершину w такую, что существует путь для , который можно получить из уже полученной информации динамического программирования[5][6].

Андреас Бьёрклунд даёт альтернативный подход, использующий принцип включения/исключения для сокращения числа перебираемых гамильтоновых циклов и задача подсчёта циклов может быть решена путём вычисления определителя некоторой матрицы.

Используя этот метод, он показал, как решить задачу о гамильтоновом цикле для произвольных графов с n вершинами с помощью алгоритма Монте-Карло за время . Для двудольных графов этот алгоритм можно улучшить до времени [7].

Для графов с максимальной степенью три аккуратный поиск с возвратом может найти гамильтонов цикл (если таковой существует) за время [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].

Примечания[править | править код]

  1. Garey, Johnson, 1979, с. 199—200, A1.3: GT37 - 39.
  2. graph theory - Reduction from Hamiltonian cycle to Hamiltonian path - Mathematics Stack Exchange. Дата обращения: 18 февраля 2019. Архивировано 23 апреля 2019 года.
  3. Martello, 1983, с. 131–138.
  4. Rubin, 1974, с. 576–80.
  5. Bellman, 1962, с. 61–63.
  6. Held, Karp, 1962, с. 196–210.
  7. Björklund, 2010, с. 173–182.
  8. Iwama, Nakashima, 2007, с. 108–117.
  9. Adleman, 1994, с. 1021–1024.
  10. Oltean, 2006, с. 217–227.
  11. Garey, Johnson, Stockmeyer, 1974, с. 47–63.
  12. Plesńik, 1979, с. 199–201.
  13. Akiyama, Nishizeki, Saito, 1980–1981, с. 73–76.
  14. Itai, Papadimitriou, Szwarcfiter, 1982, с. 676–686.
  15. Buro, 2000, с. 250–261.
  16. Chiba, Nishizeki, 1989, с. 187–211.
  17. Schmid, Schmidt, 2018.
  18. Thomason, 1978, с. 259–268.
  19. Papadimitriou, 1994, с. 498–532.

Литература[править | править код]