7,129
个编辑
更改
跳到导航
跳到搜索
第27行：
第27行： + + − 一个图中的'''<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"> 围长Girth</font>'''是其最小环的长度；并且这个环必须是无弦的。'''<font color="#ff8000"> 笼Cages</font>'''定义为具有给定度和围长组合的最小正则图。+ − − 一个图中的'''<font color="#ff8000"> 边环Peripheral cycle</font>'''具有以下性质：不在此边环上的两条连边可以通过一条特殊路径连接；该路径内部顶点均不在此边环上。如果一个图中的某条环不是通过添加一条边形成的，那么其边环肯定是导出环。
→无弦环
[[文件: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是弦。]]
一个图中的'''<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"> 围长 girth</font>'''是其最小环的长度；并且这个环必须是无弦的。'''<font color="#ff8000"> 笼 cages</font>'''定义为具有给定度和围长组合的最小正则图。
一个图中的'''<font color="#ff8000"> 边环 Peripheral cycle</font>'''具有以下性质：不在此边环上的两条连边可以通过一条特殊路径连接；该路径内部顶点均不在此边环上。如果一个图中的某条环不是通过添加一条边形成的，那么其边环肯定是导出环。
<br>
== 环空间 ==
== 环空间 ==