主題
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

參見

近哈密頓圖, 圖的周長, 哈密頓圖, 哈密頓通路

使用 探索

參考文獻

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. "哈密頓數。" 來自 Web 資源。 https://mathworld.tw/HamiltonianNumber.html

主題分類