一、定义
网络流是一个特殊的有向完全图，每一条边有一个限制，叫做“容量”。
在之后的讨论中，所有的“图”默认是有向图，特殊标注除外。
| 约定符号 | 限定范围 |
|---|---|
| $u,v$ | 点 |
| $V$ | 图的点集 |
| $E$ | 图的边集 |
| $(u,v)$ | 图中的一条边 $u \to v$ |
| $X,Y$ | 二分图的点集 |
| $\text{cap}(u,v)$ | 网络流中边 $u \to v$ 的容量 |
| $\text{cost}(u,v)$ | 网络流中边 $u \to v$ 的费用 |
| $\text{cap}(u,v)=[l,r]$ | 网络流中边的上下界是 $[l,r]$ |
| $f(u,v)$ | 网络流中边 $u \to v$ 的流量 |
| $S$ | 网络流中的源点 |
| $T$ | 网络流中的汇点 |
一个合法的网络流上，每一条边还有一个“流量值”。如果一个网络流合法，通常应当满足以下要求：
- $\text{cap}(u,v) \in \mathbb N$
- $f(u,v) \leqslant \text{cap}(u,v)$
- “正反抵消”：$\forall (u,v), f(u,v) + f(v,u) = 0$
- “流量守恒”：$\forall u, \displaystyle\sum_{(u,v)} f(u, v) = 0$
- 存在一个 $S$ 和一个 $T$，不要求满足流量守恒。
| 术语 | 对象 | 类型 | 定义 | 含义 |
|---|---|---|---|---|
| 最大流 | 网络流 | 整数 | 在所有合法网络流中，$\displaystyle\sum_{(S,u)} f(S,u)$ 最大的数值 | 最大的流入流量 |
| 割 | 网络流 | 整数 | 将点集分成包含 $S$ 的 $V_S$ 和包含 $T$ 的 $V_T$，最小割 $=\displaystyle\sum_{u\in V_S, v\in V_T} f(u,v)$ | |
| 独立集 | 图 | 点集 | $\forall u, v \in $ 独立集，$u$ 与 $v$ 无连边 | 每两个点没有连边 |
| 点覆盖 | 图 | 点集 | $\forall (u, v) \in E, u \in$ 点覆盖 或 $v \in$ 点覆盖 | 每条边都被至少一个点覆盖 |
| 闭合子图 | 图 | 图 | 在原图中选择一个子图 $(V’, E’)$ 使得 $\nexists (u,v) \in E$，$u\in V’$ 且 $v \notin V’$ | 不存在指向子图外的边 |
| 路径 | DAG | 有序边集 | 对于路径 $E_{1 … k} = (u_{1 … k}, v_{1 … k})$，有 $\forall i = 2 … k, v_{i-1} = u_i$ | |
| 路径覆盖 | DAG | 路径集 | 选出若干条路径$E_1,E_2,\dots,E_m$，不存在 $e_1\in E_i, e_2\in E_j, e_1 = e_2$ | 用不交的路径覆盖所有顶点 |
| 偏序集 | DAG | DAG | $\forall (u,v),$ 如果存在路径以 $u$ 开头 $v$ 结尾，那么一定存在边 $(u,v)$ | 可以由 DAG 传递闭包得到 |
| 最长链 | 偏序集 | 点集 | $\forall(u,v),\exists (u,v)\in E \lor (v,u)\in E$ | 每两个点都可比 |
| 最长反链 | 偏序集 | 点集 | $\forall(u,v),\exists (u,v)\notin E \land (v,u)\notin E$ | 每两个点都不可比 |
三、定理
- 最大流 = 最小割
这是一个非常直接的定理，两个数值上相等。
经常用作构图，有一些题适合使用最小割思想去建图。 - 二分图的最小点覆盖 ~ 最大匹配
如何导出一个最小点覆盖呢？
给出第一个网络流建图方法：
假设二分图是 $(X,Y,E)$，
$S \xrightarrow{1}X \xrightarrow{1} Y \xrightarrow{1} T$。
令 非匹配边 为 $f(u,v)=0$（也就是残量网络中 $\text{cap}(u,v)=1$）的边），
匹配边 为 $f(u,v)=1$ 的边。
这里的最大匹配也就是所有的匹配边构成的集合。
非匹配点 为 $\forall (u,v), f(u,v)=0$ 的 $v$。
从 $Y$ 中所有的 非匹配点 出发，走 非匹配边 到 $X$，再走 匹配边 到 $Y$，不断dfs这个过程，得到所有访问过的点，即vis数组；
$Y$ 中没有访问过的点 + $X$ 中访问过的点 = 最小点覆盖。