961
个编辑
更改
跳到导航
跳到搜索
第119行：
第119行： − + 第128行：
第128行： − −
→Kőnig's theorem and perfect graphs 柯尼希定理和完美图
Another class of related results concerns perfect graphs: every bipartite graph, the complement of every bipartite graph, the line graph of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their chromatic number is two and their maximum clique size is also two) but perfection of the complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs.
Another class of related results concerns perfect graphs: every bipartite graph, the complement of every bipartite graph, the line graph of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their chromatic number is two and their maximum clique size is also two) but perfection of the complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs.
另一类相关特性与'''<font color="#ff8000"> 完美图perfect graph</font>'''有关：每个二分图，以及其补图、其线图、其线图的补图均为完美图。其实关于二分图的完美性很容易就可以看出来（他们的色数为2，最大的团数同样为2），但是二分图的补图完美性判定就更简单些，可以看作是柯尼希定理的另一种陈述。其实在定义完美图这一概念的初期，它是作为其中之一的论证结果而存在的。同时完美图线图的补图完美性也是作为柯尼希定理的另一种陈述，线图的完美性陈述了比较早期的柯尼希定理，即每一个二分图的着色边，其色数都等于其最大节点度数。
另一类相关特性与'''<font color="#ff8000"> 完美图Perfect graph</font>'''有关：每个二分图，以及其补图、其线图、其线图的补图均为完美图。其实关于二分图的完美性很容易就可以看出来（他们的色数为2，最大的团数同样为2），但是二分图的补图完美性判定就更简单些，可以看作是柯尼希定理的另一种陈述。其实在定义完美图这一概念的初期，它是作为其中之一的论证结果而存在的。同时完美图线图的补图完美性也是作为柯尼希定理的另一种陈述，线图的完美性陈述了比较早期的柯尼希定理，即每一个二分图的着色边，其色数都等于其最大节点度数。
根据'''<font color="#ff8000"> 强完美图定理Strong perfect graph theorem</font>'''，完美图具有类似于二分图的'''<font color="#ff8000"> 禁止图特征Forbidden graph characterization</font>'''：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为'''<font color="#ff8000"> 导出子图Induced subgraph</font>'''时，图才是完美的。二分图，其线图以及补图构成了完美图五种基本类别中的四个，被用于证明了强完美图定理。
根据'''<font color="#ff8000"> 强完美图定理Strong perfect graph theorem</font>'''，完美图具有类似于二分图的'''<font color="#ff8000"> 禁止图特征Forbidden graph characterization</font>'''：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为'''<font color="#ff8000"> 导出子图Induced subgraph</font>'''时，图才是完美的。二分图，其线图以及补图构成了完美图五种基本类别中的四个，被用于证明了强完美图定理。
=== Degree 度 ===
=== Degree 度 ===