一些笔记：
一些关系
二分图匹配大小 = 最小点覆盖大小 = $|V|$ - 二分图最大独立集。
DAG 最小路径覆盖 = $|V|$ - 拆点图注最大匹配 = 偏序集最长反链（即在 DAG 上选出最大的两两不可到达的点集）。
什么是拆点图？
对于 DAG 中每一条边 $u \rightarrow v$，我们在新图中连：$u_r \rightarrow v_l$，则形成了一个二分图。这个二分图即原 DAG 的拆点图。
Hall 定理：
邻集定义：
$$
N(S) = { v \in Y \mid \exists u \in S,\ (u,v) \in E }
$$
$N(S)$：集合 $S$ 的邻集，即 $S$ 中所有顶点能一步到达的邻居的集合。
$S$：左侧顶点集合 $X$ 的任意一个子集。
$Y$：二分图右侧的顶点集合。
$E$：二分图中所有边的集合。
霍尔定理：
$$
\forall S \subseteq X,\quad |S| \le |N(S)|
$$
$|S|$：集合 $S$ 中顶点的个数。
$|N(S)|$：集合 $N(S)$ 中顶点的个数。
König-Hall 公式（最大匹配数）：
$$
\nu(G) = |X| - \max_{Ss \subseteq X} \big( |S| - |N(S)| \big)
$$
$\nu(G)$：最大匹配大小。
$|X|$：左侧顶点总数。
$\max_{S \subseteq X}$：在所有子集 $S$ 中取最大值。
缺陷形式：
$$
\delta = \max_{S \subseteq X} \big( |S| - |N(S)| \big)
$$
$$
\nu(G) = |X| - \delta
$$
$\delta$：缺陷值，必须放弃的最少顶点数。
Comments NOTHING