二分图最小覆盖的Konig定理及其证明(转)

二分图最小覆盖的Konig定理及其证明

二分图：

顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。

最小覆盖：

最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝最大匹配数

Konig定理：

二分图的最小顶点覆盖数等于最大匹配数。

 证明：

 为主便叙述，假设G分为左边X和右边Y两个互不相交的点集。。。。。。

假设G经过匈牙利算法后找到一个最大匹配M，则可知G中再也找不到一条增广路径。

标记右边未匹配边的顶点，并从右边未匹配边的顶点出发，按照边：未匹配->匹配->未匹配...，的原则标记途中经过的顶点，则最后一条经过的边必定为匹配边。重复上述过程，直到右边不再含有未匹配边的点。

记得到的左边已标记的点和右边未标记的点为S， 以下证明S即为所求的最小顶点集。

1。| S | == M 
    显然，左边标记的点全都为匹配边的顶点，右边未标记的点也为匹配边的顶点。因此，我们得到的点与匹配边一一对应。

2。S能覆盖G中所有的边。

       上途S中点所得到的边有以下几种情况：

       （1）左右均标记；

       （2）左右均无标记；

       （3）左边标记，右边未标记；

       若存在一条边e不属于S所覆盖的边集，则e 左边未标记右边标记。

如果e不属于匹配边，那么左端点就可以通过这条边到达（从而得到标记）；如果e属于匹配边，那么右端点不可能是一条路径的起点，于是它的标记只能是从这条边的左端点过来的左端点就应该有标记。

 

3。S是最小的覆盖。

       因为要覆盖这M条匹配边至少就需要M个点。