主題
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 定理, 史密斯網路定理, 路徑, 旅行商問題, 單筆畫迴路, 唯一哈密頓圖

透過 探索

參考文獻

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.

在 上被引用

哈密頓環

請引用為

Weisstein, Eric W. "哈密頓環。" 來自 Web 資源。 https://mathworld.tw/HamiltonianCycle.html

學科分類