主题
Search

哈密顿环

下载 Mathematica Notebook下载 Wolfram Notebook

哈密顿环，也称为哈密顿回路、哈密顿圈或哈密顿路径，是一个穿过图的图环（即闭环），它恰好访问每个节点一次（Skiena 1990, p. 196）。 具有哈密顿环的图被称为哈密顿图。 按照惯例，单例图 K_1 被认为是哈密顿图，即使它不具有哈密顿环，而两个节点的连通图 K_2 则不是。

哈密顿环以威廉·罗文·哈密顿爵士的名字命名，他设计了一个谜题，其中寻求沿多面体边的十二面体的这种路径（二十面体游戏）。

图的哈密顿环可以使用 Wolfram 语言 有效地计算，使用FindHamiltonianCycle[g][[All, All, 1]][[1]]（其中返回的环不一定是字典序第一个）。图的所有简单（无向）环都可以有效地计算时间（但内存开销超过表示实际环所需的 10 倍），使用Sort[FindHamiltonianCycle[g, All][[All, All, 1]]]。（请注意，默认情况下，返回的环不一定按排序顺序返回。）可能的Method选项包括FindHamiltonianCycleinclude"Backtrack", "Heuristic", "AngluinValiant", "Martello"和"MultiPath"。 此外，Wolfram 语言 命令FindShortestTour[g] 尝试找到最短路径，这对于哈密顿图 G 来说是一个哈密顿环（初始顶点在末尾重复），如果它返回的列表的第一个元素等于 G 的顶点计数。

可以使用以下命令获取许多命名图的哈密顿环的预计算列表GraphData[graph,"HamiltonianCycles"]。 类似地，可以使用以下命令获得相应哈密顿环数量的预计算计数GraphData[graph,"HamiltonianCycleCount"]..

对于阶数 n=1, 2, ... 的所有简单图，有向哈密顿环的总数分别为 0, 0, 2, 10, 58, 616, 9932, 333386, 25153932, 4548577688, ... (OEIS A124964)。

恰好具有一个哈密顿环的图被称为唯一哈密顿图。

一般而言，找到哈密顿环的问题是 NP 完全问题（Karp 1972；Garey 和 Johnson 1983, p. 199），因此确定给定的通用图是否具有哈密顿环的唯一已知方法是进行详尽的搜索。 Rubin (1974) 描述了一种有效的搜索程序，可以使用极大地减少回溯和猜测的推导来查找图中的一些或所有哈密顿路径和回路。 Angluin 和 Valiant (1979) 提出的概率算法，由 Wilf (1994) 描述，也可能有助于找到哈密顿环和路径。

HamiltonianPlatonicCycles

所有柏拉图立体都是哈密顿图（Gardner 1957），如上图所示。

恰好有五个已知的连通非哈密顿顶点传递图，即路径图 P_2、彼得森图 F_(010)A、考克斯特图 F_(028)A、三角形替换彼得森图和三角形替换考克斯特图。 正如 Gould (1991) 引用 Bermond (1979) 所述，Thomassen 推测所有其他连通顶点传递图都是哈密顿图（参见 Godsil 和 Royle 2001, p. 45；Mütze 2024）。

Khomenko 和 Golovko (1972) 给出了一个公式，给出了任何长度的图环的数量，但它的计算需要计算和执行涉及大小高达 n-2 的所有子集的矩阵运算，这使得计算成本很高。 Khomenko 和 Golovko 公式的一个大大简化和改进的版本，用于 n-环（即哈密顿环）的特殊情况，给出

c_n=1/(2n)sum_(i=2)^n(-1)^(n-i)sum_(|S|=n-i)Tr(A_S^n),

其中 A_S^k 是邻接矩阵 A 的子矩阵的第 k 次矩阵幂，其中删除了行和列的子集 S，Tr 是矩阵迹 (Perepechko 和 Voropaev)。

