二分图

最大匹配

网络流建图

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

Hall 定理

存在完美匹配的充要条件是：对于左半边的任意一个子集，它们映射到右半边的大小都大于等于它们自己的大小。

最小点覆盖

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

最大独立集

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