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

Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи 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[англ.]. Аналогичная задача разрешимости — проверить, существует ли гамильтонов цикл или путь. Ориентированные и неориентированные задачи о гамильтоновом цикле являлись двумя из 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.

Литература

править
  • Michael R. Garey, David S. Johnson. [Computers and Intractability: A Guide to the Theory of NP-Completeness Computers and Intractability: A Guide to the Theory of NP-Completeness]. — W.H. Freeman, 1979. — ISBN 978-0-7167-1045-5.
  • Silvano Martello. An Enumerative Algorithm for Finding Hamiltonian Circuits in a Directed Graph // ACM Transactions on Mathematical Software. — 1983. — Т. 9, вып. 1. — С. 131–138. — doi:10.1145/356022.356030.
  • Frank Rubin. A Search Procedure for Hamilton Paths and Circuits // Journal of the ACM. — 1974. — Т. 21, вып. 4. — С. 576–80. — doi:10.1145/321850.321854.
  • Richard Bellman. Dynamic programming treatment of the travelling salesman problem // Journal of the ACM. — 1962. — Т. 9. — С. 61–63. — doi:10.1145/321105.321111.
  • Held, Karp. A dynamic programming approach to sequencing problems // J. SIAM. — 1962. — Т. 10, вып. 1. — С. 196–210. — doi:10.1137/0110015.
  • Andreas Björklund. Determinant sums for undirected Hamiltonicity // Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10). — 2010. — С. 173–182. — ISBN 978-1-4244-8525-3. — doi:10.1109/FOCS.2010.24.
  • Kazuo Iwama, Takuya Nakashima. An improved exact algorithm for cubic graph TSP // Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007). — 2007. — Т. 4598. — С. 108–117. — (Lecture Notes in Computer Science). — ISBN 978-3-540-73544-1. — doi:10.1007/978-3-540-73545-8_13.
  • Leonard Adleman. Molecular computation of solutions to combinatorial problems // Science. — 1994. — Ноябрь (т. 266, вып. 5187). — С. 1021–1024. — doi:10.1126/science.7973651. — Bibcode1994Sci...266.1021A. — PMID 7973651. — JSTOR 2885489.
  • Mihai Oltean. A light-based device for solving the Hamiltonian path problem // Unconventional Computing. — Springer LNCS 4135, 2006. — doi:10.1007/11839132_18.
  • Michael Garey, David S. Johnson, Larry Stockmeyer. Some simplified NP-complete problems // Proc. 6th ACM Symposium on Theory of Computing (STOC '74). — 1974. — С. 47–63. — doi:10.1145/800119.803884.
  • Plesńik J. The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two // Information Processing Letters. — 1979. — Т. 8, вып. 4. — С. 199–201. — doi:10.1016/0020-0190(79)90023-1.
  • Takanori Akiyama, Takao Nishizeki, Nobuji Saito. NP-completeness of the Hamiltonian cycle problem for bipartite graphs // Journal of Information Processing. — 1980–1981. — Т. 3, вып. 2. — С. 73–76.
  • Alon Itai, Christos Papadimitriou, Jayme Szwarcfiter. Hamilton Paths in Grid Graphs // SIAM Journal on Computing. — 1982. — Т. 4, вып. 11. — С. 676–686. — doi:10.1137/0211056.
  • Michael Buro. Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs // Conference on Computers and Games. — 2000. — Т. 2063. — С. 250–261. — (Lecture Notes in Computer Science). — ISBN 978-3-540-43080-3. — doi:10.1007/3-540-45579-5_17.
  • Norishige Chiba, Takao Nishizeki. The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs // Journal of Algorithms. — 1989. — Т. 10, вып. 2. — С. 187–211. — doi:10.1016/0196-6774(89)90012-6.
  • Andreas Schmid, Jens M. Schmidt. Computing Tutte Paths // Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear.. — 2018.
  • Thomason A. G. Hamiltonian cycles and uniquely edge colourable graphs // Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977). — 1978. — Т. 3. — С. 259–268. — (Annals of Discrete Mathematics). — ISBN 9780720408430. — doi:10.1016/S0167-5060(08)70511-9.
  • Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence // Journal of Computer and System Sciences. — 1994. — Т. 48, вып. 3. — С. 498–532. — doi:10.1016/S0022-0000(05)80063-7.