FindHamiltonianCycle

FindHamiltonianCycle[g]

求图 g 中的哈密顿圈.

FindHamiltonianCycle[g,k]

求至多 k 个哈密顿圈.

FindHamiltonianCycle[{vw,…},…]

使用规则 vw 指定图 g.

更多信息和选项

背景

  • FindHamiltonianCycle 试图找出一个或多个不同的哈密顿圈，也被称为哈密顿环路，哈密顿巡回或哈密顿回路. 哈密顿圈会以边列表的列表形式返回，不存在时则返回 {}. 哈密顿圈（若该圈被显式路径标明且路径由特定端点组成，则更适合被称为哈密顿环路）是由不同边组成的一个连续序列，头尾两条边的端点是重合的且图的每个顶点都恰好出现一次. 哈密顿圈因此是长度为 的图圈，其中 是图结点的数量. 哈密顿圈被用于重建基因组序列，求解一些游戏（最明显的是 Icosian 游戏），找出国际象棋棋盘上的骑士巡逻路线，以及寻找正则图的有吸引力的环形嵌入. 具有哈密顿圈的图被称为哈密顿图.
  • FindHamiltonianCycle[g,k] 试图找出 k 个哈密顿圈，其中计数要求 k 可以被省略（在这种情况下它的取值为 1），可以是一个正整数，或者可以是 All.
  • 寻找哈密顿圈是个 NP 完全问题. 然而，有许多启发式算法有时（但并不总是）可以很快的找到哈密顿圈. 出于这个原因，简单的重排图中的顶点可能会让 FindHamiltonianCycle 有不同的运行时间.
  • 可以用 HamiltonianGraphQ 来检测一个图是不是哈密顿的. FindShortestTour 是另一个试图找出图上单个哈密顿圈（或更一般的指定的一组点）的函数，它的优点是有时它运行得比 FindHamiltonianCycle 更快.
  • 个结点的图的哈密顿圈对应的是长度为 的圈，而任意长度的圈可以用 FindCycle 寻找. 哈密顿圈访问所有的顶点，但未必要经过每一条边. 访问所有边恰好一次的圈被称为欧拉圈并可用 FindEulerianCycle 寻找.

范例

打开所有单元关闭所有单元

基本范例  (2)

求哈密顿圈：

显示该圈：

求若干个哈密顿圈：

范围  (8)

FindHamiltonianCycle 可用于无向图：

有向图：

多重图：

混合图：

求若干哈密顿圈：

使用规则指定图：

对非哈密顿图 FindHamiltonianCycle 返回空结果：

FindHamiltonianCycle 可用于大规模图：

应用  (5)

求解 Icosian 游戏问题 [MathWorld]，即求沿着十二面体的边的哈密顿圈：

在一个带标签的十二面体上，求包含给定标签序列的哈密顿圈：

获取包含序列 B、C、P、N、M 的圈：

突出显示圈：

求骑士棋子访问 8×8 的棋盘的每一方格恰好一次的移动序列：

一条闭合的骑士巡回路线：

圆形基因组 "ATGGCGTGCA" 的基于图的集合，棋子顶点为 k-mer，边成对对齐：

重建基因组：

阶的格雷码是超立方图 的哈密顿圈：

求 的全部哈密顿圈：

突出显示格雷码：

属性和关系  (5)

对由大量哈密顿图组成的集合使用 GraphData：

非哈密顿图：

通过使用 HamiltonianGraphQ 测试图是否有哈密顿圈：

哈密顿图是双向连接的：

哈密顿图的线图具有一个哈密顿圈：

欧拉图的线图具有哈密顿圈：

具有 个顶点和最小度大于 的无向图具有哈密顿圈：

具有 个顶点和最小度大于 的有向图具有哈密顿圈：

巧妙范例  (1)

求哈密顿圈：

动态突出显示圈：

Wolfram Research (2010)，FindHamiltonianCycle，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html （更新于 2015 年）.

文本

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_2024_findhamiltoniancycle, author="Wolfram Research", title="{FindHamiltonianCycle}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findhamiltoniancycle, organization={Wolfram Research}, title={FindHamiltonianCycle}, year={2015}, url={https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html}, note=[Accessed: 18-November-2024 ]}