查看“︁柯尼希定理 (图论)”︁的源代码


[[File:Koenigs-theorem-graph.svg|thumb|例如，在图中的[[二分图|二部图]]中，最大匹配（蓝边）和最小顶点覆盖（红点）数均为 6。]]
在[[图论]]中， '''柯尼希定理'''是指[[二分图|二部图]]的最大的[[匹配 (图论)|匹配]]数与最小的[[頂點覆盖問題|顶点覆盖]]数相等。该定理以犹太裔匈牙利数学{{le|柯尼希·德纳什|Dénes Kőnig}}的名字命名。1931年，匈牙利数学家[[艾蓋瓦里·耶內]]独立发现了该定理在[[图论术语|加权图]]的情形下更一般的形式。

== 匹配与覆盖 ==
图的顶点[[覆盖 (图论)|覆盖]]是指它的一个顶点集，该图的每一条边都至少有一个端点在这个顶点集中。如果该图没有一个点数更少的顶点覆盖，则称其为最小顶点覆盖。<ref>Called a ''covering'' and a ''minimum covering'' respectively by {{Harvard citation text|Bondy|Murty|1976}}, p.&nbsp;73.</ref>

图的[[匹配 (图论)|匹配]]是指一个边的集合，每两条边都没有公共顶点。一个匹配称为最大匹配，如果不存在一个边数更多的匹配。<ref>{{Harvard citation text|Bondy|Murty|1976}}, p.&nbsp;70.</ref>

对于匹配的每一条边，顶点覆盖中至少有一个顶点为此边的端点，因此任何顶点覆盖集的元素个数都大于等于所有匹配集的元素个数。柯尼希定理表明对于[[二部圖|二部图]]，这两个集合元素大小相同。

== 定理的陈述 ==
<blockquote>在任意[[二分图|二部图]]中，[[最大匹配]]的边数等于[[頂點覆蓋|最小顶点覆盖]]的顶点数。 ''<ref name="thm-stmt">{{Harvard citation text|Bondy|Murty|1976}}, Theorem&nbsp;5.3, p.&nbsp;74; {{Harvard citation text|Cook|Cunningham|Pulleyblank|Schrijver|2011}}.</ref>''</blockquote>

== 证明 ==
[[File:柯尼希定理证明时用到的插图.png|thumb|如图粗线代表匹配 ''M''，红点代表集合 ''U'']]
设<math>M</math>是一个最大匹配，因为顶点覆盖大于等于匹配集的大小，因此我们只需构造一个大小为<math>|M|</math>的顶点覆盖。构造如下：

将二部图的两部分分别记为 ''A'' 和 ''B''。一个图关于匹配 ''M'' 的'''交错路'''（alternating path）是指一条从图中一个非匹配顶点出发，边在匹配集 ''M'' 与 <math>E\backslash M </math> 中交错出现的道路。<ref>{{Cite book|title=图论|last=Diestel|first=Reinhard|publisher=科学出版社|year=2020|isbn=978-7-03-064807-5|location=北京|pages=32|translator-first=青林|script-title=Graph Theory|translator-last=于}}</ref>取顶点集 ''U'' 如下：对于 ''M'' 的每条边，如果存在一条交错路终止于该边在 ''B'' 中的端点，那么该端点属于 ''U''，否则该边在 ''A'' 中的端点属于 ''U''。因爲 ''U'' 里每一个顶点都与  ''M'' 的一条边一一对应，所以<math>|U|=|M|</math>。因此我们只需要证明 ''U'' 为一个顶点覆盖。

假设有一条边 ''ab'' 没有被 ''U'' 覆盖，即 <math>a\in A, b\in B</math>都不在 ''U'' 中。如果 ''a'' 不是某一匹配的端点，那么 ''ab'' 本身就是一条从非匹配顶点出发的交错路，那么<math>b\in U</math>，矛盾。如果 ''a'' 属于某个匹配 ''ab'''，那么<math>b'\in U</math>。这样，<math>Pb'ab</math>就是一条交错路，从而<math>b\in U</math>，矛盾。

:


== 参考文献 ==
{{Reflist|30em}}

== 参考 ==

* {{Citation|last=Biggs|first=E. K.|last2=Lloyd|last3=Wilson|first3=R. J.|isbn=0-19-853916-9|pages=203–207|publisher=Oxford University Press|title=Graph Theory 1736–1936|year=1976}}.
* {{Citation|last=Cook|first=William J.|author1-link=William J. Cook|last2=Cunningham|first2=William H.|last3=Pulleyblank|first3=William R.|author3-link=William R. Pulleyblank|last4=Schrijver|first4=Alexander|author4-link=Alexander Schrijver|isbn=9781118031391|pages=48–49|publisher=John Wiley & Sons|series=Wiley Series in Discrete Mathematics and Optimization|title=Combinatorial Optimization|url=https://books.google.com/books?id=tarLTNwM3gEC&pg=PA48|volume=33|year=2011}}.
* {{Citation|last=Bondy|first=J. A.|author1-link=J. A. Bondy|last2=Murty|first2=U. S. R.|author2-link=U. S. R. Murty|isbn=0-444-19451-7|publisher=North Holland|title=Graph Theory with Applications|year=1976|url=https://archive.org/details/graphtheorywitha0000bond}}.
* {{Citation|last=Gallai|first=Tibor|author-link=Tibor Gallai|doi=10.1007/BF02020271|number=3–4|journal=[[Acta Mathematica Hungarica|Acta Mathematica Academiae Scientiarum Hungaricae]]|mr=0124238|pages=395–434|title=Maximum-minimum Sätze über Graphen|volume=9|year=1958}}.
* {{Citation|last=Göös|first=Mika|last2=Suomela|first2=Jukka|arxiv=1205.4605|doi=10.1007/s00446-013-0194-z|number=6|journal=Distributed Computing|mr=3280546|pages=435–443|title=No sublogarithmic-time approximation scheme for bipartite vertex cover|volume=27|year=2014}}
* {{Citation|last=Kőnig|first=Dénes|author-link=Dénes Kőnig|journal=Matematikai és Természettudományi Értesítő|pages=104–119|title=Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére|volume=34|year=1916}}.
* {{Citation|last=Kőnig|first=Dénes|author-link=Dénes Kőnig|journal=Matematikai és Fizikai Lapok|pages=116–119|title=Gráfok és mátrixok|volume=38|year=1931}}.
* {{Citation|last=Lovász|first=László|author-link=László Lovász|doi=10.1016/0012-365X(72)90006-4|number=3|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|mr=0302480|pages=253–267|title=Normal hypergraphs and the perfect graph conjecture|volume=2|year=1972}}.
* {{Citation|last=Lovász|first=László|author-link=László Lovász|contribution=Minimax theorems for hypergraphs|doi=10.1007/BFb0066186|place=Berlin|mr=0406862|pages=111–126|series=Lecture Notes in Mathematics|volume=411|publisher=Springer|title=Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross)|year=1974}}.
* {{Citation|last=Storer|first=J. A.|isbn=9780817642532|publisher=Springer|series=Progress in Computer Science and Applied Logic Series|title=An Introduction to Data Structures and Algorithms|year=2001}}.
[[Category:包含证明的条目]]