哈密頓路徑問題

圖論中的經典問題漢米頓路徑問題（中國大陸作哈密頓路徑問題，台灣作漢米頓路徑問題）（Hamiltonian path problem）與漢米頓環問題（中國大陸作哈密頓環問題，台灣作漢米頓環問題）（Hamiltonian cycle problem）分別是來確定在一個給定的圖上是否存在哈密頓路徑（一條經過圖上每個頂點的路徑）和哈密頓環（一條經過圖上每個頂點的環）。兩個問題皆為NP完全。^[1]

哈密頓環問題與哈密頓路徑問題之間的關係[編輯]

哈密頓環問題與哈密頓路徑問題之間有着很簡單的關係：

給定圖 $G$ ,通過加入新頂點 $v$ 並將新頂點與所有其他頂點連接起來，我們得到了圖 $H$ 。在圖 $G$ 之上的哈密頓路徑問題與在 $H$ 之上的哈密頓環問題等價。因此尋找哈密頓路徑的速度不可能比尋找哈密頓環的速度快很多。
從另一個方向來看，給定圖 $G$ ，給定圖上一個頂點 $v$ ，通過加入新頂點給定圖 $v'$ ,並且讓 $v'$ 的鄰居等於 $v$ 的鄰居，再增加兩個度為1的新頂點，並讓他們分別與 $v$ 和 $v'$ 相連，得到圖 $H$ ，則圖 $G$ 上的哈密頓環問題與圖 $H$ 上的哈密頓路徑問題等價。^[2]

算法[編輯]

在一個階數為 $n$ 的圖中，可能成為哈密頓路徑的頂點序列最多有有 $n$ !個（在完全圖的情況下恰好為 $n$ !個)，因此暴力搜索所有可能的頂點序列是非常慢的。一個早期的在有向圖上尋找哈密頓環的算法是Martello的枚舉算法^[3] 由Frank Rubin^[4] 提供的搜索過程將圖的邊分為3種類型：必須在路徑上的邊、不能在路徑上的邊和未定邊。在搜索的過程中，一個決策規則的集合將未定邊進行分類，並且決定是否繼續進行搜索。這個算法將圖分成幾個部分，在它們上問題能夠被單獨地解決。

另外，Bellman, Held, and Karp 的動態規劃算法可以在O(n² 2ⁿ)時間內解決問題。在這個方法中，對每個頂點集 $S$ 和其中的每一個頂點 $v$ ，均做出如下的判定：是否有一條經過 $S$ 中每個頂點，並且在 $v$ 結束的路徑，對於每一對 $S$ 和 $v$ ，若且唯若存在 $v$ 的鄰居 $w$ 滿足存在一條路徑經過 $S-v$ 的所有頂點，並在 $w$ 上結束的路徑時，存在路徑經過 $S$ 中每個頂點，並且在 $v$ 結束。這個充要條件已經可以之前的動態規劃計算中確認。^[5]^[6]

Andreas Björklund通過容斥原理將哈密爾頓環的計數問題規約成一個更簡單，圈覆蓋的計數問題，後者可以被通過計算某些矩陣的行列式解決。通過這個方法，並通過蒙特卡洛算法，對任意 $n$ 階圖，可以在O(1.657ⁿ)時間內解決。對於二分圖，這個算法可以被進一步提升至o(1.415ⁿ)。^[7]

對於最大度小於等於3的圖，一個回溯搜索的方法可以在 O(1.251ⁿ)時間內找到哈密頓環。^[8]

哈密頓環和哈密頓路徑也可以通過SAT 求解器找到。

複雜度[編輯]

哈密頓環和哈密頓路徑問題是FNP問題，它的決定性問題是檢測是否存在一條哈密頓環或哈密頓路徑。有向圖和無向圖上的哈密頓環問題是卡普的二十一個NP-完全問題中的其中兩個。對於一些特殊類型的圖來說，它們仍然是NP完全的。例如：

