961
个编辑
更改
跳到导航
跳到搜索
第45行：
第45行： − + − + − − 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 是一个和弦。 第59行：
第55行： − 图中的无弦循环，也称为洞循环或诱导循环，是这样一种循环，即循环的两个顶点都不由一条本身不属于该循环的边连接。反孔是图孔的补。无弦圈可以用来刻画完美图: 根据完美图问题，一个图是完美的当且仅当它的孔洞或反孔洞都没有大于3的奇数顶点数。弦图是完美图的一种特殊类型，它没有任何大于3的孔洞。+ 第67行：
第63行： − 图的周长是其最短周期的长度; 这个周期必然是无弦的。笼状图是给定度和围长组合的最小正则图。+ 第75行：
第71行： − 外围圈是图中的一个圈，它的性质是不在圈上的每两条边都可以通过一条内部顶点避开圈的路连接起来。如果一个图不是通过向一个圈加一条边而形成的，那么一个外围圈必然是一个诱导圈。+ − −
→Chordless cycles
* 在一个有向环或简单有向回路中，唯一重复的顶点是起始点和最终点
* 在一个有向环或简单有向回路中，唯一重复的顶点是起始点和最终点
== Chordless cycles ==
== Chordless cycles 无弦环 ==
[[File:Graph with Chordless and Chorded Cycles.svg|thumb|right|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.]]
[[File:Graph with Chordless and Chorded Cycles.svg|thumb|right|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）个顶点时，图才是完美的。弦图是完美图的特殊形式，即没有任何长度大于三的孔。
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 ==
== Cycle space ==