环
此词条由Jie翻译。
In graph theory, a cycle in a graph is a non-empty trail in which the only repeated vertices are the first and last vertices. A directed cycle in a directed graph is a non-empty directed trail in which the only repeated vertices are the first and last vertices.
In graph theory, a cycle in a graph is a non-empty trail in which the only repeated vertices are the first and last vertices. A directed cycle in a directed graph is a non-empty directed trail in which the only repeated vertices are the first and last vertices.
在图论中，一个图中的 环Cycle是一个非空轨迹，其中唯一重复的点是起始点和最终点。如果是一个有向图的 有向环Directed cycle，它同样是非空有向迹线，其中唯一重复的点也是起始点和最终点。
A graph without cycles is called an acyclic graph. A directed graph without directed cycles is called a directed acyclic graph. A connected graph without cycles is called a tree.
A graph without cycles is called an acyclic graph. A directed graph without directed cycles is called a directed acyclic graph. A connected graph without cycles is called a tree.
不带有环的图称为 无环图Acyclic graph。不带有有向环的有向图称为 有向无环图Directed acyclic graph。没有环的连接图称为 树Tree。
Definitions 定义
Circuit, cycle 回路，环
- Let G = (V, E, ϕ) be a graph. A circuit is a non-empty trail (e1, e2, …, en) with a vertex sequence (v1, v2, …, vn, v1).
Let be a graph. A circuit is a non-empty trail with a vertex sequence .
- A cycle or simple circuit is a circuit in which the only repeated vertices are the first and last vertices.模板:Sfn
- The length of a circuit or cycle is the number of edges involved.
- 回路Circuit是一条非空路径，其中第一个和最后一个顶点重复。设图G =（V，E，ϕ），那么回路是具有顶点序列（v1，v2，...，vn，v1）的非空路径（e1，e2，…，en）。
- 在一个环或简单回路中，唯一重复的顶点是起始点和最终点。
- 一个回路或环的长度指的是相关连边的数量。
Directed circuit, cycle 有向回路，环
- A directed circuit is a non-empty directed trail in which the first and last vertices are repeated.模板:Sfn
- Let G = (V, E, ϕ) be a directed graph. A directed circuit is a non-empty directed trail (e1, e2, …, en) with a vertex sequence (v1, v2, …, vn, v1).
Let be a directed graph. A directed circuit is a non-empty directed trail with a vertex sequence
- A directed cycle or simple directed circuit is a directed circuit in which the only repeated vertices are the first and last vertices.模板:Sfn
- 有向回路是一个非空有向路径，其中第一个和最后一个顶点重复出现。设有向图G =（V，E，ϕ），其有向回路是具有顶点序列（v1，v2，...，vn，v1）的非空有向路径（e1，e2，……，en）。
- 在一个有向环或简单有向回路中，唯一重复的顶点是起始点和最终点
Chordless cycles 无弦环
A chordless cycle in a graph, also called a hole or an induced cycle, is a cycle such that no two vertices of the cycle are connected by an edge that does not itself belong to the cycle. An antihole is the complement of a graph hole. Chordless cycles may be used to characterize perfect graphs: by the strong perfect graph theorem, a graph is perfect if and only if none of its holes or antiholes have an odd number of vertices that is greater than three. A chordal graph, a special type of perfect graph, has no holes of any size greater than three.
A chordless cycle in a graph, also called a hole or an induced cycle, is a cycle such that no two vertices of the cycle are connected by an edge that does not itself belong to the cycle. An antihole is the complement of a graph hole. Chordless cycles may be used to characterize perfect graphs: by the strong perfect graph theorem, a graph is perfect if and only if none of its holes or antiholes have an odd number of vertices that is greater than three. A chordal graph, a special type of perfect graph, has no holes of any size greater than three.
一个图的 无弦环Chordless cycles（也可以称为 孔Hole或 导出环Induced cycle），指的是该环中没有两个顶点通过不属于该环的边相连。其反孔部分为此图孔的补图。无弦环i可用于表征 完美图Perfect graphs：通过强完美图定理，当且仅当它的孔或反孔部分中无奇数（且大于3）个顶点时，图才是完美的。弦图是完美图的特殊形式，即没有任何长度大于三的孔。
The girth of a graph is the length of its shortest cycle; this cycle is necessarily chordless. Cages are defined as the smallest regular graphs with given combinations of degree and girth.
The girth of a graph is the length of its shortest cycle; this cycle is necessarily chordless. Cages are defined as the smallest regular graphs with given combinations of degree and girth.
图的 围长Girth是其最小环的长度；并且这个环必须是无弦的。 笼Cages定义为具有给定度和围长组合的最小正则图。
A peripheral cycle is a cycle in a graph with the property that every two edges not on the cycle can be connected by a path whose interior vertices avoid the cycle. In a graph that is not formed by adding one edge to a cycle, a peripheral cycle must be an induced cycle.
A peripheral cycle is a cycle in a graph with the property that every two edges not on the cycle can be connected by a path whose interior vertices avoid the cycle. In a graph that is not formed by adding one edge to a cycle, a peripheral cycle must be an induced cycle.
一个图中的 边环Peripheral cycle具有以下性质：不在此边环上的两条连边可以通过一条特殊路径连接，该路径内部顶点均不在此边环上。如果一个图中的某条环并非通过加一条边形成，那么其边环肯定是导出环。
Cycle space 环空间
The term cycle may also refer to an element of the cycle space of a graph. There are many cycle spaces, one for each coefficient field or ring. The most common is the binary cycle space (usually called simply the cycle space), which consists of the edge sets that have even degree at every vertex; it forms a vector space over the two-element field. By Veblen's theorem, every element of the cycle space may be formed as an edge-disjoint union of simple cycles. A cycle basis of the graph is a set of simple cycles that forms a basis of the cycle space.[1]
The term cycle may also refer to an element of the cycle space of a graph. There are many cycle spaces, one for each coefficient field or ring. The most common is the binary cycle space (usually called simply the cycle space), which consists of the edge sets that have even degree at every vertex; it forms a vector space over the two-element field. By Veblen's theorem, every element of the cycle space may be formed as an edge-disjoint union of simple cycles. A cycle basis of the graph is a set of simple cycles that forms a basis of the cycle space.
关于术语“ 环Cycle”还可以指代一个图中环空间的一个元素。在一个图中，存在很多环空间，每个都有对应的 系数域Coefficient field或 环Ring（代数）。最常见的是二元环空间（通常简称为环空间），它是由在该图中每个顶点上具有偶数度的边集组成。它在二元域上形成了一个向量空间。根据 维布伦定理Veblen's theorem，该环空间的每个元素都可以形成为简单环的不相交边的并集。该图的环基相当于一组简单环，它们构成了环空间的基。
Using ideas from algebraic topology, the binary cycle space generalizes to vector spaces or modules over other rings such as the integers, rational or real numbers, etc.[2]
Using ideas from algebraic topology, the binary cycle space generalizes to vector spaces or modules over other rings such as the integers, rational or real numbers, etc.
根据 代数拓扑Algebraic topology的思想， 二元环空间Binary cycle space可以推广为其他 环Ring中的 向量空间Vector spaces或 模Module，例如整数，有理数或实数等。
Cycle detection 环检测
The existence of a cycle in directed and undirected graphs can be determined by whether depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge). In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.
The existence of a cycle in directed and undirected graphs can be determined by whether depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge).All the back edges which DFS skips over are part of cycles. In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.
关于环在有向（无向）图中的存在性，可以通过深度优先搜索（DFS）来确定，具体方法是查找是否存在一条连边指向当前顶点的祖先点（包括回边）。DFS跳过的所有回边都是环的一部分。在无向图中，指向一个节点父级的连边不应算作后边，但是如果找到任何其他已访问的顶点可以视为后边。在无向图的情况下，只需要O（n）时间即可在n个顶点图中找到一个循环，因为最多n-1个边可以是树边。
Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.
Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.
很多拓扑排序算法也可以用于检测环，因为这些环阻碍了拓扑排序。另外，如果一个有向图被划分为具有强连接的不同组成部分，则环仅存在于这些组成部分内，而不是它们之间，因为环本身性质就是强连接的。
For directed graphs, distributed message based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself.
For directed graphs, distributed message based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself.
对于有向图的环检测，可以使用基于分布式消息的算法。其概念是环中的某一个顶点发出了一条消息并最终返回，因此称为分布式环检测算法。
Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a computer cluster (or supercomputer).
Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a computer cluster (or supercomputer).
通过在计算机集群（或超级计算机）上使用分布式图形处理系统，该方法非常适合大规模图的运算。
Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.
Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.
环检测的应用还包括使用等待图来检测并发系统中的死锁。
Covering graphs by cycles 环覆盖图
In his 1736 paper on the Seven Bridges of Königsberg, widely considered to be the birth of graph theory, Leonhard Euler proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once, it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex. The corresponding characterization for the existence of a closed walk visiting each edge exactly once in a directed graph is that the graph be strongly connected and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting walk is known as an Euler cycle or Euler tour. If a finite undirected graph has even degree at each of its vertices, regardless of whether it is connected, then it is possible to find a set of simple cycles that together cover each edge exactly once: this is Veblen's theorem When a connected graph does not meet the conditions of Euler's theorem, a closed walk of minimum length covering each edge at least once can nevertheless be found in polynomial time by solving the route inspection problem.
In his 1736 paper on the Seven Bridges of Königsberg, widely considered to be the birth of graph theory, Leonhard Euler proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once, it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex. The corresponding characterization for the existence of a closed walk visiting each edge exactly once in a directed graph is that the graph be strongly connected and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting walk is known as an Euler cycle or Euler tour. If a finite undirected graph has even degree at each of its vertices, regardless of whether it is connected, then it is possible to find a set of simple cycles that together cover each edge exactly once: this is Veblen's theorem. When a connected graph does not meet the conditions of Euler's theorem, a closed walk of minimum length covering each edge at least once can nevertheless be found in polynomial time by solving the route inspection problem.
莱昂哈德·欧拉Leonhard Euler在1736年发表的关于柯尼斯堡七桥的论文，这篇论文后来被广泛认为是图论的起源。论文中，欧拉做出了以下证明：对于一个具有封闭行走路线的有限无向图，要求访问者经过每条边恰好一次。其充分必要条件是除了孤立的顶点（即，所有边都被两两顶点相连）之外，其他每个顶点都是偶数度。一旦该有向图满足能一次性访问所有边不重复的特征，那么它就具有强连接性，并且每个顶点的进入次数和离开次数必定相等。无论哪种情况，其访问轨迹均被称为欧拉环或欧拉环游。如果一个有限的无向图在其每个顶点上都具有偶数度，那么不管其是否相连，均有可能找到一组简单的环，使满足恰好覆盖该图的每个边一次：这即是维勃伦定理Veblen's theorem。当一个连通图不满足欧拉定理的条件时，通过解决邮路问题，可以在多项式时间内找到覆盖每个边的最短闭合路径。
The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering the edges, is much harder. Such a cycle is known as a Hamiltonian cycle, and determining whether it exists is NP-complete.
The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering the edges, is much harder. Such a cycle is known as a Hamiltonian cycle, and determining whether it exists is NP-complete.
相比较，寻找覆盖每个顶点仅一次而不是覆盖连边的简单环问题要困难得多。这种环被称为哈密顿环，确定其存在性的过程属于NP-完全问题。目前诸多包含哈密顿环的相关图类研究被发表。其中一个例子是奥尔定理Ore's theorem，如果一个图中每个不相邻的顶点对的度数之和最少等于该图中顶点总数，那么该图中必然有哈密顿环。
The cycle double cover conjecture states that, for every bridgeless graph, there exists a multiset of simple cycles that covers each edge of the graph exactly twice. Proving that this is true (or finding a counterexample) remains an open problem.<ref>{{citation
The cycle double cover conjecture states that, for every bridgeless graph, there exists a multiset of simple cycles that covers each edge of the graph exactly twice. Proving that this is true (or finding a counterexample) remains an open problem.<ref>{{citation
双圈覆盖猜想指出，对于每个无桥图，都存在一组简单环可以将图的每个边缘恰好覆盖两次。然而目前其是否成立（或找到反例）仍然是一个悬而未决的问题。
Graph classes defined by cycles 根据环定义的图类
Several important classes of graphs can be defined by or characterized by their cycles. These include:
Several important classes of graphs can be defined by or characterized by their cycles. These include:
图的几个重要类别可以由其环定义或表征。其中包括：
- Bipartite graph, a graph without odd cycles (cycles with an odd number of vertices).
- Cactus graph, a graph in which every nontrivial biconnected component is a cycle
- Cycle graph, a graph that consists of a single cycle.
- Chordal graph, a graph in which every induced cycle is a triangle
- Directed acyclic graph, a directed graph with no cycles
- Line perfect graph, a graph in which every odd cycle is a triangle
- Perfect graph, a graph with no induced cycles or their complements of odd length greater than three
- 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
- Strongly connected graph, a directed graph in which every edge is part of a cycle
- Triangle-free graph, a graph without three-vertex cycles
- 二分图Bipartite graph，其中无奇数环（具有奇数个顶点的环）。
- 仙人掌图Cactus graph，其中每个非平凡的双向连通分量都是一个环。
- 环图Cycle graph，由一个环组成的图。
- 弦图Chordal graph，其中每个导出环都是三角形。
- 有向无环图Directed acyclic graph，无环的有向图。
- 线完美图Line perfect graph，其中每个奇环都是三角形。
- 完美图Perfect graph，无导出环或大于3的奇数路径长度的环。
- 伪森林Pseudoforest，其中每个连通分量最多只有一个环。
- 绞窄图Strangulated graph，其中每个边环都是三角形。
- 强连通图Strongly connected graph，一种有向图，其中每个边都是环的一部分。
- 无三角形图Triangle-free graph，无三个顶点环的图
See also 其他参考资料
- Cycle detection in a sequence of iterated function values 通过迭代函数值序列进行环检测
References
- ↑ Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces", Graph Theory and Its Applications (2nd ed.), CRC Press, pp. 197–207, ISBN 9781584885054.
- ↑ Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28.
- Balakrishnan, V. K. (2005). Schaum's outline of theory and problems of graph theory ([Nachdr.] ed.). McGraw–Hill. ISBN 978-0070054899.
- Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. https://books.google.fr/books?id=vaXv_yhefG8C.
Category:Graph theory objects
范畴: 图论对象
This page was moved from wikipedia:en:Cycle (graph theory). Its edit history can be viewed at 环/edithistory