哈密頓路徑問題

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

正十二面體上的哈密頓環(紅色)。

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

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

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


算法

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

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

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

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

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

複雜度

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

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

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

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

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

外部連結

  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 .