二分图匹配相关性质(知识点整理)

思路来源

http://www.matrix67.com/blog/archives/116

https://blog.csdn.net/ACMer_ZP/article/details/78570926

https://blog.csdn.net/huangshuai147/article/details/51087275

https://www.cnblogs.com/icode-girl/p/5418461.html

心得

有些东西真是学了又学学了又忘忘了又学

依稀记得自己去年就在学这个

最小点覆盖 最小边覆盖 最大匹配 最小路径覆盖 最大独立集

以下除最小路径覆盖指DAG外&＃xff0c;其余皆为二分图

结论

1.最小点覆盖&＃61;最大匹配 

2.最大独立集&＃61;总点数-最大匹配

3.最小边覆盖&＃61;总点数-最大匹配

4.DAG不相交最小路径覆盖&＃61;DAG顶点数-对应二分图最大匹配

5.无向图最大匹配&＃61;最大匹配/2

输出最小点覆盖方案&＃xff1a;https://blog.csdn.net/Code92007/article/details/83688492

输出最大独立集方案&＃xff1a;https://blog.csdn.net/Code92007/article/details/98205680

证明

1.最小点覆盖

用最少的点&＃xff0c;覆盖所有的边&＃xff0c;全为孤立顶点(没边)输出0

证明&＃xff1a;Konig定理

http://www.matrix67.com/blog/archives/116

2.最大独立集

选中最多的点&＃xff0c;使得两两之间都没有边&＃xff0c;

联合结论1&＃xff0c;即证最大独立集&＃61;总点数-最小点覆盖

设最小点覆盖点集为S&＃xff0c;S的大小为n&＃xff0c;全集为U&＃xff0c;

记没有在S中的点构成的集合为T(即U-S)

①若T内存在两点之间有边E&＃xff0c;则E没有被S内的点覆盖&＃xff0c;矛盾&＃xff0c;故T内两两之间没有边

①说明&＃xff0c;T是一个合法解&＃xff0c;所以答案不小于T&＃xff0c;ans>&＃61;|T|

②若T还可扩充&＃xff0c;则必至少选一点v&＃xff0c;v属于S&＃xff0c;且v与T内所有点之间都没有边

这说明&＃xff0c;与v相连的所有边&＃xff0c;另一端的顶点都是集合S-v里的点&＃xff0c;

同样表明&＃xff0c;与v相连的所有边&＃xff0c;被S-v的点覆盖了&＃xff0c;因此&＃xff0c;在最小点覆盖中&＃xff0c;v多余&＃xff0c;

这说明&＃xff0c;S-v构成一个新的最小点覆盖&＃xff0c;与S是最小点覆盖&＃xff0c;矛盾

②说明&＃xff0c;T不可扩充&＃xff0c;所以答案不大于T&＃xff0c;ans<&＃61;|T|

①②表明&＃xff0c;ans&＃61;|T|

3.最小边覆盖

用最少的边&＃xff0c;覆盖所有的点&＃xff0c;有孤立顶点时不存在

证明&＃xff1a;

由于最大匹配边能覆盖两个点&＃xff0c;而非匹配边只能覆盖一个点&＃xff0c;所以优先用最大匹配里的边

设点数为n&＃xff0c;最大匹配为m&＃xff0c;则m条边覆盖2*m个点&＃xff0c;

其余n-2*m个点只能由n-2*m条非匹配边覆盖&＃xff0c;

故共计n-m条边&＃xff0c;为点数-最大匹配

4.DAG不相交最小路径覆盖

用若干条不相交(不共点不共边)的路径&＃xff0c;覆盖所有的点

图片来源&＃xff1a;https://www.cnblogs.com/icode-girl/p/5418461.html

左边DAG图&＃xff0c;一个点拆成出点和入点两个点&＃xff0c;二分图左侧为出点&＃xff0c;右侧为入点

原图中1到3的连边&＃xff0c;对应二分图中出点1到入点3的连边&＃xff0c;

设DAG中顶点数为n&＃xff0c;最大匹配数为m&＃xff0c;且认为最大匹配的边有方向&＃xff0c;从左指向右&＃xff0c;

那么最大匹配上左边的点&＃xff0c;因为有后继&＃xff0c;所以不可能成为一条路径中的终点&＃xff0c;

而其他的点&＃xff0c;因为没有后继&＃xff0c;所以只能成为出度为0的点&＃xff0c;即终点&＃xff0c;

终点的个数&＃xff0c;即为路径的条数&＃xff0c;所以&＃xff0c;左侧剩下了n-m个点&＃xff0c;也就对应了n-m条路径

5.无向图最大匹配&＃61;最大匹配数/2

无向图因为左侧连向右侧有边&＃xff0c;右侧连向左侧也有边

所以不论左侧右侧&＃xff0c;统统求一遍最大匹配&＃xff0c;

最大匹配边&＃xff0c;左边被计一次右边被计一次&＃xff0c;故除以2