二分圖,^[9]
最大度為3的無向平面圖,^[10]
入度和出度最大為2的有向平面圖,^[11]
無橋的無向的平面3-正則二分圖，
3-頂點連通，3-正則的二分圖，^[12]
square grid graph的子圖,^[13]
square grid graph的3-正則子圖.^[14]

然而，對於某些類型的圖，哈密頓環和哈密頓路徑問題可以在多項式時間內解決：

根據威廉·湯瑪斯·圖特的結論，4-頂點連通平面圖總是存在哈密頓環，並且可以在線性時間內找到哈密頓環。^[15] by computing a so-called Tutte path.
圖特通過證明2-正則平面圖包含圖特路徑，證明了以上的結論。對2-正則平面圖來說，其圖特路徑可以在平方時間內找到，^[16], 這可能可以被用來尋找一般平面圖上的哈密頓環和較長的環。

將以上提供的條件匯總起來，3-正則，3-定點連通的二分圖是否總是存在哈密頓環這一問題仍然是開放的,在這個情況下這一問題不是NP完全的，詳見 Barnette's conjecture.

在所有頂點的度都是奇數的途中，一個與握手引理有關的結論說明對於任意一條邊來說，經過它的哈密頓環的個數總是偶數，因此如果存在一條哈密頓環，則一定存在另一條 ^[17] 然而，找到第二條哈密頓換並不是一個簡單的計算問題。Papadimitriou定義了一個複雜性類複雜性類 PPA來描述這一類問題。 ^[18]

外部連結[編輯]

Hamiltonian Page : Hamiltonian cycle and path problems, their generalizations and variations

^ Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 978-0-7167-1045-5 A1.3: GT37–39, pp. 199–200.
^ Reduction from Hamiltonian cycle to Hamiltonian path
^ Martello, Silvano, 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
^ Rubin, Frank, A Search Procedure for Hamilton Paths and Circuits, Journal of the ACM, 1974, 21 (4): 576–80, doi:10.1145/321850.321854
^ Bellman, R., Dynamic programming treatment of the travelling salesman problem, Journal of the ACM, 1962, 9: 61–63, doi:10.1145/321105.321111 .
^ Held, M.; Karp, R. M., A dynamic programming approach to sequencing problems (PDF), J. SIAM, 1962, 10 (1): 196–210 [2020-10-03], doi:10.1137/0110015, hdl:10338.dmlcz/103900, （原始內容存檔 (PDF)於2019-09-22）。
^ Björklund, Andreas, Determinant sums for undirected Hamiltonicity, Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10): 173–182, 2010, ISBN 978-1-4244-8525-3, arXiv:1008.0541 , doi:10.1109/FOCS.2010.24 。
^ Iwama, Kazuo; Nakashima, Takuya, An improved exact algorithm for cubic graph TSP, Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007), Lecture Notes in Computer Science 4598: 108–117, 2007, ISBN 978-3-540-73544-1, doi:10.1007/978-3-540-73545-8_13 。
^ Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete. Computer Science Stack Exchange. [2019-03-18].
^ Garey, M. R.; Johnson, D. S.; Stockmeyer, L., Some simplified NP-complete problems, Proc. 6th ACM Symposium on Theory of Computing (STOC '74): 47–63, 1974, doi:10.1145/800119.803884 .
^ Plesńik, J., The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two (PDF), Information Processing Letters, 1979, 8 (4): 199–201 [2020-10-03], doi:10.1016/0020-0190(79)90023-1, （原始內容存檔 (PDF)於2020-11-25） .
^ Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji, NP-completeness of the Hamiltonian cycle problem for bipartite graphs, Journal of Information Processing, 1980–1981, 3 (2): 73–76, MR 0596313 .
^ Itai, Alon; Papadimitriou, Christos; Szwarcfiter, Jayme, Hamilton Paths in Grid Graphs, SIAM Journal on Computing, 1982, 4 (11): 676–686, doi:10.1137/0211056 .
^ Buro, Michael, Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs (PDF), Conference on Computers and Games, Lecture Notes in Computer Science 2063: 250–261, 2000 [2020-10-03], ISBN 978-3-540-43080-3, doi:10.1007/3-540-45579-5_17, （原始內容存檔 (PDF)於2020-11-06） .
^ Chiba, Norishige; Nishizeki, Takao, 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
^ Schmid, Andreas; Schmidt, Jens M., 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), Annals of Discrete Mathematics 3: 259–268, 1978, ISBN 9780720408430, MR 0499124, doi:10.1016/S0167-5060(08)70511-9 .
^ Papadimitriou, Christos H., On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences, 1994, 48 (3): 498–532, MR 1279412, doi:10.1016/S0022-0000(05)80063-7 .

