更改

跳到导航 跳到搜索
添加9字节 、 2020年10月2日 (五) 22:38
第54行: 第54行:  
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>''':通过强完美图定理,当且仅当它的孔或反孔部分中无奇数(且大于3)个顶点时,图才是完美的。弦图是完美图的特殊形式,即没有任何长度大于三的孔。
      第70行: 第70行:  
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>'''具有以下性质:不在此边环上的两条连边可以通过一条特殊路径连接,该路径内部顶点均不在此边环上。如果一个图中的某条环并非通过加一条边形成,那么其边环肯定是导出环。
+
一个图中的'''<font color="#ff8000"> 边环Peripheral cycle</font>'''具有以下性质:不在此边环上的两条连边可以通过一条特殊路径连接;该路径内部顶点均不在此边环上。如果一个图中的某条环不是通过添加一条边形成的,那么其边环肯定是导出环。
    
== Cycle space 环空间 ==
 
== Cycle space 环空间 ==
526

个编辑

导航菜单