二分图最大匹配

为了描述方便将两个集合分成左和右两个部分，所有匹配边都是横跨左右两个集合，可以假想成男女配对。

假设图有 个顶点， 条边。

题目描述

给定一个二分图 ，即分左右两部分，各部分之间的点没有边连接，要求选出一些边，使得这些边没有公共顶点，且边的数量最大。

增广路算法 Augmenting Path Algorithm

因为增广路长度为奇数，路径起始点非左即右，所以我们先考虑从左边的未匹配点找增广路。 注意到因为交错路的关系，增广路上的第奇数条边都是非匹配边，第偶数条边都是匹配边，于是左到右都是非匹配边，右到左都是匹配边。 于是我们给二分图 定向，问题转换成，有向图中从给定起点找一条简单路径走到某个未匹配点，此问题等价给定起始点 能否走到终点 。 那么只要从起始点开始 DFS 遍历直到找到某个未匹配点，。 未找到增广路时，我们拓展的路也称为 交错树。

性质

因为要枚举 个点，总复杂度为 。

实现

转为网络最大流模型

二分图最大匹配可以转换成网络流模型。

将源点连上左边所有点，右边所有点连上汇点，容量皆为 。原来的每条边从左往右连边，容量也皆为 ，最大流即最大匹配。

如果使用

Dinic 算法 求该网络的最大流，可在 求出。

Dinic 算法分成两部分，第一部分用 时间 BFS 建立网络流，第二步是 时间 DFS 进行增广。

但因为容量为 ，所以实际时间复杂度为 。

接下来前 轮，复杂度为 。 轮以后，每条增广路径长度至少 ，而这样的路径不超过 ，所以此时最多只需要跑 轮，整体复杂度为 。

代码可以参考

Dinic 算法 的参考实现，这里不再给出。

补充

二分图最小点覆盖（König 定理）

最小点覆盖：选最少的点，满足每条边至少有一个端点被选。

二分图中，最小点覆盖 最大匹配。

二分图最大独立集

最大独立集：选最多的点，满足两两之间没有边相连。

因为在最小点覆盖中，任意一条边都被至少选了一个顶点，所以对于其点集的补集，任意一条边都被至多选了一个顶点，所以不存在边连接两个点集中的点，且该点集最大。因此二分图中，最大独立集 最小点覆盖。

习题

参考资料

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