转自：http://blog.sina.com.cn/s/blog_51cea4040100h152.html
想当年,ccy学二分图匹配的时候学完匈牙利算法，做了一个place the robts后，就没弄了，这次，看吴老师给高二新做的ppt，才知道，自己学到的东西又是多么滴少。ccy哭~~~~~~~~~~
（不要安慰我）~~~~
当再看ppt的一道题下有个结论最小覆盖点==最大匹配数时，就无语了。原因有二，其一，我以前听都没听过，其二，现在感觉是那么回事，但是，又想问为什么。
先说一下，什么叫做最小覆盖点。
在一个二分图中，一个x部或y部的覆盖点可以覆盖与之相连的所有线段，选择一些点，使得覆盖所有线段，点数最少。
König定理：最小覆盖点数==最大匹配数
我有两个证明。
***********************************************************************************************
证明一：
首先，我们要抓住二分图最大匹配后图的特点，此时，不存在增广路。如下图所示，该图为不完整的最大匹配后的二分图：
红点为匹配点，蓝点为未匹配点。
对于一个点而言，他所连接的点有这三种情况：
1、只连接了红点；
2、只连接了蓝点；
3、连接了红点和蓝点。
在上面的图中，x与y是所连接的边是匹配边。x连接了红点和蓝点，这个时候，y所连接的点一定没有蓝点，如果有，就是一条新的增广路，那么该图就不是最大匹配图了。
另一天更明显，就是在最大匹配图中 不会出现一条边同时连接着两个蓝点。
那么，对于一条边而言，只有两种情况：
1、两端的点是红点；
2、两端的点一点是红色，一点是蓝色。
可知，一条边上，一定有红点，那么，我们就选择红点作为覆盖点。
对于上面的匹配边xy，我们无论是选择x还是y都可以覆盖xy这条边，但是对于图中的蓝点而言，只能选择x作为覆盖点去覆盖那条边，这样，我们就选择x作为覆盖点，它所覆盖的边中，既包括了与他相连的那些蓝点的边，也包括了xy这条匹配边。因为y点没有蓝色连接点，所以，y不是必须选择的覆盖点，它与那些红点相连的边都可以选择那些红点来覆盖边。所以，对于一条匹配边而言，我们只需要选择其中一个点就可以覆盖完整个二分图里的边了。
所以最小覆盖点数等于最大匹配。
**************************************************************************************************
证明二：
这是Matrix67的证明，ccy用自己的语言写一下，O(∩_∩)O~~~~~~~~~~~~
Matrix67证明的链接：http://www.matrix67.com/blog/?s=%E6%9C%80%E5%B0%8F%E8%A6%86%E7%9B%96%E7%82%B9
对于一个已经匹配好的二分图，我们进行如下操作，就可以找出一些点，使之覆盖所有的边。
规则如下：对于Y部所有未被匹配的点，我们就从它出发，找“交错轨”，这里的“交错轨”和匹配时的交错轨很相似，他们一样的地方都是从一个未被匹配的点出发，按着颜色交替搜下去，他们不同的是，匹配的交错轨最终要在另一个部里找到一个未匹配的点，这里的“交错轨”，没有办法找到未被匹配的点，我们就一直搜下去，知道搜不动，既搜到以前又搜过的。把搜这条“交错轨”所经过的点我们都做上标记。最后，覆盖点就是X部被标记了的点和Y部没有标记的点。
如图所示：
从Y部的未被匹配的点出发，顺着蓝色线所标记的路，经过的点都做上标记，最后，选取X部做了标记的点和Y部没有做标记的点，既图中的蓝点。
从图中，直接看出，通过这种方法可以选取最大匹配数量的点覆盖完了所有的边。
首先我们要明白按这种方法标记的特点：
1、出发的第一条边是灰色，结束的边是黑色；
2、X的被标记的点是从Y到X走灰边；
3、Y被标记的点是未匹配的点或者从X到Y是黑色的边的点。
我们看X部，它的点，有3种情况：
1、只有一条黑边；
2、只有灰边；
3、黑边灰边都有。
情况1只有一条黑边的点不可能被标记，由标记特点2可知。
情况2只有灰边的点不可能被标记到。如果被标记，那么这条边就是结束边，而“交错轨”的结束边是黑色，由特点1知。
情况3黑边灰边都有，这样的X点可能被标记，因为它有进有出。
如果我们把X部标记了的点去掉后，只可能有下面三种情况：
第一种：
这个时候，只剩情况1、2的X部点，他们所连接的Y部点都是没有被标记的，最后，我们选择Y部点作为覆盖点时，整个图的边就覆盖完了。
第二种：
虽然上图有X点同时连接着灰边和黑边，但是，选择上图的两个蓝点后，就可以把所有的边覆盖完。
第三种：
第一种和第二种的综合版
这个，纯属搞笑，O(∩_∩)O~。
好了，这样我们证明了通过这种方法选择的点一定可以覆盖完所有边。
下面，还需要证明，这样的覆盖点等于最大匹配数。
对于每条匹配边而言，它都有X部和Y部的匹配点。我们通过标记后，对于走过的匹配边而言，我们选择的是X部的点，对于走过的匹配边而言，我们选择的是Y部的点，所以加起来就是匹配数。
那么，这就一定是最小覆盖点数吗？
答案是显而易见的，因为，每条匹配边之间都是独立的，没有重合的X部点或者Y部点，所以，只对于匹配边而言，每条匹配边都需要一个覆盖点，才能覆盖这条边。
所以，最小覆盖点数等于最大匹配数。
**************************************************************************************************
忽忽~ ccy终于写完了……
今天天气很好，出太阳了，爬山去，O(∩_∩)O~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~