更改

 

[[文件:Graph cycle.svg|200px|thumb|right|这是一个经过着色的图，用于说明路径H-A-B（绿色），闭合路径或具有重复顶点的路径B-D-E-F-D-C-B（蓝色）和无重复边或顶点的环H-D-G-H（红色）。]]

[[文件:Graph cycle.svg|200px|thumb|right|这是一个经过着色的图，用于说明路径H-A-B（绿色），闭合路径或具有重复顶点的路径B-D-E-F-D-C-B（蓝色）和无重复边或顶点的环H-D-G-H（红色）。]]

In [[graph theory]], a '''cycle''' in a [[Graph (discrete mathematics)|graph]] is a non-empty [[Path (graph theory)#Walk, trail, path|trail]] in which the only repeated [[Vertex (graph theory)|vertices]] are the first and last vertices. A '''directed cycle''' in a [[directed graph]] is a non-empty [[Path (graph theory)#Directed walk, trail, path|directed trail]] in which the only repeated vertices are the first and last vertices.

在'''图论 graph theory'''中，一个图中的'''环Cycle'''是一个非空轨迹，其中唯一重复的点是起点和终点。一个有向图中的''' 有向环Directed cycle'''同样是非空有向迹线，其中唯一重复的点也是起点和终点。

 

 

在图论中，一个图中的'''<font color="#ff8000"> 环Cycle</font>'''是一个非空轨迹，其中唯一重复的点是起点和终点。一个有向图中的'''<font color="#ff8000"> 有向环Directed cycle</font>'''同样是非空有向迹线，其中唯一重复的点也是起点和终点。

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.

没有环的图称为'''<font color="#ff8000"> 无环图Acyclic graph</font>'''。没有有向环的有向图称为'''<font color="#ff8000"> 有向无环图Directed acyclic graph</font>'''。没有环的连接图称为'''<font color="#ff8000"> 树Tree</font>'''。

没有环的图称为'''无环图 acyclic graph'''。一个有向图，但是没有有向环，称为'''有向无环图Directed acyclic graph'''。没有环的连接图称为''' 树 Tree'''。

== Definitions 定义 ==

== 定义 ==

=== Circuit, cycle 回路，环 ===

=== 回路，环 ===

* A '''circuit''' is a non-empty [[Path (graph theory)#Walk, trail, path|trail]] in which the first and last vertices are repeated.{{sfn|Bender|Williamson|2010|p=164}}

* A '''circuit''' is a non-empty [[Path (graph theory)#Walk, trail, path|trail]] in which the first and last vertices are repeated.{{sfn|Bender|Williamson|2010|p=164}}

*The '''length''' of a circuit or cycle is the number of edges involved.

*The '''length''' of a circuit or cycle is the number of edges involved.

* '''<font color="#ff8000"> 回路Circuit</font>'''如图，一条非空路径，其中第一个和最后一个顶点重合。设图''G =（V，E，ϕ）''，那么回路是具有顶点序列（''v1，v2，...，vn，v1''）的非空路径（''e1，e2，…，en''）。

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

* 在一个环或简单回路中，唯一重复的顶点是起点和终点。

* 在一个环或简单回路中，唯一重复的顶点是起点和终点。

* 一个回路（或环）的长度指的是相关连边的数量。

* 一个回路（或环）的长度指的是相关连边的数量。

   --[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]])  【审校】补充翻译：如图所示，以一个具有顶点序列的非空轨迹环为例。

   --[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]])  【审校】补充翻译：如图所示，以一个具有顶点序列的非空轨迹环为例。

=== Directed circuit, cycle 有向回路，环 ===

=== 有向回路，环 ===

* A '''directed circuit''' is a non-empty [[Path (graph theory)#Directed walk, trail, path|directed trail]] in which the first and last vertices are repeated.{{sfn|Bender|Williamson|2010|p=164}}

* A '''directed circuit''' is a non-empty [[Path (graph theory)#Directed walk, trail, path|directed trail]] in which the first and last vertices are repeated.{{sfn|Bender|Williamson|2010|p=164}}

* 在一个有向环或简单有向回路中，唯一重合的顶点是起点和终点

* 在一个有向环或简单有向回路中，唯一重合的顶点是起点和终点

== Chordless cycles 无弦环 ==

== 无弦环 ==

[[文件:Graph with Chordless and Chorded Cycles.svg.png|200px|thumb|right|此图中的绿色环（A-B-C-D-E-F-A）是无弦的，而红色环（G-H-I-J-K-L-G）则是有弦的。因为连边K-I是弦。]]

[[文件:Graph with Chordless and Chorded Cycles.svg.png|200px|thumb|right|此图中的绿色环（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.

一个图中的'''<font color="#ff8000"> 无弦环Chordless cycles</font>'''（也可以称为'''<font color="#ff8000"> 孔Hole</font>'''或'''<font color="#ff8000"> 导出环Induced cycle</font>'''），指的是该环中没有两个顶点通过不属于该环的边相连。其反孔部分为此图孔的补图。无弦环i可用于表征'''<font color="#ff8000"> 完美图Perfect graphs</font>'''：通过强完美图定理，当且仅当它的孔或反孔部分中无奇数（且大于3）个顶点时，图才是完美的。弦图是完美图的特殊形式，即没有任何长度大于三的孔。

一个图中的'''<font color="#ff8000"> 无弦环Chordless cycles</font>'''（也可以称为'''<font color="#ff8000"> 孔Hole</font>'''或'''<font color="#ff8000"> 导出环Induced cycle</font>'''），指的是该环中没有两个顶点通过不属于该环的边相连。其反孔部分为此图孔的补图。无弦环i可用于表征'''<font color="#ff8000"> 完美图Perfect graphs</font>'''：通过'''强完美图定理 strong perfect graph theorem'''，当且仅当它的孔或反孔部分中无奇数（且大于3）个顶点时，图才是完美的。弦图是完美图的特殊形式，即没有任何长度大于三的孔。

一个图中的'''<font color="#ff8000"> 边环Peripheral cycle</font>'''具有以下性质：不在此边环上的两条连边可以通过一条特殊路径连接；该路径内部顶点均不在此边环上。如果一个图中的某条环不是通过添加一条边形成的，那么其边环肯定是导出环。

一个图中的'''<font color="#ff8000"> 边环Peripheral cycle</font>'''具有以下性质：不在此边环上的两条连边可以通过一条特殊路径连接；该路径内部顶点均不在此边环上。如果一个图中的某条环不是通过添加一条边形成的，那么其边环肯定是导出环。

== 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 [[finite field|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 (linear algebra)|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 [[finite field|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 (linear algebra)|basis]] of the cycle space.

根据'''<font color="#ff8000"> 代数拓扑Algebraic topology</font>'''的思想，'''<font color="#ff8000"> 二元环空间Binary cycle space</font>'''可以推广为其它'''<font color="#ff8000"> 环Ring</font>'''中的'''<font color="#ff8000"> 向量空间Vector spaces</font>'''或'''<font color="#ff8000"> 模Module</font>'''，例如整数，有理数或实数等。

根据'''<font color="#ff8000"> 代数拓扑Algebraic topology</font>'''的思想，'''<font color="#ff8000"> 二元环空间Binary cycle space</font>'''可以推广为其它'''<font color="#ff8000"> 环Ring</font>'''中的'''<font color="#ff8000"> 向量空间Vector spaces</font>'''或'''<font color="#ff8000"> 模Module</font>'''，例如整数，有理数或实数等。

== 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 [[Depth-first search#Output of a depth-first search|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''&nbsp;−&nbsp;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 [[Depth-first search#Output of a depth-first search|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''&nbsp;−&nbsp;1 edges can be tree edges.

环检测的应用还包括使用'''<font color="#ff8000"> 等待图Wait-for graphs</font>'''来检测并发系统中的'''<font color="#ff8000"> 死锁Deadlocks</font>'''。

环检测的应用还包括使用'''<font color="#ff8000"> 等待图Wait-for graphs</font>'''来检测并发系统中的'''<font color="#ff8000"> 死锁Deadlocks</font>'''。

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

<small>This page was moved from [[wikipedia:en:Cycle (graph theory)]]. Its edit history can be viewed at [[环/edithistory]]</small></noinclude>

<small>This page was moved from [[wikipedia:en:Cycle (graph theory)]]. Its edit history can be viewed at [[环/edithistory]]</small></noinclude>