FindEulerianCycle

FindEulerianCycle[g]
求图 g 中的欧拉圈.

FindEulerianCycle[g,k]
求至多 k 个欧拉圈.

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

更多信息更多信息

背景
背景

  • FindEulerianCycle 试图找出一个或多个不同的欧拉圈,也被称为图的欧拉环路,欧拉巡回或欧拉回路. 欧拉圈会作为边列表的列表返回,不存在时则返回 {}. 欧拉圈(若该圈被显式路径标明且路径由特定端点组成,则更适合被称为环路)是由不同边组成的一个连续序列,头尾两条边的端点是重合的且图的每条边都恰好出现一次. 欧拉圈可被用于重建基因组序列,构建 de Bruijin 序列,以及寻找最佳会议排期.
  • FindEulerianCycle[g,k] 试图找出 k 个欧拉圈,其中计数要求 k 可以被省略(在这种情况下它取值为 1),或者也可以设为 All. 欧拉圈不必是简单圈,即圈中可以有重复的顶点(不像哈密尔顿圈,它总是简单的).
  • 具有欧拉圈的图被称为欧拉图. 然而,这里需要谨慎的解释一下术语,因为有些作者把欧拉图定义为另一种东西,用来命名所有顶点都是偶数度的图. 后一定义是受欧拉的正确(但不是他证明的)观察启发,他注意到连通简单图有欧拉回路当且仅当没有一个顶点是奇数度的. 欧拉圈因此在数学上比哈密尔顿圈要容易研究些. 尽管连通情况下有 个结点的两种欧拉图数量是一样的,但不连通情况下数量就不一样了,因为存在不连通的图具有多个不连通的圈,它的每个结点都是偶数度的但没有单个的圈可以经过所有的边.
  • EulerianGraphQ 可被用于判定一个图是不是欧拉图. 寻找其它类型的圈的函数包括 FindCycleFindHamiltonianCycle.
2010年引入
(8.0)
| 2015年更新
(10.3)