哈密頓路徑問題

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

正十二面體上的哈密頓環（紅色）。

哈密頓環問題與哈密頓路徑問題之間的關係

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

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

算法

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

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

Andreas Björklund通過容斥原理將哈密爾頓環的計數問題規約成一個更簡單，圈覆蓋的計數問題，後者可以被通過計算某些矩陣的行列式解決。通過這個方法，並通過蒙特卡洛算法，對任意${\displaystyle 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猜想（英語：Barnette's conjecture）。

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

外部連結

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

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.