网络流(1)：算法及其应用

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为网络流算法及其应用，包括Ford-Fulkerson算法及二分图最大匹配等应用问题。

最大流问题

问题描述

• 输入：
  • ​有向图 $G(V, E)$，源点 $s$ 和汇点 $t$
  • ​对每条边 $e \in E$，定义容量 $c(e)$
• 输出：从 $s$ 到 $t$ 的最大流量

流的定义

• ​流函数：$f: E \to \mathbb{R}_{\ge 0}$，对每条边 $e \in E$ 分配流量 $f(e)$
• ​容量约束：对每条边 $e \in E$，满足 $f(e) \le c(e)$
• ​流量守恒：对任意中间节点 $u \in V \setminus \{s, t\}$，满足
  $\sum_{(v, u) \in E} f(v, u) = \sum_{(u, w) \in E} f(u, w)$（流入流量 = 流出流量）
• ​总流量：$v(f) = \sum_{(s, v) \in E} f(s, v)$

Ford-Fulkerson 算法

残留网络

• 定义：$G^f$ ，顶点集与原图相同，边集 E_f 包含两类边：
  • ​正向边：若原边 $(u, v)$ 的流量 $f(u, v) < c(u, v)$，残留容量为 $c(u, v) - f(u, v)$
  • ​反向边：若原边 $(v, u)$ 的流量 $f(v, u) > 0$，残留容量为 $f(v, u)$
• 作用：通过残留网络找到增广路径，动态调整流量

算法设计

• 初始化：设初始流 $f(e) = 0$，构建初始残留网络 $G_f$
• 迭代过程：
  • 寻找增广路径：在 $G_f$ 中找一条 $s \rightarrow t$ 路径 $p$
  • ​计算瓶颈容量：找出路径 $p$ 上残留容量的最小值 $b$
  • 更新流量：对路径 $p$ 中的每条边 $(u, v)$
    • 若为正向边，增加流量：$f(u, v)$ += $b$
    • 若为反向边，减少原边流量：$f(v, u)$ -= $b$
  • 更新残留网络：根据新流量 $f$ 重新构建 $G_f$
• 终止条件：当残留网络中不存在 $s \to t$ 路径时，返回最大流 $f$

正确性与复杂度

• 正确性：最大流最小割定理（见下节）
• 终止性：
  • 若所有容量都为有理数，算法会终止
  • 若容量有无理数，算法不一定终止
• 整数流定理：如果网络所有边的容量都是整数，则存在整数最大流
• 时间复杂度：$O(|E| \cdot f_{\max})$（所有容量为整数）

网络流的应用

比赛胜负问题

问题描述

问题转化

二分图最大匹配问题

问题描述

• 输入：​二分图 $G = (A, B, E)$，其中：
  • $A$ 与 $B$ 为互不相交的顶点集合
  • $E \subseteq A \times B$ 为边集合
• 输出：​最大匹配 $M \subseteq E$，满足：
  • $\forall u \in A \cup B$，最多存在一条边 $e \in M$ 与 $u$ 相连
  • $|M|$ 达到所有可能匹配中的最大值

问题转化

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