网络流(2)：正确性证明

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为Ford-Fulkerson算法的正确性证明。

最大流最小割定理

最小割问题

• 割的定义：给定带权图 $G = (V, E, c)$ 及顶点对 $s, t \in V$，一个 $s$-$t$ 割将 $V$ 划分为两个子集 $L$ 和 $R$，满足 $s \in L$ 和 $v \in R$
• 割的值：$c(L, R) = \sum_{(u, v) \in E, u \in L, v \in R} c(u, v)$
• 最小割问题：给定带权图 $G = (V, E, c)$ 和顶点对 $s, t \in V$，要求找到所有可能的 $s$-$t$ 割中，​值最小的割​（即最小割）

定理陈述

• 定理内容：最大流等于最小割，即

$$\max_{f} v(f) = \min_{L, R} c(L, R)$$

定理证明

• Lemma 1：对任意流 $f$ 和任意割 $\{L, R\}$，$v(f) \le c(L, R)$
  • 含义：任意割的值是任意流的值的上界
  • Claim：$v(f) = f_{ou}(L) - f_{in}(L)$
  • $v(f) \le f_{ou}(L) = \sum_{(u, v) \in E, u \in L, v \in R} f(u, v) \le \sum_{(u, v) \in E, u \in L, v \in R} c(u, v) = c(L, R)$
• Lemma 2：存在一个割 $\{L, R\}$ 使得 Ford-Fulkerson 算法输出的流 $f$ 满足 $v(f) = c(L, R)$
  • 可以推出最大流最小割定理及 Ford-Fulkerson 算法正确性
  • 令 $L$ 表示 $G^f$ 中从 $s$ 可达的顶点集合
  • Claim 1：$f_{ou}(L) = c(L, R)$
  • Claim 2：$f_{in}(L) = 0$ （贪心不能保证）
  • 从而 $v(f) = f_{ou}(L) - f_{in}(L) = c(L, R)$

最小割算法

1. ​求解最大流 $f$ 并​构造残留网络 $G^f$
2. ​令 $L$ = 在 $G^f$ 中从 $s$ 可达的顶点集合，$R$ = $V \setminus L$
3. 返回 $\{L, R\}$

应用：霍尔婚姻定理

定理陈述

• 内容：设二分图 $G = (A, B, E)$ 存在大小为 $|A|$ 的匹配当且仅当 $\forall S \subseteq A, |S| \leq |N(S)|$，其中 $N(S)$ 表示与 $S$ 中顶点直接相连的 $B$ 中顶点的集合
• 解读：霍尔婚姻定理给出了二分图存在完美匹配的充要条件

定理证明

• 必要性（$\Rightarrow$）：反证法，比较显然
• 充分性（$\Leftarrow$）：反证法，假设条件成立但最大匹配大小 $M < |A|$
  1. 由整数流定理，最大匹配 $M$ 对应流网络的最大流值 $v(f) = M$
  2. 由最大流最小割定理，存在值为 $M$ 的最小割值
  3. 最小割 $\{L, R\}$ 的可能情况：
     • Case 1：$L$ 仅包含源点 $s$，此时割值为 $|A|$
     • Case 2：$R$ 仅包含汇点 $t$，此时割值为 $|B|$，则 $|A| \le N(A) \le |B| < |A|$，矛盾
     • Case 3：

注：本文中所有图片均来自张宇昊老师的课程PPT。