主题
Search

哈密顿数

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

一个连通图 G 的哈密顿数 h(n) 是一个哈密顿通路 G 的长度。换句话说，它是图中闭合生成通路的最小长度。对于一个哈密顿图，h(G)=|G|，其中 |G| 是顶点数。因此，哈密顿数给出了一种衡量图与成为哈密顿图有多远的度量，并且一个哈密顿数 h(G)=n+1 的图被称为近哈密顿图。

Punnim等人 (2007) 表明

n<=h(G)<=2n-2,
(1)

当且仅当 G 是一个树时，h(G)=2n-2。由于一个树的哈密顿数为 2n-2，一个近哈密顿树必须满足 2n-2=n+1，得到 n=3。由于 3-路径图 P_3 是三个节点上唯一的树，它也是唯一的近哈密顿树。

一般来说，确定图的哈密顿数是困难的 (Lewis 2019)。

如果 G 是一个 k-连通图，具有 n 个顶点和直径 d，则

h(G)<=2(n-1)-|_k/2_|(2d-2)
(2)

(Goodman 和 Hedetniemi 1974, Lewis 2019)。

如果 G 是一个具有 n 个顶点的近哈密顿三次图，则三角形替换图 G^* 的哈密顿数为

h(G^*)=3n+2
(3)

(Punnim等人 2007)。

下表总结了特殊类别的（非哈密顿）图的值，其中 n 表示图的顶点数

图 Gh(G)
n-哑铃图2(n+1)
完全k-部图 K_(k_1,k_2,...,k_n){k_1+k_2+...k_n for n=1 or k_1+k_2+...+k_n>=max(k_1,...,k_n); 2max(k_1,...,k_n) otherwise
广义 Petersen 图 GP(k,m){2k+1 for k=5 (mod 6) and m=2; 2k otherwise
哈密顿图n
(k,m,l)-皮划艇桨图k+m+2l
(m,n)-棒棒糖图m+2n
(m,n)-蝌蚪图m+2n
树2n-2

参见

近哈密顿图, 图的周长, 哈密顿图, 哈密顿通路

使用 Wolfram|Alpha 探索

参考文献

Chartrand, G.; Thomas, T.; Saenpholphat, V.; 和 Zhang, P. "A New Look at Hamiltonian Walks." Bull. Inst. Combin. Appl. 42, 37-52, 2004.Goodman, S. E. 和 Hedetniemi, S. T. "On Hamiltonian Walks in Graphs." In Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory and Computing. Held at Florida Atlantic University, Boca Raton, Fla., March 5-8, 1973 (Ed. F. Hoffman, R. B. Levow, and R. S. D. Thomas). Winnipeg, Manitoba: Utilitas Mathematica, pp. 335-342, 1973.Goodman, S. E. 和 Hedetniemi, S. T. "On Hamiltonian Walks in Graphs." SIAM J. Comput. 3, 214-221, 1974.Lewis, T. M. "On the Hamiltonian Number of a Plane Graph." Disc. Math. Graph Th. 39, 171-181, 2019.Punnim, N.; Saenpholphat, V.; 和 Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security 7, 83-86, 2007.Punnim, N. 和 Thaithae, S. "The Hamiltonian Number of Some Classes of Cubic Graphs." East-West J. Math. 12, 17-26, 2010.Thaithae, S. 和 Punnim, N. "The Hamiltonian Number of Graphs with Prescribed Connectivity." Ars Combin. 90, 237-244, 2009.Thaithae, S. 和 Punnim, N. "The Hamiltonian Number of Cubic Graphs." In Computational geometry and graph theory: Revised selected papers from the International Conference (Kyoto CGGT 2007) held at Kyoto University, Kyoto, June 11-15, 2007 (Ed. H. Ito, M. Kano, N. Katoh and Y. Uno). Berlin: Springer, pp. 213-233, 2008.

引用此页

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

主题分类