最大流与最小割

Views: --

流网络是带容量的有向图 G=(V,E)G=(V,E)，有源点 ss 和汇点 tt。最大流问题问：在不超过边容量且中间结点不囤积流量的前提下，最多能从 ss 输送多少到 tt。

1. 可行流的约束

对每条边 (u,v)(u,v)：

0≤f(u,v)≤c(u,v).0\le f(u,v)\le c(u,v).

对每个 u∉{s,t}u\notin\{s,t\}，满足流守恒：

∑vf(v,u)=∑vf(u,v).\sum_v f(v,u)=\sum_v f(u,v).

流值可定义为源点净流出量：

∣f∣=∑vf(s,v)−∑vf(v,s).|f|=\sum_v f(s,v)-\sum_v f(v,s).

2. 为什么需要反向边

早期选择可能不理想，需要撤销一部分流并改道。残量网络用残量容量表达“还能怎样调整”：

  • 正向残量 cf(u,v)=c(u,v)−f(u,v)c_f(u,v)=c(u,v)-f(u,v)，表示还能多送多少；
  • 反向残量 cf(v,u)=f(u,v)c_f(v,u)=f(u,v)，表示最多能撤回多少。

反向边不一定是原图真实管道，而是修改既有决策的能力。缺少反向边的“只往前塞”贪心可能卡在非最大流。

3. 增广路

残量网络中从 ss 到 tt 的路径称为增广路。路径瓶颈为

Δ=min⁡(u,v)∈Pcf(u,v).\Delta=\min_{(u,v)\in P}c_f(u,v).

沿路径每条残量边增加 Δ\Delta；走到反向边时，等价于减少对应原边流量。每次增广都让总流值增加 Δ\Delta。

4. Ford–Fulkerson 框架

flow = 0
while residual graph has an s-t path P:
    delta = minimum residual capacity on P
    augment delta along P
return flow

整数容量下，每次至少增加 1，时间可写为 O(E∣f∗∣)O(E|f^*|)，其中 ∣f∗∣|f^*| 是最大流值。若使用任意实数容量和任意选路，甚至可能不终止，因此它更像一个算法框架。

5. Edmonds–Karp

每次在残量网络中用 BFS 选择边数最少的增广路，就是 Edmonds–Karp。它的增广次数为 O(VE)O(VE)，每次 BFS 为 O(E)O(E)，所以

T=O(VE2).T=O(VE^2).

该界与最大流数值无关，是多项式时间保证。

6. 割与容量

一个 ss-tt 割 (S,T)(S,T) 满足 s∈S,t∈Ts\in S,t\in T。割容量只统计从 SS 指向 TT 的原图边：

c(S,T)=∑u∈S,v∈Tc(u,v).c(S,T)=\sum_{u\in S,v\in T}c(u,v).

任何流穿过这个割时都受这些边容量限制，因此对所有可行流都有

∣f∣≤c(S,T).|f|\le c(S,T).

7. 最大流最小割定理

当残量网络中不存在增广路时，令 SS 为从 ss 在残量网络中仍可达的顶点，T=V−ST=V-S。

  • 所有从 SS 到 TT 的原边都已满流，否则还能沿正向残量边到达；
  • 所有从 TT 到 SS 的原边流量为 0，否则还能沿反向残量边到达。

因此当前流值恰等于该割容量。结合弱上界，得到

max⁡∣f∣=min⁡c(S,T).\max |f|=\min c(S,T).

“残量图中无增广路”“流是最大流”“存在同值的最小割”三者等价。

8. 建模技巧：点容量

若限制经过某个顶点 vv 的总流量不超过 bvb_v，可把它拆成 vinv_{in} 与 voutv_{out}，中间连容量 bvb_v 的边；原入边接到 vinv_{in}，原出边从 voutv_{out} 发出。

这叫拆点，也是网格中限制每个格子只能使用一次的常用方法。

9. 整数性与应用

容量为整数时，增广算法能得到整数最大流。于是可以用单位容量建模二分图匹配、边不相交路径等离散问题。

注意最大流允许流量分叉、汇合，并不自动给出单条路径；若要拆成路径，可沿正流边逐条提取。

评论