环
此词条由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.
在图论中，图中的一个环是非空轨迹，其中唯一重复的顶点是第一个和最后一个顶点。有向图中的有向环是非空有向迹线，其中唯一重复的顶点是第一个和最后一个顶点。
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.
不带有环的图称为无环图。不带有有向环的有向图称为有向无环图。没有环的连接图称为树。
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.
- 回路是一条非空路径，其中第一个和最后一个顶点重复。设图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.
一个图的无弦环（也可以称为孔或诱导环），指的是该环中没有两个顶点通过不属于该环的边相连。其反孔部分为此图孔的补图。无弦环可用于表征完美图：通过强完美图定理，当且仅当它的孔或反孔部分中无奇数（且大于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.
图的围长是其最小环的长度；并且这个环必须是无弦的。笼定义为具有给定度和围长组合的最小正则图。
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.
一个图中的边环具有以下性质：不在此边环上的两条连边可以通过一条特殊路径连接，该路径内部顶点均不在此边环上。如果一个图中的某条环并非通过加一条边形成，那么其边环肯定是诱导环。
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).[3]All the back edges which DFS skips over are part of cycles.[4] 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.[4]
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.引用错误：没有找到与</ref>对应的<ref>标签 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.
在他1736年关于柯尼斯堡七桥问题图的论文中，被广泛认为是图论的诞生，Leonhard Euler 证明了，对于一个有限的无向图来说，如果有一个封闭的步行恰好访问每条边一次，那么除了孤立的顶点(也就是说，所有的边都包含在一个分量中)和每个顶点的度之外，它是连通的，这是充分必要的。在有向图中，存在一个正好一次访问每条边的闭角色塑造的对应条件是该图是强连通的并且在每个顶点上有相等数目的入边和出边。无论哪种情况，最终的行走都被称为欧拉循环或欧拉环。如果一个有限的无向图在它的每个顶点上都有偶数度，不管它是否连通，那么就有可能找到一组简单的圈，它们一起精确地覆盖每条边一次: 这就是维布伦定理。当连通图不满足欧拉定理的条件时，通过求解路径检查问题，可以在多项式时间内找到覆盖每条边至少一次的最小长度封闭行走。
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.引用错误：没有找到与</ref>对应的<ref>标签 Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is Ore's theorem that a Hamiltonian cycle can always be found in a graph for which every non-adjacent pair of vertices have degrees summing to at least the total number of vertices in the graph.[5]
| year = 1972}}.</ref> Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is Ore's theorem that a Hamiltonian cycle can always be found in a graph for which every non-adjacent pair of vertices have degrees summing to at least the total number of vertices in the graph.
1972}}.关于可以保证包含哈密顿圈的图类，已经发表了许多研究成果，其中一个例子是奥尔定理，即哈密顿圈总是可以在一个图中找到，对于这个图，每一对不相邻的顶点都有至少与图中顶点总数相加的度数。
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>对应的<ref>标签
| year = 1985}}..</ref>
1985} . . </ref >
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
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.
- ↑ Tucker, Alan (2006). "Chapter 2: Covering Circuits and Graph Colorings". Applied Combinatorics (5th ed.). Hoboken: John Wiley & sons. p. 49. ISBN 978-0-471-73507-6.
- ↑ 4.0 4.1 Sedgewick, Robert (1983), "Graph algorithms", Algorithms, Addison–Wesley, ISBN 0-201-06672-6
- ↑ Ore, Ø. (1960), "Note on Hamilton circuits", American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928.
- 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