Wolfram 语言与系统参考资料中心

FindEulerianCycle

FindEulerianCycle[g]

求图 g 中的欧拉圈.

FindEulerianCycle[g,k]

求至多 k 个欧拉圈.

FindEulerianCycle[{vw,…},…]

使用规则 vw 指定图 g.

背景

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

范例

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

基本范例 (2)

求欧拉圈：

Wolfram Language code: g = GraphData["OctahedralGraph"];

Wolfram Language code: FindEulerianCycle[g]

显示欧拉圈：

Wolfram Language code: Table[HighlightGraph[g, Part[First[%], 1 ;; i]], {i, Length[First[%]]}]

求若干个欧拉圈：

Wolfram Language code: FindEulerianCycle[GraphData["ButterflyGraph"], 2]

范围 (8)

FindEulerianCycle 可用于无向图：

Wolfram Language code: FindEulerianCycle[[image]]

有向图：

Wolfram Language code: FindEulerianCycle[[image]]

多重图：

Wolfram Language code: FindEulerianCycle[[image]]

求若干个欧拉圈：

Wolfram Language code: FindEulerianCycle[[image], 2]

求所有的欧拉圈：

Wolfram Language code: FindEulerianCycle[[image], All]//Length

使用规则指定图：

Wolfram Language code: FindEulerianCycle[{1 -> 2, 2 -> 3, 3 -> 1, 1 -> 3, 3 -> 4, 4 -> 1}]

FindEulerianCycle 对于非欧拉图返回空结果：

Wolfram Language code: FindEulerianCycle[[image]]

FindEulerianCycle 可用于大规模图：

Wolfram Language code: g = HypercubeGraph[14];

Wolfram Language code: EdgeCount[g]

Wolfram Language code: FindEulerianCycle[g]//Short//Timing

应用 (7)

普雷格尔河上柯尼斯堡市的七座桥不能无重复的由单条路径遍历，尤其还要求在和起点相同的地方结束行程：

Wolfram Language code: graph = \!\(\*GraphicsBox[«6»]\);

Wolfram Language code: FindEulerianCycle[graph]

描绘出一个信封的图案，并且无需抬起钢笔，无需两次划过同一条线：

Wolfram Language code: g = [image];

该图不是欧拉图：

Wolfram Language code: EulerianGraphQ[g]

由于存在两个度数为奇数的顶点，通过经由一个新的顶点（以避免多重边）连接度数为奇数的顶点，可构建增广欧拉图：

Wolfram Language code: {s, t} = Pick[VertexList[g], OddQ /@ VertexDegree[g]]

Wolfram Language code:

h = Graph[Append[VertexList[g], "z"], Join[EdgeList[g], {t"z", "z"s}], VertexCoordinates -> Append[GraphEmbedding[g], {0., -0.8}], VertexSize -> Tiny, EdgeStyle -> {Dashed, t"z" -> Green, "z"s -> Green}]

Wolfram Language code: EulerianGraphQ[h]

在增广图中，找到一个欧拉圈：

Wolfram Language code: FindEulerianCycle[h]//First

对回路内的边进行轮转，直到含有顶点的边成为最后的几条边：

