FindHamiltonianCycle
更多信息和选项
- 一个哈密顿圈对每个顶点恰好遍历一次.
- FindHamiltonianCycle 返回由哈密顿圈组成的路径的列表.
- 如果不存在哈密顿圈则 FindHamiltonianCycle 返回列表 {}.
- FindHamiltonianCycle[g] 等价于 FindHamiltonianCycle[g,1].
- FindHamiltonianCycle[g,All] 求图 g 中的所有哈密顿圈.
- FindHamiltonianCycle 可用于无向图、有向图、多重图和混合图.
背景
- FindHamiltonianCycle 试图找出一个或多个不同的哈密顿圈,也被称为哈密顿环路,哈密顿巡回或哈密顿回路. 哈密顿圈会以边列表的列表形式返回,不存在时则返回 {}. 哈密顿圈(若该圈被显式路径标明且路径由特定端点组成,则更适合被称为哈密顿环路)是由不同边组成的一个连续序列,头尾两条边的端点是重合的且图的每个顶点都恰好出现一次. 哈密顿圈因此是长度为
的图圈,其中
是图结点的数量. 哈密顿圈被用于重建基因组序列,求解一些游戏(最明显的是 Icosian 游戏),找出国际象棋棋盘上的骑士巡逻路线,以及寻找正则图的有吸引力的环形嵌入. 具有哈密顿圈的图被称为哈密顿图. - FindHamiltonianCycle[g,k] 试图找出 k 个哈密顿圈,其中计数要求 k 可以被省略(在这种情况下它的取值为 1),可以是一个正整数,或者可以是 All.
- 寻找哈密顿圈是个 NP 完全问题. 然而,有许多启发式算法有时(但并不总是)可以很快的找到哈密顿圈. 出于这个原因,简单的重排图中的顶点可能会让 FindHamiltonianCycle 有不同的运行时间.
- 可以用 HamiltonianGraphQ 来检测一个图是不是哈密顿的. FindShortestTour 是另一个试图找出图上单个哈密顿圈(或更一般的指定的一组点)的函数,它的优点是有时它运行得比 FindHamiltonianCycle 更快.
个结点的图的哈密顿圈对应的是长度为
的圈,而任意长度的圈可以用 FindCycle 寻找. 哈密顿圈访问所有的顶点,但未必要经过每一条边. 访问所有边恰好一次的圈被称为欧拉圈并可用 FindEulerianCycle 寻找.
范例
打开所有单元 关闭所有单元基本范例 (2)
范围 (8)
FindHamiltonianCycle 可用于无向图:
FindHamiltonianCycle[[image]]FindHamiltonianCycle[[image]]FindHamiltonianCycle[[image]]FindHamiltonianCycle[[image]]FindHamiltonianCycle[[image], 2]FindHamiltonianCycle[{1 -> 2, 2 -> 3, 3 -> 1, 1 -> 3, 3 -> 4, 4 -> 1}]对非哈密顿图 FindHamiltonianCycle 返回空结果:
FindHamiltonianCycle[[image]]FindHamiltonianCycle 可用于大规模图:
g = CompleteGraph[10000];FindHamiltonianCycle[g] //Length// Timing应用 (5)
求解 Icosian 游戏问题 [MathWorld],即求沿着十二面体的边的哈密顿圈:
{g = PolyhedronData["Dodecahedron", "Skeleton"], Graphics3D[{Opacity[.8], PolyhedronData["Dodecahedron", "GraphicsComplex"]}]}h = PathGraph@First[FindHamiltonianCycle[g]];{HighlightGraph[g, h, GraphHighlightStyle -> "Thick"], Graphics3D[{Opacity[.8], PolyhedronData["Dodecahedron", "GraphicsComplex"], Red, Tube[PolyhedronData["Dodecahedron", "Vertices"][[Append[VertexList[h], VertexList[h][[1]]]]], 0.1]}]}g = [image];StringJoin /@ Map[First, FindHamiltonianCycle[g, All], {2}]Flatten[StringCases[%, __ ~~ ("BCPNM" | "MNPCB" ) ~~ __ ]]Map[HighlightGraph[g, PathGraph[Characters[#]], GraphHighlightStyle -> "Thick"]&, %]求骑士棋子访问 8×8 的棋盘的每一方格恰好一次的移动序列:
g = KnightTourGraph[8, 8];cycle = First[FindHamiltonianCycle[g]]checkerboard = ArrayPlot[Table[Mod[j + i, 2], {i, 8}, {j, 8}], ColorRules -> {1 -> RGBColor[0, .55, .77], 0 -> RGBColor[.67, .9, .99]}, Frame -> False, DataRange -> {{1, 8}, {1, 8}}];Show[{checkerboard, HighlightGraph[g, PathGraph[cycle], GraphHighlightStyle -> "DehighlightHide", EdgeStyle -> Directive[Thick, Red]]}]圆形基因组 "ATGGCGTGCA" 的基于图的集合,棋子顶点为 k-mer,边成对对齐:
threeMers = StringJoin /@ Partition[Characters["ATGGCGTGCA"], 3, 1, 1]edges = Flatten[Table[StringCases[threeMers, x : (StringDrop[e, 1] ~~ _) :> ex], {e, threeMers}]]Graph[threeMers, edges, GraphLayout -> "CircularEmbedding", PlotTheme -> "DiagramGold"]FindHamiltonianCycle [%]//FirstStringJoin[StringTake[First /@ %, 1]]graycode3 = With[{n = 3}, Table[IntegerString[BitXor[BitShiftRight[i], i], 2, n]
, {i, 0, 2 ^ n - 1}]]Subscript[𝒬, 3] = VertexReplace[HypercubeGraph[3, VertexShapeFunction -> "Name"], Table[i + 1 -> IntegerString[i, 2, 3], {i, 0, 7}]]Map[First, FindHamiltonianCycle[Subscript[𝒬, 3], All], {2}]MemberQ[%, graycode3]HighlightGraph[Subscript[𝒬, 3], PathGraph[graycode3]]属性和关系 (5)
对由大量哈密顿图组成的集合使用 GraphData:
Short[GraphData["Hamiltonian"]]Short[GraphData["Nonhamiltonian"]]通过使用 HamiltonianGraphQ 测试图是否有哈密顿圈:
GraphData[{"DutchWindmill", {4, 4}}]HamiltonianGraphQ[%]g = GraphData["Foster038A"]FindHamiltonianCycle[g]CompleteGraph[4]{HamiltonianGraphQ[%], FindHamiltonianCycle[LineGraph[%]]}g = Graph[{12, 23, 31, 34, 45, 53}]{EulerianGraphQ[%], FindHamiltonianCycle[LineGraph[g]]}g = [image];{Min[VertexDegree[g]] > VertexCount[g] / 2, FindHamiltonianCycle[g]}g = [image];{Min[VertexDegree[g]] > VertexCount[g], FindHamiltonianCycle[g]}巧妙范例 (1)
g = PolyhedronData["Dodecahedron", "Skeleton"];Shallow[cycle = First[FindHamiltonianCycle[g]]]color[cycles_] := {cycles, cycles[[All, 1]], Style[cycles[[-1, 2]], Yellow]}Dynamic[HighlightGraph[g, color[cycle[[1 ;; Clock[{1, Length[cycle], 1}, 40]]]]]]文本
Wolfram Research (2010),FindHamiltonianCycle,Wolfram 语言函数,https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html (更新于 2015 年).
CMS
Wolfram 语言. 2010. "FindHamiltonianCycle." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2015. https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html.
APA
Wolfram 语言. (2010). FindHamiltonianCycle. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html 年
BibTeX
@misc{reference.wolfram_2026_findhamiltoniancycle, author="Wolfram Research", title="{FindHamiltonianCycle}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html}", note=[Accessed: 16-November-2026]}
BibLaTeX
@online{reference.wolfram_2026_findhamiltoniancycle, organization={Wolfram Research}, title={FindHamiltonianCycle}, year={2015}, url={https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html}, note=[Accessed: 16-November-2026]}