二分图 最小点覆盖==最大匹配？？？

假设最大匹配为M。

首先，最小覆盖点集一定>=M:
因为这M条匹配边是两两不共点的，所以光是覆盖这M条已经就需要M个点了。



接下来证明可以构造M个点来覆盖所有的边。构造方法如下：
假设二分图已经求出最大匹配了。
首先从左边每一个未匹配的点出发，走一条“未匹配边-已匹配边-未匹配边-已匹配边………已匹配边”的交错路出来（由于未匹配边的左端点没被匹配过，如果右端点也是未匹配点，那么完全可以把这条边算作一条新的匹配边，
则不满足上面“假设二分图已经求出最大匹配了”，显然最短的交错路也应该是“未匹配边-已匹配边”），

于是得到交错路径上所有未匹配的边都是从左到右的，而已匹配的边是从右到左的。

我们把这个交错路径上的所有点（左点和右点）都标记掉。
当左边每个未匹配点都如上操作完了以后（标记了交错路集上的所有点），我们选出左边所有未标记点和右边所有已标记点。那么这个点集合就是我们构造的最小点覆盖集。下面是证明：

1.首先证明这样构造的点集是M个点：
 左边未标记的点一定是已匹配的点了:因为每个我们已经从左边所有未匹配的点为起点做了以上的标记操作了。
（a）而且每条匹配边，如果右端点被选入了点集，那么它一定被标记了（在交错路上），那么它所匹配的左端点也被标记了（也在交错路上）（由上面“而已匹配的边是从右到左的”得到），所以左端点不会被选入点集了。
（a）的逆否命题得左边未被标记的匹配点，它对应的匹配边的右端点一定没被标记（没被选入点集）。
因此我们我们选取的左边所有未标记点和右边所有已标记点刚好是这M条匹配边的端点，所以是M个。




2.然后证明这样构造的M个点是可以覆盖所有边的：
显然任何边只要左端点是未标记的或者右端点是已标记的那么都已经能被所选点集覆盖了。那么还剩只剩下一种可能未被覆盖的边了：左端点已标记并且右端点未被标记的边。
那么这样的边图中存在吗？
答案是不存在的。
假设这样的边是未匹配边，（由上面“未匹配的边都是从左到右的”）,左边的点被标记（在交错路上），那么右端点一定也在交错路上（被标记了）
假设这样的边是已匹配的边，（由上面“而已匹配的边是从右到左的”）,右端点都不在交错路上（未被标记），左端点就不可能在交错路上（当然不可能被标记了）。

因此这样构造M个点是可以覆盖所有边的。

木有了···

• Re:给自己理下思路，也分享给大家 (1110) laserss 2012-08-13 12:13:14