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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

Сложность

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

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

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

В графах в которых все вершины имеют нечётную степень, довод, связанный с леммой о рукопожатиях, показывает, что число гамильтоновых циклов через фиксированное ребро всегда чётно, так что если дан один гамильтонов цикл, то и другой должен существовать[18]. Однако поиск этого второго цикла не выглядит как простая вычислительная задача. Пападимитриу определил класс сложности PPA[англ.], чтобы собрать вместе задачи, подобные этой[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.

Литература

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Задача_о_гамильтоновом_пути&oldid=5906257