环

此词条由Jie翻译。

A graph with edges colored to illustrate path H-A-B (green), closed path or walk with a repeated vertex B-D-E-F-D-C-B (blue) and a cycle with no repeated edge or vertex H-D-G-H (red). 这是一个经过着色的图，用于说明路径H-A-B（绿色），闭合路径或具有重复顶点的路径B-D-E-F-D-C-B（蓝色）和无重复边或顶点的环H-D-G-H（红色）。

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 回路，环

• A circuit is a non-empty trail in which the first and last vertices are repeated.模板:Sfn

Let G = (V, E, ϕ) be a graph. A circuit is a non-empty trail (e₁, e₂, …, e_n) with a vertex sequence (v₁, v₂, …, v_n, v₁).

Let  be a graph. A circuit is a non-empty trail  with a vertex sequence .

• 回路是一条非空路径，其中第一个和最后一个顶点重复。设图G =（V，E，ϕ），回路是具有顶点序列（v1，v2，...，vn，v1）的非空路径（e1，e2，…，en）。

• 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.
• 一个回路或环的长度指的是相关连边的数量。

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 (e₁, e₂, …, e_n) with a vertex sequence (v₁, v₂, …, v_n, v₁).

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

Chordless cycles

文件:Graph with Chordless and Chorded Cycles.svg

In this graph the green cycle (A-B-C-D-E-F-A) is chordless whereas the red cycle (G-H-I-J-K-L-G) is not. This is because the edge K-I is a chord.

In this graph the green cycle (A-B-C-D-E-F-A) is chordless whereas the red cycle (G-H-I-J-K-L-G) is not. This is because the edge K-I is a chord.

在这个图中，绿色循环(A-B-C-D-E-F-A)是无脉络的，而红色循环(G-H-I-J-K-L-G)则不是。这是因为边 K-I 是一个和弦。

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的奇数顶点数。弦图是完美图的一种特殊类型，它没有任何大于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.

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.

术语“圈”也可以指图的圈空间的一个元素。有许多圈空间，每个系数域或环都有一个圈空间。最常见的是二元循环空间(通常简称为循环空间) ，它由在每个顶点具有偶度的边集组成，它在二元域上形成一个向量空间。根据维布伦定理，圈空间中的每个元素都可以构成简单圈的边不交并。图的圈基是构成圈空间基的一组简单圈。

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.

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.

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

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).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.

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 跳过的所有后边都是循环的一部分。在无向图中，一个节点的父节点的边不能算作后边，但是找到任何其他已经访问过的顶点都表示后边。在无向图的情况下，只需要 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.

 | isbn = 0-471-25060-0}}</ref>

| isbn = 0-471-25060-0} </ref >

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.

在他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. 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.

| 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.

| 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 space

• Cycle basis

• Cycle detection in a sequence of iterated function values

References

• 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