#55 运筹学

柯尼希定理由 XDénes Kőnig 于1931年提出的图论领域的定理，用于说明在二分图中最小点覆盖的点数于最大匹配数的相等性。此外Jenő Egerváry在同年同样独立地将其提出，并拓展到了有权图的范围。

下面的证明提供了一种从最大匹配构造最小顶点覆盖的方法。
设G=(V,E)是一个二部图，设L,R是顶点集V的两个部分。假设M是G的一个最大匹配。在一个顶点覆盖中，没有一个顶点可以覆盖M的一条以上的边(M是一个匹配，所以不存在边的半重叠情况)，所以如果可以被构造出一个有|M|个顶点的顶点覆盖，那么它一定是一个最小覆盖。 [1]
下面我们构造一个上述顶点覆盖。设U是顶点集L中未被匹配的顶点的集合（U可能是空集，此时L中的所有顶点都在匹配M中）。设顶点集Z是顶点集U中的顶点通过M交错路相连点的集合。如下关系式取顶点集K：
K = ( L \ Z ) ∪ ( R ∩ Z )
对于边集E中的任意边e , 边e如果不是一个M交错路的一部分，则它的左顶点属于顶点集K。接下来我们证明这一点。如果e是匹配M中的边但不在M交错路中，那么它的左顶点不可能在M交错路中（因为根据匹配的定义，两条同一匹配中的边不能共享一个顶点），也就是说e的左顶点属于L \ Z。在另一种情况中，e既不属于匹配M也不在M交错路中，那么显然e的左端点不能在M交错路中，否则这条M交错路可以通过添加边e进行扩展。因此，K是一个顶点覆盖。 [1]
此外，K中的每个顶点都是一条匹配边的顶点。这是因为L \ Z中的每个顶点都是匹配的。而 R∩Z 中的每个顶点也必须是匹配的，因为如果存在一条与未匹配的顶点交替的M交错路，那么通过删除该路径上匹配的边，在原有位置上添加未匹配的边来改变匹配，会增加匹配的大小。然而，任何匹配中的边都不能有两个端点都在K中。 [1]
因此，K是一个最小的顶点覆盖。