对于二分匹配的总结

(1) 最大独立集: 在一个二分图中,选择一些顶点,使得所选择的点集中任意两个顶点之间没有边相连

最大独立集 = 顶点个数 - 最大匹配

设所有匹配了的点的集合为A，所有没有匹配的点的集合为B设(u,v)为一条匹配边，那么集合B中的点最多能和u，v中的一个点中存在边，如果两条边都存在边的话会再次产生增广路而使得它不是最大匹配。

那么对于匹配(u,v)中，如果存在与B集合中的点有边的点且这个点是u，那么抛弃u，如果不存在，那么抛弃u，v中任意一个点，就能使得剩下的点中没有边相连。

题目：hdu3829

http://blog.csdn.net/cq_pf/article/details/44310299

(2) 最小边覆盖：在一个二分图中，选择一些边，使得这些边能覆盖这个二部图的所有点

最小边覆盖 = 最大独立集

设所有匹配了的点的集合为A，所有没有匹配的点的集合为B设(u,v)为一条匹配边，那么集合B中的点最多能和u，v中的一个点中存在边，如果两条边都存在边的话会再次产生增广路而使得它不是最大匹配。

那么对于匹配(u,v)中，如果存在与B集合中的点有边的点且这个点是u,那么需要选择所有与u相连的所有边，如果不存在，则只需要选边(u,v);

题目：poj3020

http://blog.csdn.net/cq_pf/article/details/44523067

(3) 最小路径覆盖：在一个有向图中，路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联

最小路径覆盖 = 顶点个数 - 最大匹配

最小路径覆盖不需要时二部图，是DAG图

可以将一个点拆为u’,u’’,那么对于条边u----->v就可表示为u’-------v’’那么对于一条路径覆盖是由一个匹配图的匹配边构成的（如果不是一个匹配图，那么就会存在 i’-------j’’,i’-----k’’的情况，即有i----->j,i------->k的边，那么就会与路径覆盖矛盾）对于路径覆盖是在这条路径的所有匹配边的个数加1，所以最小路径覆盖 = 顶点个数 - 最大匹配。

题目：poj1548

http://blog.csdn.net/cq_pf/article/details/44422747

(4) 二分匹配求出匹配时的求必须边

题目：poj1486

http://blog.csdn.net/cq_pf/article/details/44352389

对于二分匹配的总结

原文：http://blog.csdn.net/cq_pf/article/details/44569087