下表总结了各种图类上的（无向）哈密顿环的数量。n-超立方体由 Gardner (1986, pp. 23-24) 考虑，然而他给出了 n-超立方体的计数，对于 n=1, 2, ... 为 2, 8, 96, 43008, ... (OEIS A006069)，这必须除以 2^n 才能得到不同（有向）环的数量，而不管起始顶点如何，都将点的位移视为等效。

图OEIS序列
Andrásfai 图A3079020, 1, 5, 145, 8697, 1109389, 236702901, ...
反棱柱图A306447X, X, 16, 29, 56, 110, 225, 469, 991, 2110, 4511, ...
(n,n)-黑主教图A307920X, X, 0, 4, 704, 553008, , 13802629632, 1782158930138112, ...
鸡尾酒会图 K_(n×2)A3079230, 1, 16, 744, 56256, ...
完全图 K_nA0017100, 0, 1, 3, 12, 60, 360, 2520, 20160, 181440, ...
完全二部图 K_(n,n)A0107960, 1, 6, 72, 1440, 43200, 1814400, ...
完全三部图 K_(n,n,n)A3079241, 16, 1584, 463104, 29928960, ...
2n-交叉棱柱图A007283X, X, X, 6, 12, 24, 48, 96, 192, 384, 768, 1536, ...
皇冠图A3064961, 6, 156, 4800, 208440, 11939760, 874681920, ...
立方体连接环图A000000X, X, 6, 28628, ...
环图 C_nA000012X, X, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
折叠立方体图A307925X, 0, 3, 72, 23760, 332012113920, ...
网格图 P_n square P_nA0037630, 1, 0, 6, 0, 1072, 0, 4638576, 0, ...
网格图 P_n square P_n square P_nA0000000, 6, 0, ?, 0, ...
半立方体图A3079260, 0, 3, 744, 986959440, 312829871511322359060480, ...
超立方体图 Q_nA0660370, 1, 6, 1344, 906545760, ...
(n,n)-国王图A140519X, 3, 16, 2830, 2462064, 22853860116, ...
(n,n)-骑士图A001230X, 0, 0, 0, 0, 9862, 0, 13267364410532, ...
n-梯形图A0574270, 1, 1, 1, 1, 1, 1, ...
莫比乌斯梯形A103889X, X, X, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15, ...
Mycielski 图A3079270, 1, 10, 102310, ...
奇图A301557X, 1, 0, 1419264, ...
置换星图A0000000, 0, 1, 18, ...
棱柱图 Y_nA103889X, X, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, ...
(n,n)-皇后图A3079280, 3, 1960, 402364270, 39741746126749664, ...
车图 K_n square K_nA269561X, 1, 48, 284112, 167875338240, ...
太阳图A000012X, X, 1, 1, 1, 1, 1, 1, ...
环面网格图 C_n square C_nA222199X, X, 48, 1344, 23580, 3273360, ...
转置图A3078960, 0, 6, 569868288, ...
三角图A307930X, 0, 1, 16, 3216, 9748992, ...
三角形网格图A1126761, 1, 3, 26, 474, 17214, 685727, ...
轮图 W_nA000027X, X, X, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
(n,n)-白主教图A307929X, X, 1, 4, 396, 553008, 4701600128, 1782158930138112, ...

下表总结了其中一些图类的闭合形式，其中 alpha、beta 和 gamma 是 x^3-x^2-2x-1 的根，K_x(x) 是第二类修正贝塞尔函数。

图公式
反棱柱图(2n+alpha^n+beta^n+gamma^n)
鸡尾酒会图 K_(n×2)1/2(2n-1)!_1F_1(-n,1-2n;-2)
完全图 K_n1/2(n-1)!
完全二部图 K_(n,n)1/2n!(n-1)!
完全三部图 K_(n,n,n)2^(n-1)(n-1)!(n!)2_3F_2(1/2(n-1),-1/2n,n;1,1,1)
2n-交叉棱柱图3/2·2^n
皇冠图(-1)^n(n-1)!+n!sum_(j=0)^(n-1)(-1)^j(n-j-1)!(2n-j-1; j)
=1/2(n-1)!nint(2ne^(-2)K_n(2))
环图 C_n1
河内图1
梯形图 P_2 square P_n1
莫比乌斯梯形 M_n2+n-(-1)^n
棱柱图 Y_n(-1)^n+n+1
太阳图1
轮图 W_nn-1

