一些笔记：
一些关系
二分图匹配大小 = 最小点覆盖大小 = $|V|$ - 二分图最大独立集。
DAG 最小路径覆盖 = $|V|$ - 拆点图注最大匹配 = 偏序集最长反链（即在 DAG 上选出最大的两两不可到达的点集）。
什么是拆点图？
对于 DAG 中每一条边 $u \rightarrow v$，我们在新图中连无向边：$(u_r,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