定义

两个点集，点集内部没有连边的图称为二分图。

二分图最大匹配

选中最多的边，满足每个点只被选到一次，即最大边匹配点。

考虑网络流建模。每个点只能用一次，\(S\) 向左边的点连一条流量为 \(1\) 的边，右边的点向 \(T\) 连一条流量为 \(1\) 的边，就可以保证这个要求。然后两个点集之间连原图的边，流量随便，反正每个点只会用一次，每条边最多也只会流 \(1\) 的流量。

使用 dinnic 算法，时间复杂度为 \(O(n\sqrt{m})\)。

二分图最小点覆盖

选中最少的点，使得所有边至少有一个端点被选中。即最小点覆盖边。

定理：二分图最小点覆盖等于最大匹配。

证明：对于一个最大匹配，一定不存在一条边，两个点都没有匹配的。因此所有边都一定至少有一个点匹配了。因此最大匹配一定是点覆盖。

假设存在一个更小的点覆盖，那么这个点覆盖一定不是最大匹配。那么这个点覆盖一定存在一条边，两个端点都没有匹配，所以这个不是点覆盖。因此最大匹配就是最小点覆盖。证毕。

直接跑网络流即可。

二分图最大独立集

待补充。