[1] Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 978-0-7167-1045-5 A1.3: GT37–39, pp. 199–200.

[2] Reduction from Hamiltonian cycle to Hamiltonian path

[3] Martello, Silvano, 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

[4] Rubin, Frank, A Search Procedure for Hamilton Paths and Circuits, Journal of the ACM, 1974, 21 (4): 576–80, doi:10.1145/321850.321854

[5] Bellman, R., Dynamic programming treatment of the travelling salesman problem, Journal of the ACM, 1962, 9: 61–63, doi:10.1145/321105.321111 .

[6] Held, M.; Karp, R. M., A dynamic programming approach to sequencing problems (PDF), J. SIAM, 1962, 10 (1): 196–210 [2020-10-03], doi:10.1137/0110015, hdl:10338.dmlcz/103900, （原始內容存檔 (PDF)於2019-09-22）。

[7] Björklund, Andreas, Determinant sums for undirected Hamiltonicity, Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10): 173–182, 2010, ISBN 978-1-4244-8525-3, arXiv:1008.0541 , doi:10.1109/FOCS.2010.24 。

[8] Iwama, Kazuo; Nakashima, Takuya, An improved exact algorithm for cubic graph TSP, Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007), Lecture Notes in Computer Science 4598: 108–117, 2007, ISBN 978-3-540-73544-1, doi:10.1007/978-3-540-73545-8_13 。

[9] Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete. Computer Science Stack Exchange. [2019-03-18].

[10] Garey, M. R.; Johnson, D. S.; Stockmeyer, L., Some simplified NP-complete problems, Proc. 6th ACM Symposium on Theory of Computing (STOC '74): 47–63, 1974, doi:10.1145/800119.803884 .

[11] Plesńik, J., The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two (PDF), Information Processing Letters, 1979, 8 (4): 199–201 [2020-10-03], doi:10.1016/0020-0190(79)90023-1, （原始內容存檔 (PDF)於2020-11-25） .

[12] Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji, NP-completeness of the Hamiltonian cycle problem for bipartite graphs, Journal of Information Processing, 1980–1981, 3 (2): 73–76, MR 0596313 .

[13] Itai, Alon; Papadimitriou, Christos; Szwarcfiter, Jayme, Hamilton Paths in Grid Graphs, SIAM Journal on Computing, 1982, 4 (11): 676–686, doi:10.1137/0211056 .

[14] Buro, Michael, Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs (PDF), Conference on Computers and Games, Lecture Notes in Computer Science 2063: 250–261, 2000 [2020-10-03], ISBN 978-3-540-43080-3, doi:10.1007/3-540-45579-5_17, （原始內容存檔 (PDF)於2020-11-06） .

[15] Chiba, Norishige; Nishizeki, Takao, 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

[16] Schmid, Andreas; Schmidt, Jens M., Computing Tutte Paths, Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear., 2018

[17] Thomason, A. G., Hamiltonian cycles and uniquely edge colourable graphs, Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics 3: 259–268, 1978, ISBN 9780720408430, MR 0499124, doi:10.1016/S0167-5060(08)70511-9 .

[18] Papadimitriou, Christos H., On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences, 1994, 48 (3): 498–532, MR 1279412, doi:10.1016/S0022-0000(05)80063-7 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]