查看“︁環 (圖論)”︁的源代码

[[File:Directed_cycle.svg|thumb|right|有向回路]]
[[图论]]中，'''环'''是只有首末顶点重复的非空[[道路 (图论)|路徑]]。没有环的图称作无环图，没有有向环的有向图称为[[有向无环图]]；无环连通图称作[[树 (图论)|树]]。

== 定义 ==
=== 回路，环 ===
* '''回路'''是一条非空的路径， 其中首末[[顶点 (图论)|顶点]]顶点是同一点。令图<math>G = (V, E, \varnothing)</math>，回路是非空路径<math>(e_1, e_2, \ldots, e_n)</math>，其顶点序列为<math>(v_1, v_2, \ldots, v_n, v_1)</math>
*'''环路'''或'''简单回路'''是只有首末顶点相同的回路。
*回路和环的'''长度'''是经过的边数。

=== 有向回路，有向环路 ===
* '''有向回路'''是非空的有向路径，其首末顶点相同。令有向图<math>G=(V,E,\varnothing)</math>，回路是非空有向路径<math>(e_1, e_2, \ldots, e_n)</math>，其顶点序列为<math>(v_1, v_2, \ldots, v_n, v_1)</math>。
* '''有向环路'''或'''简单有向回路'''，是只有首末顶点重复的有向回路。

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

图的[[圍長 (圖論)|围长]]是图中最短环的长度。由此，最短环一定是无弦的。{{le|籠 (圖論)|Cage (graph theory)|笼}}是给定围长和度后最小的[[正则图]]。

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

