環 (圖論)

有向回路

图论中，环是只有首末顶点重复的非空路徑。没有环的图称作无环图，没有有向环的有向图称为有向无环图；无环连通图称作树。

定义

回路，环

• 回路是一条非空的路径， 其中首末顶点顶点是同一点。令图$G=(V,E,\varnothing )$，回路是非空路径$(e_{1},e_{2},\ldots ,e_{n})$，其顶点序列为$(v_{1},v_{2},\ldots ,v_{n},v_{1})$
• 环路或简单回路是只有首末顶点相同的回路。
• 回路和环的长度是经过的边数。

有向回路，有向环路

• 有向回路是非空的有向路径，其首末顶点相同。令有向图$G=(V,E,\varnothing )$，回路是非空有向路径$(e_{1},e_{2},\ldots ,e_{n})$，其顶点序列为$(v_{1},v_{2},\ldots ,v_{n},v_{1})$。
• 有向环路或简单有向回路，是只有首末顶点重复的有向回路。

无弦环

若环上任意两顶点都不会被不属于环的边相连，则称之为图中的无弦环或洞，其补称作反洞（antihole）。无弦环可用于刻画完美图：根据强完美图定理，图是完美图的充要条件是其不存在顶点数为奇数的洞或反洞。弦图是一种特殊的完美图，其不存在顶点数大于等于3的无弦环。

图的围长是图中最短环的长度。由此，最短环一定是无弦的。笼是给定围长和度后最小的正则图。

边环是图上具有一些特殊性质的环：连接任意两个不在环上的顶点的路径必须经过这个环上的顶点。若图不是由环加一条边构成的，则边环一定是导出环。

环空间

“环”也可指图的环空间的元素。有很多环空间，每个系数域或环都有一个。最常见的是二元环空间（常简称为“环空间”），由每个顶点具有偶数度的边集组成；其在2元素有限域上形成了向量空间。据维布伦定理，环空间的每个元素都可由简单环的边不交并形成。图的环基是形成环空间的基的简单环集合。

利用代数拓扑的思想，二元循环空间可推广到其他环（如整数、有理数或实数环等等）上的向量空间或模。

在图上探测环

有向图和无向图上的环可用深度优先搜索（DFS）探测：寻找一条连接当前顶点与之前顶点的边（它包含了一条后向边）。DFS跳过的所有后向边都属于某个环。无向图上，指向父节点的边不能算作后向边，但找到已经过的顶点意味着后向边的存在。找到n阶无向图上的环只需要O(n)时间。

许多拓扑排序算法也要探测环，因为它们将是拓扑排序的障碍。另外，若有向图被分为几个强连通分量，那么环只会存在于这些分量内，而不会连接，因为环本身就是强连接的。

对有向图，还可使用基于分布式信息的算法。其思路是，从一个顶点发出的信息可通过环回到这个顶点。分布式环检测算法十分适于在计算机集群上用分布式图处理系统来处理大规模的图。

环检测的应用如用wait-for graph检测并行系统的死锁。

算法

上述用深度优先搜索查找循环的方法可描述为：

For every vertex v: visited(v) = finished(v) = false
For every vertex v: DFS(v)

其中

DFS(v) =
  if finished(v): return
  if visited(v):
    "Cycle found"
    return
  visited(v) = true
  for every neighbour w: DFS(w)
  finished(v) = true

对于无向图，“邻接”指与v相连的所有顶点，递归调用DFS(v)的除外。这种省略可避免算法找到形如v→w→v的平凡环，其存在于所有有多条边的无向图中。

用广度优先搜索的变体将找到长度尽可能小的环。

用环覆盖图

1736年，欧拉在关于柯尼斯堡七桥问题的论文中证明，要使有限无向图中的闭合走法能精确访问每条边（使其成为闭合轨迹）一次，必须同时满足：除孤立顶点外是连通的（即所有边都包含在一个分量中），同时每个点的度都是偶数。而对有向图，存在闭漫游（closed walk）不重复地经过每条边的充要条件是：图是强连接的，且每个顶点出入度相等。在这两个情况下，环或漫游称作欧拉环。对有限无向图（无论连通），若其每个顶点的度都是偶数，则可以找到一组简单的环不重复地覆盖每一条边，这就是维布伦定理。即使连通图不满足欧拉定理的条件，仍可以在多项式时间内通过解邮递员问题，找到长度最短的闭漫游，经过每一条边至少一次。

在图上找到不重复地过每个顶点的简单环，要更加困难，这样的环是哈密顿环，确定图上是否存在哈密顿环是NP完全问题。很多研究已经找到了一些种类的图，其上一定能找到哈密顿环。例如奧爾定理：若图上每对不相邻顶点的度之和大于等于图的阶数，则图中有哈密顿环。

循环双覆盖猜想可表述为：对无桥图，存在由简单环组成的多重集，使它们一起能覆盖每条边恰好两次。目前这个猜想仍未证明或证伪。

由环刻画的图类别

有一些重要的图的类型可以被环来刻画和定义。它们包括：

• 二分图，不存在奇数长的环的图
• 仙人掌圖，a graph in which every nontrivial biconnected component is a cycle
• 环图，一个环组成的图
• 弦圖，不存在长度大于3的导出环（induced cycle）的图
• 有向无环图，a directed graph with no cycles
• 线完美图，每一个奇数长度的简单环都是一个三角形
• 完美图，不存在长度大于3的洞(hole)或反洞(antihole)
• Pseudoforest，a graph in which each connected component has at most one cycle
• 绞窄图，a graph in which every peripheral cycle is a triangle
• 强连通图，一个有向图，其中每一条边都是环的一部分
• 無三角形圖，a graph without three-vertex cycles

參見

• 环空间
• 環基
• 迭代函数值序列中的环探测