另请参阅

Chvátal 定理, 狄拉克定理, 欧拉环, 欧拉图, Grinberg 公式, 哈密顿图, 哈密顿路径, 哈密顿遍历, Herschel 图, 二十面体游戏, Kozyrev-Grinberg 理论, 最长路径, 中间层猜想, 奥尔定理, Pósa 定理, 史密斯网络定理, 路径, 旅行商问题, 单笔画回路, 唯一哈密顿图

通过 Wolfram|Alpha 探索

参考文献

Angluin, D. 和 Valiant, L. "Probabilistic Algorithms for Hamiltonian Circuits and Matchings." J. Comput. Sys. Sci. 18, 155-190, 1979.Bermond, J.-C. "Hamiltonian Graphs." Ch. 6 in Selected Topics in Graph Theory (Ed. L. W. Beineke 和 R. J. Wilson). London: Academic Press, pp. 127-167, 1979.Bollobás, B. Graph Theory: An Introductory Course. New York: Springer-Verlag, p. 12, 1979.Chalaturnyk, A. "A Fast Algorithm for Finding Hamilton Cycles." Master's thesis. Winnipeg, Manitoba, Canada: University of Manitoba, 2008. ftp://www.combinatorialmath.ca/g&g/chalaturnykthesis.pdf.Chartrand, G. Introductory Graph Theory. New York: Dover, p. 68, 1985.Csehi, C. Gy. 和 Tóth, J. "Search for Hamiltonian Cycles." Mathematica J. 13, 2011. http://www.mathematica-journal.com/2011/05/search-for-hamiltonian-cycles/.Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150-156, May 1957.Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 96-97, 1984.Gardner, M. "The Binary Gray Code." In Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, pp. 23-24, 1986.Garey, M. R. 和 Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.Godsil, C. 和 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.Karp, R. M. "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations (Ed. R. E. Miller 和 J. W. Thatcher). New York: Plenum Press, pp. 85-103, 1972.Khomenko, N. P. 和 Golovko, L. D. "Identifying Certain Types of Parts of a Graph and Computing Their Number." Ukr. Math. J. 24, 313-321, 1972.Kocay, W. "An Extension of the Multi-Path Algorithm for Hamilton Cycles." Disc. Math. 101, 171-188, 1992.Kocay, W. 和 Li, B. "An Algorithm for Finding a Long Path in a Graph." Util. Math. 45, 169-185, 1994.Lederberg, J. "Hamilton Circuits of Convex Trivalent Polyhedra (up to 18 Vertices)." Amer. Math. Monthly 74, 522-527, 1967.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Ore, O. "A Note on Hamiltonian Circuits." Amer. Math. Monthly 67, 55, 1960.Perepechko, S. N. 和 Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."Rubin, F. "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21, 576-580, 1974.Skiena, S. "Hamiltonian Cycles." §5.3.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 196-198, 1990.Sloane, N. J. A. Sequences A003042/M2053, A005843/M0985, A006069/M1903, A007395/M0208, A094047, A124349, A124355, A124356, A129348, A129349, A143246, A143247, A143248, A174589, A222199, A280847, A281255, A301557, A306447, A307896, A307902in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "On Hamiltonian Circuits." J. London Math. Soc. 21, 98-101, 1946.Vandegriend, "B. Finding Hamiltonian Cycles: Algorithms, Graphs and Performance." Master's thesis, Winnipeg, Manitoba, Canada: University of Manitoba, 1998.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/HamiltonianCycle.html

学科分类