此條目需要,以確保文法、、、等使用恰当。 (2022年6月7日) |
此條目目前正依照en:Hamiltonian path problem上的内容进行。 (2020年10月4日) |
图论中的经典问题哈密顿路径问题(台湾作漢米頓路徑問題)(Hamiltonian path problem)与哈密顿环问题(台湾作漢米頓環問題)(Hamiltonian cycle problem)分别是来确定在一个给定的图上是否存在哈密顿路径(一条经过图上每个顶点的路径)和哈密顿环(一条经过图上每个顶点的环)。两个问题皆为(NP完全)。
哈密顿环问题与哈密顿路径问题之间的关系
哈密顿环问题与哈密顿路径问题之间有着很简单的关系:
- 给定图 ,通过加入新顶点 并将新顶点与所有其他顶点连接起来,我们得到了图。 在图 之上的哈密顿路径问题与在之上的哈密顿环问题等价。因此寻找哈密顿路径的速度不可能比寻找哈密顿环的速度快很多。
- 从另一个方向来看,给定图,给定图上一个顶点,通过加入新顶点给定图,并且让的邻居等于的邻居,再增加两个(度)为1的新顶点,并让他们分别与和相连,得到图,则图上的哈密顿环问题与图上的哈密顿路径问题等价。
算法
在一个阶数为的图中,可能成为哈密顿路径的顶点序列最多有有!个(在(完全图)的情况下恰好为!个),因此(暴力搜索)所有可能的顶点序列是非常慢的。 一个早期的在有向图上寻找哈密顿环的算法是Martello的枚举算法 由Frank Rubin 提供的搜索过程将图的边分为3种类型:必须在路径上的边、不能在路径上的边和未定边。在搜索的过程中,一个决策规则的集合将未定边进行分类,并且决定是否继续进行搜索。这个算法将图分成几个部分,在它们上问题能够被单独地解决。
另外, 的(动态规划)算法可以在O(n2 2n)时间内解决问题。在这个方法中,对每个顶点集和其中的每一个顶点 ,均做出如下的判定:是否有一条经过中每个顶点,并且在结束的路径,对于每一对和,当且仅当存在的邻居满足存在一条路径经过的所有顶点,并在上结束的路径时,存在路径经过中每个顶点,并且在结束。这个(充要条件)已经可以之前的动态规划计算中确认。
Andreas Björklund通过(容斥原理)将哈密尔顿环的计数问题规约成一个更简单,圈覆盖的计数问题,后者可以被通过计算某些矩阵的行列式解决。通过这个方法,并通过(蒙特卡洛算法),对任意阶图,可以在O(1.657n)时间内解决。对于(二分图),这个算法可以被进一步提升至(1.415n)。
对于最大度小于等于3的图,一个回溯搜索的方法可以在 O(1.251n)时间内找到哈密顿环。
哈密顿环和哈密顿路径也可以通过找到。
复杂度
哈密顿环和哈密顿路径问题是问题,它的决定性问题是检测是否存在一条哈密顿环或哈密顿路径。有向图和无向图上的哈密顿环问题是(卡普的二十一个NP-完全问题)中的其中两个。对于一些特殊类型的图来说,它们仍然是NP完全的。例如:
- (二分图)
- 最大度为3的无向(平面图)
- 入度和出度最大为2的有向平面图
- 的无向的平面3-正则二分图
- 3-顶点连通,3-正则的二分图
- 的子图
- square grid graph的3-正则子图
然而,对于某些类型的图,哈密顿环和哈密顿路径问题可以在多项式时间内解决:
- 根据(威廉·湯瑪斯·圖特)的结论, 平面图总是存在哈密顿环,并且可以在线性时间内找到哈密顿环。 by computing a so-called .
- 圖特通过证明2-正则平面图包含圖特路径,证明了以上的结论。对2-正则平面图来说,其圖特路径可以在平方时间内找到,这可能可以被用来寻找一般平面图上的哈密顿环和较长的环。
将以上提供的条件汇总起来,3-正则,3-定点连通的二分图是否总是存在哈密顿环这一问题仍然是开放的,在这个情况下这一问题不是NP完全的,详见。
在所有顶点的度都是奇数的途中,一个与握手引理有关的结论说明对于任意一条边来说,经过它的哈密顿环的个数总是偶数,因此如果存在一条哈密顿环,则一定存在另一条 然而,找到第二条哈密顿换并不是一个简单的计算问题。定义了一个(复杂性类) 来描述这一类问题。
外部連結
- Hamiltonian Page :
- and , , W.H. Freeman, 1979, 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, , 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
- , Dynamic programming treatment of the travelling salesman problem, (Journal of the ACM), 1962, 9: 61–63, doi:10.1145/321105.321111.
- Held, 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, , 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, , 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].
- ; ; , 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), , 1979, 8 (4): 199–201 [2020-10-03], doi:10.1016/0020-0190(79)90023-1, (原始内容 (PDF)于2020-11-25).
- Akiyama, Takanori; ; 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, , 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], , 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, , MR 0499124, doi:10.1016/S0167-5060(08)70511-9.
- , On the complexity of the parity argument and other inefficient proofs of existence, , 1994, 48 (3): 498–532, MR 1279412, doi:10.1016/S0022-0000(05)80063-7.
維基百科,wiki,書籍,書籍,圖書館,文章,文章,閱讀,下載,免費下載,免費下載,MP3,視頻,MP4,3GP,JPG,JPG,JPEG,JPEG,GIF,PNG,PNG,圖片,音樂,音樂,音樂,歌曲,電影,電影,書籍,書籍,遊戲,遊戲,遊戲,遊戲,手機,電話,Android,iOS,Apple,手機,三星,iPhone,Xiomi,xiaomi, 小米,Redmi,Honor,Oppo,Nokia,Sonya,MI,個人電腦,網絡,電腦