Задача про гамільтонів шлях

Задача про гамільтонів шлях і задача про гамільтонів цикл — це задачі визначення, чи існує гамільтонів шлях або гамільтонів цикл у заданому графі (орієнтованому або неорієнтованому). Обидві задачі NP-повні.

Зв'язок задач про гамільтонів шлях і гамільтонів цикл

Існує просте відношення між задачами знаходження гамільтонового шляху і знаходження гамільтонового циклу. З одного боку, задача про гамільтонів шлях для графа еквівалентна задачі про гамільтонів цикл у графі H, отриманому з графа G шляхом додавання нової вершини і з'єднання її з усіма вершинами графа G. Таким чином, пошук гамільтонового шляху не може бути істотно повільнішим (у гіршому випадку, як функція числа вершин), ніж пошук гамільтонового циклу. З іншого боку, задача про гамільтонів цикл для графа G еквівалентна задачі про гамільтонів шлях у графі H отриманому копіюванням однієї вершини v графа G (в v), тобто, вершина v матиме той самий окіл, що й v, і додаванням двох допоміжних вершин степеня один, одна з яких з'єднана з v, а інша з v. Задача про гамільтонів цикл є також окремим випадком задачі комівояжера, отриманої встановленням усіх відстаней між двома пунктами рівними 1, якщо вони суміжні, і 2 в іншому випадку. Після розв'язання задачі комівояжера слід перевірити, що повна відстань дорівнює n (якщо так, маршрут є гамільтоновим циклом, якщо ж гамільтонового циклу немає, найкоротший шлях буде довшим від цієї величини).

Алгоритми

Є n! різних послідовностей вершин, які можуть бути гамільтоновими шляхами в заданому графі з n вершинами (і їх стільки в повному графі), так що алгоритм повного перебору, який перебирає всі можливі послідовності, був би дуже повільним. Ранній точний алгоритм знаходження гамільтонового циклу в орієнтованому графі був алгоритмом перебору (алгоритм Мартелло).

Процедура пошуку Франка Рубіна розбиває ребра графа на три класи — ті, які повинні бути на шляху, ті, які шляху належати не можуть, і ребра, для яких рішення не прийнято. В процесі пошуку набір правил прийняття рішень класифікує ребра, для яких рішення не прийнято, і визначає, зупинитися чи продовжити пошук. Алгоритм розбиває граф на компоненти, які можуть бути оброблені окремо. Для вирішення завдання за час ${\displaystyle O(n^{2}2^{n})}$ може бути використаний алгоритм динамічного програмування Беллмана, Хелда і Карпа. У цьому методі для кожного набору S вершин і кожної вершини v з S визначається, чи існує шлях, що проходить через усі вершини S і закінчується у v. Для кожної пари (S, v) шлях існує тоді і тільки тоді, коли v має сусідню вершину w, таку що існує шлях для ${\displaystyle (S\setminus v,w)}$, який можна отримати зі вже отриманої інформації динамічного програмування.

Андреас Б'єрклунд дає альтернативний підхід, який використовує принцип включення-виключення для скорочення числа гамільтонових циклів, що перебираються, і задача підрахунку циклів може бути розв'язана шляхом обчислення визначника деякої матриці. Використовуючи цей метод він показав як розв'язати задачу про гамільтонів цикл для довільних графів з n вершинами за допомогою алгоритму Монте-Карло за час ${\displaystyle O(1{,}657^{n})}$. Для двочасткових графів цей алгоритм можна поліпшити до часу ${\displaystyle o(1{,}415^{n})}$.

Для графів з максимальним степенем 3 акуратний пошук з поверненням може знайти гамільтонів цикл (якщо такий існує) за час ${\displaystyle O(1{,}251^{n})}$.

Гамільтонові шляхи і цикли можна знайти за допомогою розв'язника SAT.

