961
个编辑
更改
跳到导航
跳到搜索
第119行：
第119行： − + − + 第127行：
第127行： − + − + 第342行：
第342行： − + − −
→Kőnig's theorem and perfect graphs 柯尼希定理和完美图
Another class of related results concerns [[perfect graph]]s: every bipartite graph, the [[complement (graph theory)|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 [[complement (graph theory)|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.<ref>{{citation|title=Modern Graph Theory
Another class of related results concerns [[perfect graph]]s: every bipartite graph, the [[complement (graph theory)|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 [[complement (graph theory)|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.<ref>{{citation|title=Modern Graph Theory
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.
另一类相关特性与完美图有关：每个二分图，以及其补图、其线图、其线图的补图均为完美图。其实关于二分图的完美性很容易就可以看出来（他们的色数为2，最大的团数同样为2），但是二分图的补图完美性判定就更简单些，可以看作是柯尼希定理的另一种陈述。其实在定义完美图这一概念的初期，它是作为其中之一的论证结果而存在的。同时完美图线图的补图完美性也是作为柯尼希定理的另一种陈述，线图的完美性陈述了比较早期的柯尼希定理，即每一个二分图的着色边，其色数都等于其最大节点度数。
另一类相关特性与完美图有关：每个二分图，以及其补图、其线图、其线图的补图均为完美图。其实关于二分图的完美性很容易就可以看出来（他们的色数为2，最大的团数同样为2），但是二分图的补图完美性判定就更简单些，可以看作是柯尼希定理的另一种陈述。其实在定义完美图这一概念的初期，它是作为其中之一的论证结果而存在的。同时完美图线图的补图完美性也是作为柯尼希定理的另一种陈述，线图的完美性陈述了比较早期的柯尼希定理，即每一个二分图的着色边，其色数都等于其最大节点度数。
According to the [[strong perfect graph theorem]], the perfect graphs have a [[forbidden graph characterization]] resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its [[complement (graph theory)|complement]] as an [[induced subgraph]]. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.<ref>{{citation
According to the [[strong perfect graph theorem]], the perfect graphs have a [[forbidden graph characterization]] resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its [[complement (graph theory)|complement]] as an [[induced subgraph]]. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.
According to the strong perfect graph theorem, the perfect graphs have a forbidden graph characterization resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its complement as an induced subgraph. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.<ref>{{citation
According to the strong perfect graph theorem, the perfect graphs have a forbidden graph characterization resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its complement as an induced subgraph. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.
根据强完美图定理，完美图具有类似于二分图的禁止图特征Forbidden graph characterization：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为导出子图时，图才是完美的。二分图，其线图以及补图构成了完美图五种基本类别中的四个，被用于证明了强完美图定理。
根据强完美图定理，完美图具有类似于二分图的禁止图特征Forbidden graph characterization：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为导出子图时，图才是完美的。二分图，其线图以及补图构成了完美图五种基本类别中的四个，被用于证明了强完美图定理。
| year = 2009}}.</ref>
| year = 2009}}.</ref>
2009} . </ref >
2009} . </ref >
===Odd cycle transversal===
===Odd cycle transversal===