環 (圖論)

在图论中，环是一条只有第一个和最后一个顶点重复的非空路徑。一个没有环的图被称作无环图，一个没有有向环的有向图被称做有向无环图。一个无环的连通图被称作树。

一个有向闭路的环

定义

回路，环

一个回路是一条非空的有向路径，其中第一个顶点和最后一个顶点相同。令图 $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的无弦环

图的围长是这个图包含的最短的环的长度。根据这个定义，最短环一定是无弦的。笼被定义为给定了围长和度之后的最小的正则图。

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

在图上探测环

在有向图和无向图上的环可以被使用深度优先搜索(DFS)的方法，通过寻找一条连接当前顶点与之前顶点的边（它包含了一条后向边），我们可以探测有向图和无向图上环的存在。[1] 所有DFS跳过的后向边都是某些环的一部分。[2] 在一个无向图上，指向父节点的边不能被算作后向边，但是找到已经被经过了的顶点意味着后向边的存在。在无向图的情况下，找到一个阶数为 $n$ 图上的环只需要O(n)时间。

许多拓扑排序算法也会探测环的存在，因为这些环会成为拓扑排序存在的障碍。另外，如果一个有向图被分成了几个强连通分量,那么环只会在这些分量内部存在，而不会连接这几个分量，因为环本身就是强连接的。[2]

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

环检测的应用包含了使用wait-for graph来检测并行系统中的死锁。[3]

用环覆盖图

1736年，欧拉证明了对于一个有限无向的图，存在一个环不重复地经过图上的每一条边地充要条件是除了孤立的定点之外，它是连通的，同时每个点的度都是偶数。相对应地，对于一个有向图来说，存在一个闭的漫游(closed walk)不重复地经过图上的每条边的红药条件是这个图是强连接的，并且每个顶点都有相同的出度和入度。在这两个情况下，这个环或漫游被称作欧拉环。如果一个有限的无向图，不论它是否连通，如果其每个顶点的度都是偶数，则可以找到一组简单的环不重复地覆盖每一条边，这被称作Veblen's theorem。[4] 即使当一个连通图并不满足欧拉定理的条件，我们仍然可以在多项式时间内通过解邮递员问题来找到一个长度最短的闭漫游(closed walk)使其经过每一条边至少一次。

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

cycle double cover conjecture可以表述为：对于每个无桥的图，存在一个简单环组成的多重集使得它们一起能够覆盖每一条边恰好两次。目前这个猜想认为被证明或证伪。[7]

由环刻画的图类别

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

二分图，不存在奇数长的环的图
仙人掌圖，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
Strangulated graph，a graph in which every peripheral cycle is a triangle
强连通图，一个有向图，其中每一条边都是环的一部分
無三角形圖，a graph without three-vertex cycles

參見

环空间
循環基底
Cycle detection in a sequence of iterated function values

參考文獻

Tucker, Alan. . 5th. Hoboken: John Wiley & sons. 2006: 49. ISBN 978-0-471-73507-6.
Sedgewick, Robert, , , Addison–Wesley, 1983, ISBN 0-201-06672-6
Silberschatz, Abraham; Peter Galvin; Greg Gagne. . John Wiley & Sons, INC. 2003: 260. ISBN 0-471-25060-0.
Veblen, Oswald, , 數學年刊, Second Series, 1912, 14 (1): 86–94, JSTOR 1967604, doi:10.2307/1967604.
Richard M. Karp, (PDF), R. E. Miller and J. W. Thatcher (编), , New York: Plenum: 85–103, 1972.
Ore, Ø., , 美國數學月刊, 1960, 67 (1): 55, JSTOR 2308928, doi:10.2307/2308928.
Jaeger, F., , , North-Holland Mathematics Studies 27: 1–12, 1985, doi:10.1016/S0304-0208(08)72993-1..

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Tucker, Alan. . 5th. Hoboken: John Wiley & sons. 2006: 49. ISBN 978-0-471-73507-6.

[sedgewick-2] Sedgewick, Robert, , , Addison–Wesley, 1983, ISBN 0-201-06672-6

[3] Silberschatz, Abraham; Peter Galvin; Greg Gagne. . John Wiley & Sons, INC. 2003: 260. ISBN 0-471-25060-0.

[4] Veblen, Oswald, , 數學年刊, Second Series, 1912, 14 (1): 86–94, JSTOR 1967604, doi:10.2307/1967604.

[5] Richard M. Karp, (PDF), R. E. Miller and J. W. Thatcher (编), , New York: Plenum: 85–103, 1972.

[6] Ore, Ø., , 美國數學月刊, 1960, 67 (1): 55, JSTOR 2308928, doi:10.2307/2308928.

[7] Jaeger, F., , , North-Holland Mathematics Studies 27: 1–12, 1985, doi:10.1016/S0304-0208(08)72993-1..