主题
Search

哈密顿路径

哈密顿路径，也称为 Hamilton path，是 图路径，位于 图 的两个顶点之间，并且恰好访问每个顶点一次。如果存在端点相邻的哈密顿路径，则生成的 图环 称为 哈密顿环（或 Hamiltonian cycle）。

拥有哈密顿路径的图称为 可追踪图。

一般来说，找到哈密顿路径的问题是 NP-完全 的 (Garey and Johnson 1983, pp. 199-200)，因此确定给定通用 图 是否具有哈密顿路径的唯一已知方法是进行穷举搜索

任何顶点奇偶性不平衡 >1 的 二分图 都没有哈密顿路径。

在 Wolfram 语言 中，实现了查找图 g 的单个哈密顿路径，命令如下：FindHamiltonianPath[g]。可以使用以下命令（效率低下）找到给定图的所有哈密顿路径：HamiltonianPath[g,All] 在 Wolfram 语言 包中Combinatorica`。可以使用以下命令获得许多命名图的所有哈密顿路径的预计算列表：GraphData[graph,"HamiltonianPaths"]，其中包含路径的两个方向（因此 {1, 2, 3} 被认为与 {3, 2, 1} 不同）。哈密顿路径的相应数量的预计算计数由以下命令给出：GraphData[graph,"HamiltonianPathCount"].

对于阶数 n=1, 2, ... 的所有简单图，有向哈密顿路径的总数分别为 0, 2, 8, 50, 416, 5616, 117308, 4862736, ... (OEIS A193352)。

Rubin (1974) 描述了一种高效的搜索程序，可以使用大大减少回溯和猜测的推导来查找图中的某些或所有哈密顿路径和环路。Wilf (1994) 描述的 Angluin 和 Valiant (1979) 提出的概率算法也可能有助于查找哈密顿环和路径。如果哈密顿环的算法可用，则可以找到两个顶点 i 和 j 之间的哈密顿路径。这可以通过检查原始图 G 是否包含边 (i,j)，如果不存在则添加它以获得 G^' 来完成。由于具有相邻端点的哈密顿路径是 哈密顿环，并且由于 i 和 j 现在相邻，因此找到哈密顿环并在边处分割会得到从 i 到 j 在 G 中的哈密顿路径。同样，如果 G^' 中不存在哈密顿环，则 G 中没有从 i 到 j 的哈密顿路径。

洛瓦兹猜想 陈述，毫无例外，每个 连通 顶点传递图 都是 可追踪的。

下表总结了各种图类上（无向）哈密顿路径的数量。

图公式
哑铃图[(n-1)!]^2
鸡尾酒会图 K_(n×2)(2n)!_1F_1(-n;-2n;-2)
完全图 K_nn!
完全二分图 K_(n,n)(n!)^2
2n-交叉棱柱图6·2^(n-1)n(n+1)
环图 C_nn
齿轮图n(n+1)
梯形图 P_2 square P_nn^2-n+2
莫比乌斯梯 M_n1/2(-1)^nn[-1+(-1)^n(5+2n^2)]
路径图 P_n1
棱柱图 Y_n1/2n[3+(-1)^n+2n^2]
太阳图n(n+1)
轮图 W_n2(n-1)(n-2)

下面总结了一些图族的有向哈密顿路径数量的递归关系。

图阶数递归
反棱柱图9a_n=a_(n-9)+a_(n-8)-3a_(n-7)-5a_(n-6)+5a_(n-5)+7a_(n-4)-4a_(n-3)-6a_(n-2)+5a_(n-1)
皇冠图3a_n=n(n-1)^2a_(n-2)+(n-2)n(n-1)a_(n-3)+n(n-1)a_(n-1)
棱柱图 Y_n6a_n=-a_(n-6)+2a_(n-5)+a_(n-4)-4a_(n-3)+a_(n-2)+2a_(n-1)

参见

图环, 图路径, 哈密顿环, 哈密顿图, 哈密顿游走, 最长路径, 洛瓦兹猜想, 竞赛图, 可追踪图

使用 Wolfram|Alpha 探索

参考文献

Angluin, D. and Valiant, L. "Probabilistic Algorithms for Hamiltonian Circuits and Matchings." J. Comput. Sys. Sci. 18, 155-190, 1979.Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, p. 199, 1983.Godsil, C. and Royle, G. "Hamilton Paths and Cycles." C§3.6 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 45-47, 2001.Gould, R. J. "Updating the Hamiltonian Problem--A Survey." J. Graph Th. 15, 121-157, 1991.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Rubin, F. "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21, 576-580, 1974.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 175, 1990.Sloane, N. J. A. Sequences A005843, A006070/M5295, A046092, A158664, A033996, A091299, A096969, A096970, A124350, A124352, A137890, A137892, A165134, A193346, and A233826 in "The On-Line Encyclopedia of Integer Sequences."Wilf, H. S. Algorithms and Complexity. pp. 120-122. Summer, 1994. http://www.math.upenn.edu/~wilf/AlgoComp.pdf.

在 Wolfram|Alpha 上被引用

哈密顿路径

请引用为

Weisstein, Eric W. "哈密顿路径。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/HamiltonianPath.html

学科分类