Зважаючи на складність розв'язування задач про гамільтонів шлях і цикл на звичайних комп'ютерах, вони вивчалися для нестандартних моделей обчислень. Наприклад, Леонард Адлеман показав, що задача про гамільтонів шлях може бути розв'язана за допомогою ДНК-комп'ютера. Використовуючи паралелізм, властивий хімічним реакціям, задача може бути розв'язана за допомогою декількох кроків хімічних реакцій, які лінійно залежать від числа вершин графа. Однак, це вимагає факторіального числа молекул ДНК, що беруть участь у реакції .

Оптичне розв'язання гамільтонової задачі запропонував Ольтеан. Ідея полягає у створенні подібної до графа структури з оптичних кабелів і розщеплювачів променя, через яку проганяється промінь у порядку розв'язування задачі. Слабким моментом цього підходу є експоненціальне зростання необхідної енергії від числа вузлів.

Складність

Задача знаходження гамільтонового циклу або шляху має складність ^[en]. Аналогічна задача розв'язності — перевірити, чи існує гамільтонів цикл або шлях. Орієнтовані і неорієнтовані задачі про гамільтонів цикл були двома з 21 NP-повних задач Карпа. Вони залишаються NP-повними навіть для неорієнтованих планарних графів максимального степеня 3, для орієнтованих планарних графів з півстепенем входу і виходу, що не перевищує 2, для неорієнтованих планарних 3-регулярних двочасткових графів без мостів, для 3-зв'язних 3-регулярних двочасткових графів, підграфів квадратної решітки і для кубічних підграфов квадратної решітки.

Однак, 4-зв'язні планарні графи завжди гамільтонові згідно з результатом Татта, а задача знаходження гамільтонового циклу в цих графах може бути розв'язана за лінійний час шляхом обчислення так званого шляху Татта. Татт довів цей результат, показавши, що будь-який 2-зв'язний планарний граф містить шлях Татта. Шляхи Татта, в свою чергу, можна обчислити за квадратичний час навіть для 2-зв'язних планарних графів, що може бути використано для пошуку гамільтонових циклів і довгих циклів в узагальнених планарних графах.

Складаючи все разом, залишається відкритою задача, чи завжди 3-зв'язні 3-регулярні двочасткові планарні графи повинні містити гамільтонів цикл і якщо повинні, задача, обмежена цими графами НЕ буде NP-повною, див. статтю «Гіпотеза Барнетта».

У графах, в яких усі вершини мають непарний степінь, довід, пов'язаний з лемою про рукостискання, показує, що число гамільтонових циклів через фіксоване ребро завжди парне, так що, якщо дано один гамильтонів цикл, то й інший повинен існувати. Однак, пошук цього іншого циклу не виглядає як проста обчислювальна задача. Пападімітріу визначив клас складності ^[en], щоб зібрати разом задачі, подібні до цієї .

Примітки

1. Garey, Johnson, 1979, с. 199-200, A1.3: GT37 - 39.
2. . Архів оригіналу за 23 квітня 2019. Процитовано 11 грудня 2019.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
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. — .
• Silvano Martello. An Enumerative Algorithm for Finding Hamiltonian Circuits in a Directed Graph // . — 1983. — Т. 9, вип. 1. — С. 131–138. — DOI:10.1145/356022.356030.
• Frank Rubin. A Search Procedure for Hamilton Paths and Circuits // . — 1974. — Т. 21, вип. 4. — С. 576–80. — DOI:10.1145/321850.321854.
• Richard Bellman. Dynamic programming treatment of the travelling salesman problem // . — 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. — . — 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). — . — DOI:10.1007/978-3-540-73545-8_13.
• Leonard Adleman. Molecular computation of solutions to combinatorial problems // Science. — 1994. — Т. 266, вип. 5187 (листопад). — С. 1021–1024. — Bibcode: 1994Sci...266.1021A. — DOI:10.1126/science.7973651. — JSTOR 2885489. — PMID 7973651.
• 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 // . — 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 // . — 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). — . — 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). — . — DOI:10.1016/S0167-5060(08)70511-9.
• Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence // . — 1994. — Т. 48, вип. 3. — С. 498–532. — DOI:10.1016/S0022-0000(05)80063-7.