二分图匹配
性质
完美匹配
Hall 定理：某个二分图 $G$ 的左右两部点集分别为 $V_1,V_2$，那么 $V_1$ 存在完美匹配当且仅当对于任意 $S\subset V_1$ 均有 $|S|\le|\cup_{u\in S}N(u)|$。
后者的必要性是显然的，现在证明其充分性。任取一个最大匹配，设其中与某个右部点 $v$ 相匹配的点为 $\hat v$。若存在左部点 $k$ 不在最大匹配中，构造点集 $S_0=\{k\}$ 和 $S_t=\{\hat v\mid v\in \cup_{u\in S_{t-1}}N(u)\}\cup\{k\}$（考虑到，对于任意 $u\in S_{t-1}$，任意 $v\in N(u)$ 均有与它匹配的左部点，否则总能按照集合扩展的路径构造出一条增广路使得答案增加）。
对于某个 $t$，令 $T=\{\hat v\mid v\in\cup_{u\in S_{t-1}}N(u)\}$。不难发现 $|T|=|\cup_{u\in S_{t-1}}N(u)|\ge|S_{t-1}|$，并且 $k\not\in|T|$。于是有 $|S_t|>|S_{t-1}|$，于是总存在某个 $t$ 使得 $|S_t|>|V_1|$，矛盾。
霍尔定理的一个简单推论是，一个二分图 $G$ 左右部点集为 $V_1,V_2$，其最大匹配数为 $|V_1|-\max_{S\subseteq V_1}(|S|-|N(S)|)$。
考虑这样一个图 $G'$，它在原图的基础上，向右部点中加入 $k=\max_{S\subseteq V_1}(|S|-|N(S)|)$ 个点 $T$，连向所有左部点。$G$ 满足 $\forall S,|S|-|N(S)|\le a$，则 $G'$ 满足 $\forall S,|S|-|N(S)|\le0$。根据霍尔定理，$G'$ 一定存在一个左部点的完美匹配，我们删去所有涉及 $T$ 中点的匹配，能够得到一组不小于 $|V_1|-k$ 的匹配。
而图中至少存在一个左部点集合 $|S|$ 使得 $|S|-|N(S)|=k$，对于任何一组匹配，这个集合中至少有 $k$ 个点没有匹配，所以最大匹配数不超过 $|V_1|-k$。
综上，$G$ 的最大匹配数为 $|V_1|-k$。
最小点覆盖（König 定理）
二分图中，最小点覆盖数等于最大匹配数。
首先，最大匹配的端点两两不同，所以至少需要最大匹配数的点来覆盖最大匹配的所有边。即最小点覆盖数不小于最大匹配数。
考虑依据二分图的任一最大匹配构造点覆盖。我们考察这样一条路径：
从某一未匹配的 $u_0$ 出发，到右侧一相邻节点 $v_1$，再到 $v_1$ 的匹配节点 $u_1$，再到 $u_1$ 右侧一相邻节点 $v_2$……重复这个过程直到无法再走下去，构成一条形如 $u_0\to v_1\to u_1\to v_2\cdots$ 的路径。
不难发现路径不会结束在某个右侧点 $v_n$，否则我们从原匹配中删除 $(u_1,v_1),(u_2,v_2),\cdots,(u_{n-1},v_{n-1})$，加入 $(u_0,v_1),(u_1,v_2),\cdots,(u_{n-1},v_n)$，可以构成一个比原匹配恰好大 $1$ 的匹配。
如果找出所有这样的路径，那么由左侧点中不存在于任意一条路径上的，和右侧点中存在于至少一条路径上的点构成一组点覆盖。这是显然的，如果一条边被某条路径所包含，那么它的右端点会覆盖它；如果它不被任何一条路径包含，那么它的左端点会覆盖它。
我们再证明这样构造出来的点覆盖大小等于最大匹配数。构造从该最大匹配到该点覆盖的映射 $f$：如果这条匹配边被某条路径所包含，它映射到这条边的右端点；如果这条匹配边不被任何一条路径包含，那么映射到它的左端点。
匹配边不会共用端点，所以 $f$ 是单射；根据所构造路径的性质，每个右侧点都会被它的匹配边映射到，每个左侧点也一定会存在一条匹配边（否则它会成为至少一条路径的起点），它会被这条匹配边映射到。$f$ 为双射，得证。
最小点覆盖数不会大于最大匹配数，而我们已经构造出来了一组大小等于最大匹配数的点覆盖，因此定理得证。
最大独立集
显然取任一点覆盖的补集都能唯一地得到一组独立集，因此最大独立集数等于点数减去最小点覆盖数。
最大团
最大独立集要求集合内不存在边，最大团要求集合内任意两点都存在一条边。因此一个图的最大团即其补图的最大独立集。
应用
DAG 路径覆盖
不相交链覆盖：用最少的不相交的链覆盖 DAG 上的所有点。
路径数等于点数减去边数，所以我们需要最大化连的边数。而每条边最多只能连一条入边、一条出边。所以我们用两个点分别代表这个点的“入口”和“出口”，二分图匹配。入口匹配上的点即该点在链上的前驱，入口没有匹配代表其为链起点；出口类似。
可相交链覆盖：用最少的链覆盖 DAG 上的所有点。
这里的做法很巧妙：求出原图 $G$ 的传递闭包 $G'$，$G'$ 中 $u,v$ 间有边当且仅当 $G$ 中存在路径 $u\to v$。
此时传递闭包 $G'$ 的最小不可重路径覆盖数量 $x$ 等于原图 $G$ 的可重路径覆盖数量 $y$。证明如下：
通过 $G'$ 上的不可重路径覆盖方案 $F$ 构造出 $G$ 上的可重路径覆盖是简单的，将 $F$ 中的每条路径上的每条边 $(u,v)$ 替换为 $G$ 上的路径 $u\to v$，这样不会使得路径数量改变。所以 $x\ge y$。
通过 $G$ 上的可重路径覆盖方案 $F$ 构造出 $G'$ 上的不可重路径覆盖，考虑重复以下过程直到不存在一个点被两条路径覆盖：找到这样的点 $u$ 和覆盖它的路径 $p,q$，如果 $p$ 长度为 $0$ 则将其从路径集合中删去；如果 $u$ 为 $p$ 的起点或终点，将 $u$ 从 $p$ 中删去；否则找到 $u$ 在 $p$ 中的前驱 $i$ 和后继 $j$，将 $p$ 中的边 $(i,u),(u,j)$ 替换为 $(i,j)$ 即可。这样的过程每进行一轮都会导致路径集合变小或某条路径长度减小，所以这样的过程一定能够在有限步内结束。整个过程中路径数量不会增大，所以 $x\le y$。$\Box$