7,129
个编辑
更改
→柯尼希定理和完美图 Kőnig's theorem and perfect graphs
===柯尼希定理和完美图 Kőnig's theorem and perfect graphs ===
===柯尼希定理和完美图 Kőnig's theorem and perfect graphs ===
在二分图中，''' 最小顶点覆盖Minimum vertex cover'''（顶点数）等于''' 最大匹配数Maximum matching'''(边数)；这就是''' 柯尼希定理Kőnig's theorem'''。<ref>{{citation | author = Kőnig, Dénes | title = Gráfok és mátrixok | journal = Matematikai és Fizikai Lapok | volume = 38 | year = 1931
在二分图中，''' 最小顶点覆盖 Minimum vertex cover'''（顶点数）等于''' 最大匹配数 Maximum matching'''(边数)；这就是''' 柯尼希定理 Kőnig's theorem'''。<ref>{{citation | author = Kőnig, Dénes | title = Gráfok és mátrixok | journal = Matematikai és Fizikai Lapok | volume = 38 | year = 1931
| pages = 116–119}}.</ref><ref>{{citation | last1 = Gross | first1 = Jonathan L. | last2 = Yellen | first2 = Jay | edition = 2nd | isbn = 9781584885054 | page = 568 | publisher = CRC Press | series = Discrete Mathematics And Its Applications | title = Graph Theory and Its Applications
| pages = 116–119}}.</ref><ref>{{citation | last1 = Gross | first1 = Jonathan L. | last2 = Yellen | first2 = Jay | edition = 2nd | isbn = 9781584885054 | page = 568 | publisher = CRC Press | series = Discrete Mathematics And Its Applications | title = Graph Theory and Its Applications
| url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568 | year = 2005}}.</ref> 该定理的另一种等价形式是，''' 最大独立集Maximum independent set'''（顶点数）加上最大匹配数等于顶点的数量。在任意没有孤立顶点的图中，''' 最小边覆盖Minimum edge cover'''（边数）加上最大匹配数等于顶点数。<ref>{{citation | last1 = Chartrand | first1 = Gary | last2 = Zhang | first2 = Ping | isbn = 9780486483689 | pages = 189–190 | publisher = Courier Dover Publications | title = A First Course in Graph Theory | url = https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189 | year = 2012}}.</ref>于是，将以上等式与柯尼希定理相结合，得出以下事实：在二分图中，最小边覆盖数值等于最大独立集数值，最小边覆盖数值加上最小顶点覆盖数值等于顶点数。
| url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568 | year = 2005}}.</ref> 该定理的另一种等价形式是，''' 最大独立集 Maximum independent set'''（顶点数）加上最大匹配数等于顶点的数量。在任意没有孤立顶点的图中，''' 最小边覆盖 Minimum edge cover'''（边数）加上最大匹配数等于顶点数。<ref>{{citation | last1 = Chartrand | first1 = Gary | last2 = Zhang | first2 = Ping | isbn = 9780486483689 | pages = 189–190 | publisher = Courier Dover Publications | title = A First Course in Graph Theory | url = https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189 | year = 2012}}.</ref>于是，将以上等式与柯尼希定理相结合，得出以下事实：在二分图中，最小边覆盖数值等于最大独立集数值，最小边覆盖数值加上最小顶点覆盖数值等于顶点数。
另一类相关特性与''' 完美图Perfect graph'''有关：每个二分图及其补图、线图、线图的补图均为完美图。其实关于二分图的完美性很容易就可以看出来（它们的色数为2，最大的团数同样为2），但是二分图的补图完美性的判定更简单些，且可以看作是柯尼希定理的另一种表述。其实在定义完美图这一概念的初期，它是作为其中之一的论证结果而存在的。<ref>{{citation|title=Modern Graph Theory|volume= 184 |series= Graduate Texts in Mathematics|author=Béla Bollobás|publisher =Springer|year= 1998|isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> 同时完美图线图的补图完美性也是作为柯尼希定理的另一种表述，线图的完美性陈述了比较早期的柯尼希定理，即每一个二分图的着色边，其色数都等于其最大节点度数。
另一类相关特性与''' 完美图 Perfect graph'''有关：每个二分图及其补图、线图、线图的补图均为完美图。其实关于二分图的完美性很容易就可以看出来（它们的色数为2，最大的团数同样为2），但是二分图的补图完美性的判定更简单些，且可以看作是柯尼希定理的另一种表述。其实在定义完美图这一概念的初期，它是作为其中之一的论证结果而存在的。<ref>{{citation|title=Modern Graph Theory|volume= 184 |series= Graduate Texts in Mathematics|author=Béla Bollobás|publisher =Springer|year= 1998|isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> 同时完美图线图的补图完美性也是作为柯尼希定理的另一种表述，线图的完美性陈述了比较早期的柯尼希定理，即每一个二分图的着色边，其色数都等于其最大节点度数。
根据''' 强完美图定理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| s2cid = 119151552 }}.</ref>
<br>
=== 度相关问题===
=== 度相关问题===