==环空间==
“环”也可指图的{{le|环空间|cycle space}}的元素。有很多环空间，每个系数域或环都有一个。最常见的是''二元环空间''（常简称为“环空间”），由每个顶点具有偶数度的边集组成；其在2元素[[有限域]]上形成了[[向量空间]]。据{{le|维布伦定理|Veblen's theorem}}，环空间的每个元素都可由简单环的边不交并形成。图的{{le|环基|cycle basis}}是形成环空间的[[基 (线性代数)|基]]的简单环集合。<ref name="gy">{{citation|title=Graph Theory and Its Applications|edition=2nd|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press|year=2005|isbn=9781584885054|chapter=4.6 Graphs and Vector Spaces|pages=197–207|chapter-url=https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197|access-date=2016-09-27|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204155009/https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197|url-status=live}}.</ref>

利用[[代数拓扑]]的思想，二元循环空间可推广到其他[[环 (代数)|环]]（如整数、有理数或实数环等等）上的向量空间或[[模]]。<ref name="diestel">{{citation|title=Graph Theory|volume=173|series=Graduate Texts in Mathematics|first=Reinhard|last=Diestel|publisher=Springer|year=2012|chapter=1.9 Some linear algebra|pages=23–28|chapter-url=https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23|access-date=2016-09-27|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204155010/https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23|url-status=live}}.</ref>
==在图上探测环==
有向图和无向图上的环可用[[深度优先搜索]]（{{lang|en|DFS}}）探测：寻找一条连接当前顶点与之前顶点的边（它包含了一条后向边）。<ref>{{cite book |author={{le|Alan Tucker||Tucker, Alan}} |title=Applied Combinatorics |year=2006 |publisher=John Wiley & sons |location=Hoboken |isbn=978-0-471-73507-6 |edition=5th |page=49 |chapter=Chapter 2: Covering Circuits and Graph Colorings }}</ref>DFS跳过的所有后向边都属于某个环。<ref name="sedgewick">{{citation |first=Robert |last=Sedgewick |authorlink=罗伯特·塞奇威克 |title=Algorithms |chapter=Graph algorithms |year=1983 |publisher=Addison–Wesley |isbn=0-201-06672-6 |url=https://archive.org/details/algorithms00sedg }}</ref>无向图上，指向父节点的边不能算作后向边，但找到已经过的顶点意味着后向边的存在。找到''n''阶无向图上的环只需要''O''(''n'')时间。

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

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

环检测的应用如用{{le|wait-for graph}}检测并行系统的[[死锁]]。<ref>{{cite book |last=Silberschatz |first=Abraham |author2=Peter Galvin |author3=Greg Gagne |title=Operating System Concepts |url=https://archive.org/details/operatingsystemc0006silb |publisher=John Wiley & Sons, INC. |year=2003 |pages=[https://archive.org/details/operatingsystemc0006silb/page/260 260] |isbn=0-471-25060-0 }}</ref>
=== 算法 ===
上述用深度优先搜索查找循环的方法可描述为：
 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年，[[欧拉]]在关于[[柯尼斯堡七桥问题]]的论文中证明，要使有限无向图中的闭合走法能精确访问每条边（使其成为闭合轨迹）一次，必须同时满足：除孤立顶点外是连通的（即所有边都包含在一个分量中），同时每个点的度都是偶数。而对有向图，存在闭漫游（{{lang|en|closed walk}}）不重复地经过每条边的充要条件是：图是[[强连通分量|强连接]]的，且每个顶点出入度相等。在这两个情况下，环或漫游称作[[一笔画问题|欧拉环]]。对有限无向图（无论连通），若其每个顶点的度都是偶数，则可以找到一组简单的环不重复地覆盖每一条边，这就是{{le|维布伦定理|Veblen's theorem}}。<ref>{{Citation |last=Veblen |first=Oswald |authorlink=奧斯瓦爾德·維布倫 |title=An Application of Modular Equations in Analysis Situs |jstor=1967604 |series=Second Series | year=1912 |journal=[[數學年刊]] |volume=14 |issue=1 |pages=86–94 |doi=10.2307/1967604 }}.</ref>即使连通图不满足欧拉定理的条件，仍可以在[[多项式时间]]内通过解[[邮递员问题]]，找到长度最短的闭漫游，经过每一条边至少一次。

在图上找到不重复地过每个顶点的简单环，要更加困难，这样的环是[[哈密顿环]]，确定图上是否存在哈密顿环是[[NP完全]]问题。<ref>{{citation |author=[[理查德·卡普|Richard M. Karp]] |chapter=Reducibility Among Combinatorial Problems |chapter-url=http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf |title=Complexity of Computer Computations |editor=R. E. Miller and J. W. Thatcher |publisher=New York: Plenum |pages=85–103 |year=1972 |accessdate=2020-10-04 |archive-date=2021-02-10 |archive-url=https://web.archive.org/web/20210210182452/http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf |dead-url=no }}.</ref>很多研究已经找到了一些种类的图，其上一定能找到哈密顿环。例如[[奧爾定理]]：若图上每对不相邻顶点的度之和大于等于图的阶数，则图中有哈密顿环。 <ref>{{citation |first=Ø. |last=Ore |authorlink=奥斯丁·欧尔 |title=Note on Hamilton circuits |journal=[[美國數學月刊]] |volume=67 |year=1960 |page=55 |issue=1 |jstor=2308928 |doi=10.2307/2308928 }}.</ref>

{{le|循环双覆盖猜想|cycle double cover conjecture}}可表述为：对无[[桥 (图论)|桥]]图，存在由简单环组成的[[多重集]]，使它们一起能覆盖每条边恰好两次。目前这个猜想仍未证明或证伪。<ref>{{citation |last=Jaeger |first=F. |contribution=A survey of the cycle double cover conjecture |doi=10.1016/S0304-0208(08)72993-1 |pages=1–12 |series=North-Holland Mathematics Studies |title=Annals of Discrete Mathematics 27 – Cycles in Graphs |volume=27 |year=1985 }}.</ref>

==由环刻画的图类别 ==
有一些重要的图的类型可以被环来刻画和定义。它们包括：
* [[二分图]]，不存在奇数长的环的图
* {{le|仙人掌圖|Cactus graph}}，a graph in which every nontrivial biconnected component is a cycle
* [[环图]]，一个环组成的图
* [[弦圖]]，不存在长度大于3的导出环（induced cycle）的图
* [[有向无环图]]，a directed graph with no cycles
* [[线完美图]]，每一个奇数长度的简单环都是一个三角形
* [[完美图定理|完美图]]，不存在长度大于3的洞(hole)或反洞(antihole)
* {{le|Pseudoforest}}，a graph in which each connected component has at most one cycle
* {{le|绞窄图|Strangulated graph}}，a graph in which every peripheral cycle is a triangle
* [[强连通分量|强连通图]]，一个有向图，其中每一条边都是环的一部分
* {{le|無三角形圖|Triangle-free graph}}，a graph without three-vertex cycles

==參見==
* {{le|环空间|Cycle space}}
* {{le|環基|Cycle basis}}
* 迭代函数值序列中的{{le|环探测|Cycle detection}}

==參考文獻==
{{reflist}}

{{图论}}