柯尼希定理 (图论)

在图论中， 柯尼希定理是指二部图的最大的匹配数与最小的顶点覆盖数相等。该定理以犹太裔匈牙利数学柯尼希·德纳什（英语：Dénes Kőnig）的名字命名。1931年，匈牙利数学家艾盖瓦里·耶内独立发现了该定理在加权图的情形下更一般的形式。

例如，在图中的二部图中，最大匹配（蓝边）和最小顶点覆盖（红点）数均为 6。

匹配与覆盖

图的顶点覆盖是指它的一个顶点集，该图的每一条边都至少有一个端点在这个顶点集中。如果该图没有一个点数更少的顶点覆盖，则称其为最小顶点覆盖。^[1]

图的匹配是指一个边的集合，每两条边都没有公共顶点。一个匹配称为最大匹配，如果不存在一个边数更多的匹配。^[2]

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

定理的陈述

在任意二部图中，最大匹配的边数等于最小顶点覆盖的顶点数。 ^[3]

证明

如图粗线代表匹配 M，红点代表集合 U

设${\displaystyle M}$是一个最大匹配，因为顶点覆盖大于等于匹配集的大小，因此我们只需构造一个大小为${\displaystyle |M|}$的顶点覆盖。构造如下：

将二部图的两部分分别记为 A 和 B。一个图关于匹配 M 的交错路（alternating path）是指一条从图中一个非匹配顶点出发，边在匹配集 M 与 ${\displaystyle E\backslash M}$ 中交错出现的道路。^[4]取顶点集 U 如下：对于 M 的每条边，如果存在一条交错路终止于该边在 B 中的端点，那么该端点属于 U，否则该边在 A 中的端点属于 U。因为 U 里每一个顶点都与 M 的一条边一一对应，所以${\displaystyle |U|=|M|}$。因此我们只需要证明 U 为一个顶点覆盖。

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

参考文献

1. Called a covering and a minimum covering respectively by Bondy & Murty (1976), p. 73.
2. Bondy & Murty (1976), p. 70.
3. Bondy & Murty (1976), Theorem 5.3, p. 74; Cook et al. (2011).
4. 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.