961
个编辑
更改
跳到导航
跳到搜索
第7行：
第7行： − 在图论中，一个图中的环Cycle是一个非空轨迹，其中唯一重复的点是起始点和最终点。如果是一个有向图的有向环Directed cycle，它同样是非空有向迹线，其中唯一重复的点也是起始点和最终点。+ 第15行：
第15行： − 不带有环的图称为无环图Acyclic graph。不带有有向环的有向图称为有向无环图Directed acyclic graph。没有环的连接图称为树Tree。+ 第29行：
第29行： − + 第57行：
第57行： − 一个图的无弦环Chordless cycles（也可以称为孔Hole或导出环Induced cycle），指的是该环中没有两个顶点通过不属于该环的边相连。其反孔部分为此图孔的补图。无弦环i可用于表征完美图Perfect graphs：通过强完美图定理，当且仅当它的孔或反孔部分中无奇数（且大于3）个顶点时，图才是完美的。弦图是完美图的特殊形式，即没有任何长度大于三的孔。+ 第65行：
第65行： − 图的围长Girth是其最小环的长度；并且这个环必须是无弦的。笼Cages定义为具有给定度和围长组合的最小正则图。+ 第73行：
第73行： − 一个图中的边环Peripheral cycle具有以下性质：不在此边环上的两条连边可以通过一条特殊路径连接，该路径内部顶点均不在此边环上。如果一个图中的某条环并非通过加一条边形成，那么其边环肯定是导出环。+ 第81行：
第81行： − 关于术语“环Cycle”还可以指代一个图中环空间的一个元素。在一个图中，存在很多环空间，每个都有对应的系数域Coefficient field或环Ring（代数）。最常见的是二元环空间（通常简称为环空间），它是由在该图中每个顶点上具有偶数度的边集组成。它在二元域上形成了一个向量空间。根据维布伦定理Veblen's theorem，该环空间的每个元素都可以形成为简单环的不相交边的并集。该图的环基相当于一组简单环，它们构成了环空间的基。+ 第89行：
第89行： − 根据代数拓扑Algebraic topology的思想，二元环空间Binary cycle space可以推广为其他环Ring中的向量空间Vector spaces或模Module，例如整数，有理数或实数等。+
无编辑摘要
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.
在图论中，一个图中的'''<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>'''。
*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.
* 回路Circuit是一条非空路径，其中第一个和最后一个顶点重复。设图''G =（V，E，ϕ）''，那么回路是具有顶点序列（''v1，v2，...，vn，v1''）的非空路径（''e1，e2，…，en''）。
* '''<font color="#ff8000"> 回路Circuit</font>'''是一条非空路径，其中第一个和最后一个顶点重复。设图''G =（V，E，ϕ）''，那么回路是具有顶点序列（''v1，v2，...，vn，v1''）的非空路径（''e1，e2，…，en''）。
* 在一个环或简单回路中，唯一重复的顶点是起始点和最终点。
* 在一个环或简单回路中，唯一重复的顶点是起始点和最终点。
* 一个回路或环的长度指的是相关连边的数量。
* 一个回路或环的长度指的是相关连边的数量。
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）个顶点时，图才是完美的。弦图是完美图的特殊形式，即没有任何长度大于三的孔。
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.
图的'''<font color="#ff8000"> 围长Girth</font>'''是其最小环的长度；并且这个环必须是无弦的。'''<font color="#ff8000"> 笼Cages</font>'''定义为具有给定度和围长组合的最小正则图。
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.
一个图中的'''<font color="#ff8000"> 边环Peripheral cycle</font>'''具有以下性质：不在此边环上的两条连边可以通过一条特殊路径连接，该路径内部顶点均不在此边环上。如果一个图中的某条环并非通过加一条边形成，那么其边环肯定是导出环。
== Cycle space 环空间 ==
== 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.
关于术语“'''<font color="#ff8000"> 环Cycle</font>'''”还可以指代一个图中环空间的一个元素。在一个图中，存在很多环空间，每个都有对应的'''<font color="#ff8000"> 系数域Coefficient field</font>'''或'''<font color="#ff8000"> 环Ring（代数）</font>'''。最常见的是二元环空间（通常简称为环空间），它是由在该图中每个顶点上具有偶数度的边集组成。它在二元域上形成了一个向量空间。根据'''<font color="#ff8000"> 维布伦定理Veblen's theorem</font>'''，该环空间的每个元素都可以形成为简单环的不相交边的并集。该图的环基相当于一组简单环，它们构成了环空间的基。
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.
根据'''<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>'''，例如整数，有理数或实数等。