柯尼希定理 (图论)

在图论中， 柯尼希定理是指二部图的最大的匹配数与最小的顶点覆盖数相等。该定理以犹太裔匈牙利数学的名字命名。1931年，匈牙利数学家艾蓋瓦里·耶內独立发现了该定理在加权图的情形下更一般的形式。

 匹配与覆盖 
图的顶点覆盖是指它的一个顶点集，该图的每一条边都至少有一个端点在这个顶点集中。如果该图没有一个点数更少的顶点覆盖，则称其为最小顶点覆盖。Called a covering and a minimum covering respectively by , p. 73.

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

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

 定理的陈述 
在任意二部图中，最大匹配的边数等于最小顶点覆盖的顶点数。 , Theorem 5.3, p. 74; .

 证明 
设是一个最大匹配，因为顶点覆盖大于等于匹配集的大小，因此我们只需构造一个大小为的顶点覆盖。构造如下：

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

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

 参考文献 

 参考 

 .
 .
 .
 .

 .
 .
 .
 .
 .
Category:包含证明的条目