二分图

最大匹配

二分图最大匹配可以转化成网络流：源点与左半边连边，汇点与右半边连边，边权全部为 $1$。则最大匹配就等于最大流。

最小点覆盖

选择一些点，满足二分图的每条边都至少有一个顶点被选中。问最少选多少个点。答案等于最大匹配数。

最大独立集

选择一些点，满足二分图中不存在两端点都被选的边。答案等于 $n-最小点覆盖$。