柯尼希定理 (图论)
在图论中， 柯尼希定理是指二部图的最大的匹配数与最小的顶点覆盖数相等。该定理以犹太裔匈牙利数学柯尼希·德纳什的名字命名。1931年，匈牙利数学家艾盖瓦里·耶内独立发现了该定理在加权图的情形下更一般的形式。
匹配与覆盖
编辑图的顶点覆盖是指它的一个顶点集，该图的每一条边都至少有一个端点在这个顶点集中。如果该图没有一个点数更少的顶点覆盖，则称其为最小顶点覆盖。[1]
图的匹配是指一个边的集合，每两条边都没有公共顶点。一个匹配称为最大匹配，如果不存在一个边数更多的匹配。[2]
对于匹配的每一条边，顶点覆盖中至少有一个顶点为此边的端点，因此任何顶点覆盖集的元素个数都大于等于所有匹配集的元素个数。柯尼希定理表明对于二部图，这两个集合元素大小相同。
定理的陈述
编辑证明
编辑
设 是一个最大匹配，因为顶点覆盖大于等于匹配集的大小，因此我们只需构造一个大小为 的顶点覆盖。构造如下：
将二部图的两部分分别记为 A 和 B。一个图关于匹配 M 的交错路（alternating path）是指一条从图中一个非匹配顶点出发，边在匹配集 M 与 中交错出现的道路。[4]取顶点集 U 如下：对于 M 的每条边，如果存在一条交错路终止于该边在 B 中的端点，那么该端点属于 U，否则该边在 A 中的端点属于 U。因为 U 里每一个顶点都与 M 的一条边一一对应，所以 。因此我们只需要证明 U 为一个顶点覆盖。
假设有一条边 ab 没有被 U 覆盖，即 都不在 U 中。如果 a 不是某一匹配的端点，那么 ab 本身就是一条从非匹配顶点出发的交错路，那么 ，矛盾。如果 a 属于某个匹配 ab'，那么 。这样， 就是一条交错路，从而 ，矛盾。
参考文献
编辑- ^ Called a covering and a minimum covering respectively by Bondy & Murty (1976), p. 73.
- ^ Bondy & Murty (1976), p. 70.
- ^ Bondy & Murty (1976), Theorem 5.3, p. 74; Cook et al. (2011).
- ^ Diestel, Reinhard. 图论 Graph Theory. 由于, 青林翻译. 北京: 科学出版社. 2020: 32. ISBN 978-7-03-064807-5.
参考
编辑- Biggs, E. K.; Lloyd; Wilson, R. J., Graph Theory 1736–1936, Oxford University Press: 203–207, 1976, ISBN 0-19-853916-9.
- Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander, Combinatorial Optimization, Wiley Series in Discrete Mathematics and Optimization 33, John Wiley & Sons: 48–49, 2011, ISBN 9781118031391.
- Bondy, J. A.; Murty, U. S. R., Graph Theory with Applications, North Holland, 1976, ISBN 0-444-19451-7.
- Gallai, Tibor, Maximum-minimum Sätze über Graphen, Acta Mathematica Academiae Scientiarum Hungaricae, 1958, 9 (3–4): 395–434, MR 0124238, doi:10.1007/BF02020271.
- Göös, Mika; Suomela, Jukka, No sublogarithmic-time approximation scheme for bipartite vertex cover, Distributed Computing, 2014, 27 (6): 435–443, MR 3280546, arXiv:1205.4605
, doi:10.1007/s00446-013-0194-z - Kőnig, Dénes, Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére, Matematikai és Természettudományi Értesítő, 1916, 34: 104–119.
- Kőnig, Dénes, Gráfok és mátrixok, Matematikai és Fizikai Lapok, 1931, 38: 116–119.
- Lovász, László, Normal hypergraphs and the perfect graph conjecture, Discrete Mathematics, 1972, 2 (3): 253–267, MR 0302480, doi:10.1016/0012-365X(72)90006-4.
- Lovász, László, Minimax theorems for hypergraphs, Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), Lecture Notes in Mathematics 411, Berlin: Springer: 111–126, 1974, MR 0406862, doi:10.1007/BFb0066186.
- Storer, J. A., An Introduction to Data Structures and Algorithms, Progress in Computer Science and Applied Logic Series, Springer, 2001, ISBN 9780817642532.
