維基百科

哈密頓路徑問題

圖論中的經典問題漢米頓路徑問題（中國大陸作哈密頓路徑問題）（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 .
取自「https://zh.wikipedia.org/w/index.php?title=哈密顿路径问题&oldid=83142177」