（初学绕路，名词都默认）
特别牛逼的konig：
二分图中，最大匹配==最小点集覆盖
基本记住这个就行了。
证明是构造性的，写出一个正确的算法，然后证明它执行完就得到了最小点集覆盖，并且等于匹配数。
算法：
- 匈牙利
- 从右边，从未配节点继续找增广路，肯定找不到，但找到了一个个V，W，VW，WW形的不完整增广路。
- 将不完整增广路上的点都染黑色。
- 取左边黑点，右边白点。
证明1：
要证这样取得的点数恰为匹配数。
证明点与匹配是一一对应的。
显然左边黑点都对应一条匹配边，且匹配边右侧也为黑色。
右边白点向左连的边一定有一条匹配边且不能构成V字路， 左侧为白色。
（即把匹配边分成两类，属于V字路，不属于V字路，属于的染左边，不属于染右边）
证明2：
要证覆盖了所有边。
把边分两类：
匹配边，再分两类，都一定覆盖了。
未配边，也分两类，都一定覆盖了。
证明3：
M即是最小覆盖。
废话。
证毕
（也可以直接用对偶定理）
推论：最大独立集 = G - 匹配数
夹挤。
小于等于G - 匹配，匹配两个只能选一个。
大于等于G - 匹配，最小覆盖的补集是独立集。
PS：最小路径覆盖 = G - 匹配数 右侧（还是左侧。。）反正未配点都是终点