写给自己复习用的，可能不太适合阅读
二分图的最小点覆盖
用最少的点覆盖二分图的所有边，即找到一个点集
，使得二分图中的每一条边都至少有一个端点属于，且
尽量小。
König 定理
二分图的最小点覆盖的点数等于最大匹配包含的边数。
从每个左部非匹配点开始再跑一次匈牙利算法，标记沿途经过的每个点，然后选择左部未被标记的点和右部被标记的点即可。
正确性证明见书P428。
但需要提到的是，左部未被标记的点是匹配点，但并非所有左部匹配点都未被标记。右部被标记的点是匹配点，但并非所有右部匹配点都被标记。
求解最小点覆盖类问题通常有一个特征，即题中内容可以抽象成二分图，每条边都必须被覆盖，求解最少的点。
二分图的最大独立集
二分图的最大独立集是指：满足点集内任意两点之间都没有边，且是
中
的子集的最大。
的最大独立集的大小等于
减去最大匹配数。
对比：
这两个题看似相似，其实求解方式完全不同。
棋盘覆盖求最大骨牌数。将相邻两个没被禁止的格子连上一条边，一条边即可对应一个骨牌。（每条边代表一个骨牌）所以要求解的是最多不产生矛盾的边数，即最大匹配。
骑士放置求解的是放置的骑士数。将没被禁止的能互相攻击到的骑士连边，我们要求解的是内部没有边相连的最大点集（每个点代表一个骑士），即最大独立集。
DAG 的最小路径点覆盖
用尽量少的不相交的简单路径覆盖有向无环图的所有顶点，这个问题被叫做最小路径点覆盖。
将的所有点拆成入点和出点，构成拆点二分图
将入点作为左部点
，出点作为右部点
。对每一条边
，在
中连接与
。减去的最大匹配数即为答案。
如果简单路径可相交，进行一次传递封包即可。
证明略。