二分图匹配及其相关

匈牙利算法（二分图最大匹配），二分图最小点覆盖，二分图最小边覆盖，有向图最小路径覆盖，二分图最大独立集。

一些数量关系&定理

二分图最小点覆盖数 $=$ 二分图最大匹配数
二分图最小边覆盖数 $=$ 点的总数 $-$ 二分图最大匹配数
有向图最小路径覆盖数 $=$ 二分图最小边覆盖数
二分图的最大独立集数 $=$ 点的总数 $-$ 二分图最小点覆盖数
完美匹配的条件：

1. $X$的点数 $<$ $Y$的点数
2. 对于$X$的任意一个子集$a$,及其所连到的$Y$中的点集$b$,满足所有$|a| > |b|$

二分图最大独立集

定义：选一些点使其两两不相邻，这些点构成的集合为独立集。找到一个包含点数最多的独立集称为最大独立集。
定理：二分图的最大独立集数 $=$ 点的总数 $-$ 二分图最小点覆盖数
首先，我们假设最大匹配数为$n$，那至少$n$对点是相邻的，那么要删去大于等于$n$的点。其次，我们也知道最小点覆盖有$n$个，那么只删去这些点就能满足条件了（剩下的点肯定不相连），因为假如这些点间还有边，那这些边没有被最小点覆盖中的点覆盖，就不成立了。
求方案
故我们这要删去最小点覆盖，剩下的就是最大独立集。
还有另一种求方案的方法：不断的找一定在最大匹配上的点删去，剩下的就是最大独立集（最大匹配上的点一定要删去，如果删去了可能不在最大匹配上的点，那就删多了）。那如何找“一定”在最大匹配上的点呢？简单讲就是把这个点删去之后最大匹配减少了，但这样做复杂度太高，其实我们只要把左边的点标记掉，从右边的点（当作未盖点）出发找增广路即可，若无，则证明左边的点一定在最大匹配上。