主題
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 猜想, 唯一哈密頓圖

使用 探索

參考資料

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 出自 "整數序列線上百科全書"。

在 中被引用

哈密頓圖

引用為

Weisstein, Eric W. "哈密頓圖。" 出自 —— 資源。 https://mathworld.tw/HamiltonianGraph.html

主題分類