主题
Search

哈密顿图

下载 Mathematica 笔记本下载 Wolfram 笔记本
HamiltonianGraphs

哈密顿图，也称为汉密尔顿图，是图，它具有哈密顿环。不是哈密顿图的图被称为非哈密顿图。

一个有 n 个节点的哈密顿图的图周长为 n。

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

虽然很容易对“哈密顿”做一个通用定义，即考虑单例图 K_1 是哈密顿图或非哈密顿图，但将“哈密顿”定义为“具有哈密顿环”，并将“哈密顿环”视为一般“环”的子集，将导致单例图是非哈密顿图的约定（B. McKay，私人通讯，2006 年 10 月 11 日）。然而，按照惯例，单例图通常被认为是哈密顿图（B. McKay，私人通讯，2007 年 3 月 22 日）。这项工作和GraphData中的约定是 K_1 是哈密顿图，而 K_2=P_2 是非哈密顿图。

对于 n 个节点的简单哈密顿图的数量，对于 n=1, 2, ...，由 1, 0, 1, 3, 8, 48, 383, 6196, 177083, ... 给出 (OEIS A003216)。

可以使用 Wolfram 语言 测试图是否是哈密顿图，使用HamiltonianGraphQ[g].

测试图是否是哈密顿图是一个 NP 完全问题（Skiena 1990, p. 196）。Rubin (1974) 描述了一种高效的搜索程序，可以使用演绎法在图中找到一些或所有哈密顿路径和环路，从而大大减少回溯和猜测。

所有哈密顿图都是双连通的，尽管反之不然（Skiena 1990, p. 197）。任何具有不平衡顶点奇偶性的二分图都不是哈密顿图。

如果图 G 中所有非相邻顶点的度数之和对于所有非相邻顶点的子集都大于节点数 n，则 G 是哈密顿图 (Ore 1960; Skiena 1990, p. 197)。

所有平面 4 连通图都具有哈密顿环，但并非所有多面体图都如此。例如，最小的非哈密顿多面体图是具有 11 个节点的Herschel 图。

HamiltonianTetrahedron
HamiltonianOctahedron
HamiltonianCube
HamiltonianDodecahedron
HamiltonianIcosahedron
HamiltonianPlatonicCycles

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

HamiltonianArchimedean

虽然 Gardner (1957) 没有明确说明，但所有阿基米德立体也都有哈密顿环路，其中一些如上图所示。然而，阿基米德对偶的骨架（即阿基米德对偶图）不一定是哈密顿图，正如 Coxeter (1946) 和 Rosenthal (1946) 对菱形十二面体 (Gardner 1984, p. 98) 所证明的那样。

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

另请参阅

近似哈密顿图, 阿基米德对偶图, 阿基米德图, Barnette 猜想, 双三次图, Chvátal 定理, 循环图, 欧拉图, 哈密顿环, 哈密顿连通图, 哈密顿路径, 哈密顿行走, Herschel 图, 次哈密顿图, 次可追踪图, 二十面体游戏, 最长路径, Meredith 图, 非哈密顿图, 非哈密顿顶点传递图, Ore 图, Tait 哈密顿图猜想, 可追踪图, 旅行商问题, Tutte 猜想, 唯一哈密顿图

使用 Wolfram|Alpha 探索

参考资料

Bermond, J.-C. "Hamiltonian Graphs." 第 6 章，出自 Selected Topics in Graph Theory （L. W. Beineke 和 R. J. Wilson 编辑）。伦敦：Academic Press，第 127-167 页，1979 年。Bollobás, B. Graph Theory: An Introductory Course. 纽约：Springer-Verlag，第 12 页，1979 年。Chartrand, G. Introductory Graph Theory. 纽约：Dover，第 68 页，1985 年。Chartrand, G.; Kapoor, S. F.; 和 Kronk, H. V. "The Many Facets of Hamiltonian Graphs." Math. Student 41, 327-336, 1973.Coxeter, H. S. M. "Problem E 711." Amer. Math. Monthly 53, 156, 1946.Dolch, J. P. "Names of Hamiltonian Graphs." 出自 4th S-E Conf. Combin., Graph Theory, Computing. Congress. Numer. 8, 259-271, 1973.Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150-156, 1957 年 5 月。Gardner, M. The Sixth Book of Mathematical Games from Scientific American. 芝加哥，伊利诺伊州：University of Chicago Press，第 96-97 页，1984 年。Godsil, C. 和 Royle, G. "Hamilton Paths and Cycles." C§3.6 出自 Algebraic Graph Theory. 纽约：Springer-Verlag，第 45-47 页，2001 年。Gould, R. J. "Updating the Hamiltonian Problem--A Survey." J. Graph Th. 15, 121-157, 1991.Hamilton, W. R. Quart. J. Math., 5, 305, 1862.Hamilton, W. R. Philos. Mag. 17, 42, 1884.Harary, F. Graph Theory. 雷丁，马萨诸塞州：Addison-Wesley，第 4 页，1994 年。Harary, F. 和 Palmer, E. M. Graphical Enumeration. 纽约：Academic Press，第 219 页，1973 年。Herschel, A. S. "Sir Wm. Hamilton's Icosian Game." Quart. J. Pure Applied Math. 5, 305, 1862.Lucas, E. Récréations mathématiques, Vol. 2. 巴黎：Gauthier-Villars，第 201 页和 208-255 页，1891 年。Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." 美国数学会通报 74, 583-592, 2024.Ore, O. "A Note on Hamiltonian Circuits." Amer. Math. Monthly 67, 55, 1960.Rosenthal, A. "问题 E 711 的解答：威廉·哈密顿爵士的二十面体游戏。" Amer. Math. Monthly 53, 593, 1946.Rubin, F. "A Search Procedure for Hamilton Paths and Circuits." 美国计算机协会杂志 21, 576-580, 1974.Skiena, S. "Hamiltonian Cycles." 第 5.3.4 节，出自 Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. 雷丁，马萨诸塞州：Addison-Wesley，第 196-198 页，1990 年。Sloane, N. J. A. 序列 A003216/M2764 出自 "整数序列在线百科全书"。

在 Wolfram|Alpha 中被引用

哈密顿图

引用为

Weisstein, Eric W. "哈密顿图。" 出自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/HamiltonianGraph.html

主题分类