7,129
个编辑
更改
跳到导航
跳到搜索
第59行：
第59行： − +
无编辑摘要
根据''' 强完美图定理 Strong perfect graph theorem'''，完美图具有类似于二分图的''' 禁止图特征 Forbidden graph characterization'''：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为''' 导出子图Induced subgraph'''时，图才是完美的。二分图及其线图、补图占据了完美图五种基本类别中的四个，它们可以用于证明了强完美图定理。<ref>{{citation | last1 = Chudnovsky | first1 = Maria | last2 = Robertson | first2 = Neil | last3 = Seymour | first3 = Paul | last4 = Thomas | first4 = Robin | doi = 10.4007/annals.2006.164.51 | issue = 1 | journal = Annals of Mathematics| pages = 51–229
根据''' 强完美图定理 Strong perfect graph theorem'''，完美图具有类似于二分图的''' 禁止图特征 Forbidden graph characterization'''：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为''' 导出子图Induced subgraph'''时，图才是完美的。二分图及其线图、补图占据了完美图五种基本类别中的四个，它们可以用于证明了强完美图定理。<ref>{{citation | last1 = Chudnovsky | first1 = Maria | last2 = Robertson | first2 = Neil | last3 = Seymour | first3 = Paul | last4 = Thomas | first4 = Robin | doi = 10.4007/annals.2006.164.51 | issue = 1 | journal = Annals of Mathematics| pages = 51–229
| title = The strong perfect graph theorem | volume = 164 | year = 2006| citeseerx = 10.1.1.111.7265| arxiv = math/0212070| s2cid = 119151552 }}.</ref>
| title = The strong perfect graph theorem | volume = 164 | year = 2006| citeseerx = 10.1.1.111.7265| arxiv = math/0212070}}.</ref>
<br>
<br>