FindHamiltonianCycle

FindHamiltonianCycle[g]
求图 g 中的哈密顿圈.

FindHamiltonianCycle[g,k]
求至多 k 个哈密顿圈.

FindHamiltonianCycle[{vw,},]
使用规则 指定图 g.

更多信息和选项更多信息和选项

背景
背景

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