Wolfram Language code: NestWhile[Append[#[[2 ;; ]], #[[1]]]&, %, Not[MemberQ[List@@#[[-2]], "z"]] || Not[MemberQ[List@@#[[-1]], "z"]]&]

显示欧拉路径：

Wolfram Language code:

Table[HighlightGraph[g, Append[Style[#, Directive[StandardGray, Dashing[{}]]]& /@ %[[ ;; i - 1]], Style[%[[i]], Directive[Red, Dashing[{}]]]]], {i, Length[%] - 2}]

求以下会议的会议室的最佳安排：

由参加者组成的图，其中的边连接参加相同会议的参加者：

Wolfram Language code: g = [image];

没有最优的会议安排，能使得连续的两次会议共享一个参加者：

Wolfram Language code: FindEulerianCycle[g]

在具有奇数会议次数的参加者之间添加虚拟会议：

Wolfram Language code: h = EdgeAdd[g, "Michael""William"];

Wolfram Language code: First[FindEulerianCycle[h]]

一种可能的安排：

Wolfram Language code: TableForm[Apply[List, Rest[%], {1}], TableHeadings -> {Table[i, {i, 10}], None} ]

由圆形基因组 "ATGGCGTGCA" 组成的基于图的组合，其中顶点作为 (k-1) 部，而边作为 k 部：

Wolfram Language code: threeMers = StringJoin /@ Partition[Characters["ATGGCGTGCA"], 3, 1, 1]

Wolfram Language code: edges = DirectedEdge[StringDrop[#, -1], StringDrop[#, 1]]& /@ threeMers

Wolfram Language code: Graph[edges, GraphLayout -> "CircularEmbedding", PlotTheme -> "DiagramGold"]

重建基因组：

Wolfram Language code: FindEulerianCycle [%]//First

Wolfram Language code: StringJoin[StringTake[First /@ %, 1]]

从欧拉圈构建 k 重 de Bruijn 序列：

Wolfram Language code: g = DeBruijnGraph[2, 3]

Wolfram Language code: cycle = First[FindEulerianCycle[g]]

De Bruijn 序列：

Wolfram Language code: First[IntegerDigits[# - 1, 2, 3]]& /@ cycle[[All, 1]]

求沿着有向圈的顶点顺序：

Wolfram Language code: Graph[{12, 23, 31, 34, 45, 53, 55}]

Wolfram Language code: FindEulerianCycle [%]//First

挑出每条边的起始顶点：

Wolfram Language code: First /@ %

求荷兰风车图的欧拉圈：

Wolfram Language code: g = GraphData[{"DutchWindmill", {3, 4}}];

Wolfram Language code: edges = First[FindEulerianCycle[g]]

沿着欧拉圈对边添加标签：

Wolfram Language code: HighlightGraph[g, Table[Labeled[edges[[i]], i], {i, Length[edges]}]]

属性和关系 (6)

对大量欧拉图集合使用 GraphData：

Wolfram Language code: Short[GraphData["Eulerian"]]

非欧拉图：

Wolfram Language code: Short[GraphData["Noneulerian"]]

利用 EulerianGraphQ 检验一个图是否含有欧拉圈：

Wolfram Language code: GraphData[{"DutchWindmill", {2, 4}}]

Wolfram Language code: EulerianGraphQ[%]

一个顶点都是偶数度的连通无向图才含有欧拉圈：

Wolfram Language code: g = GraphData[{"Antiprism", 4}]

Wolfram Language code: VertexDegree[g]

Wolfram Language code: FindEulerianCycle[g]

如果一个无向图可以被分解为边互不相交的圈，则该图含有欧拉圈：

Wolfram Language code: g = Graph[{12, 23, 31, 34, 45, 53}]

Wolfram Language code: Subgraph[g, #]& /@ {{1, 2, 3}, {3, 4, 5}}

一个无向欧拉图的线图含有欧拉圈：

Wolfram Language code: g = CompleteGraph[{2, 4}]

Wolfram Language code: {EulerianGraphQ[g], FindEulerianCycle[LineGraph[g]]}

当且仅当每个顶点具有相等的入度和出度时，一个有向图才含有欧拉圈：

Wolfram Language code: g = Graph[{12, 23, 31, 34, 41, 13}]

Wolfram Language code: {ConnectedGraphQ[g], VertexInDegree[g] == VertexOutDegree[g]}

Wolfram Language code: FindEulerianCycle[g]

巧妙范例 (1)

求欧拉圈：

Wolfram Language code: g = [image];

Wolfram Language code: Shallow[cycle = First[FindEulerianCycle[g]]]

动态突出显示圈：

Wolfram Language code: color[cycles_] := {cycles, cycles[[All, 1]], Style[cycles[[-1, 2]], Yellow]}

Wolfram Language code: Dynamic[HighlightGraph[g, color[cycle[[1 ;; Clock[{1, Length[cycle], 1}, 40]]]]]]

Top

更多学习资源

技术支持

数据科学、金融与商业

工程

科学与技术

教育科技

教育举措

开始

提高你的技能

与我们合作

成人教育计划

青少年教育计划

欢迎阅读

FindEulerianCycle

更多信息

背景

范例

基本范例 (2)

范围 (8)

应用 (7)

属性和关系 (6)

巧妙范例 (1)

文本

CMS

APA

BibTeX

BibLaTeX

FindEulerianCycle

更多信息

背景

范例

基本范例 (2)

范围 (8)

应用 (7)

属性和关系 (6)

巧妙范例 (1)

参见

相关指南

历史

文本

CMS

APA

BibTeX

BibLaTeX