跳到主要内容

网络流理论 (Network Flow Theory)

网络流不仅是组合优化的核心，更是线性规划 (Linear Programming) 在图结构上的投影。本章将从形式化对偶性出发，系统性地构建流网络的性质证明、收敛性分析及其在单位网络中的复杂度界限。

一、 形式化理论体系​

1. 流网络与可行流​

定义 (Feasible Flow)：函数 f:V×V→Rf: V \times V \to \mathbb{R} 满足：

  1. 容量限制：f(u,v)≤c(u,v)f(u, v) \le c(u, v)。
  2. 斜对称性：f(u,v)=−f(v,u)f(u, v) = -f(v, u)。
  3. 流量守恒 (Flow Conservation)：除 s,ts, t 外，对于任意 u∈V∖{s,t}u \in V \setminus \{s, t\}，满足 ∑v∈Vf(u,v)=0\sum_{v \in V} f(u, v) = 0。
流量守恒一致性证明 (Consistency Proof)

命题：在增广路算法（如 FF 或 Dinic）中，对路径 pp 进行增广操作后，流量守恒性依然保持。 证明：

  1. 设增广流量为 Δ\Delta。对于路径上的中间点 v∈pv \in p，vv 必有入边 (u,v)(u, v) 和出边 (v,w)(v, w)。
  2. 增广操作令 f(u,v)←f(u,v)+Δf(u, v) \leftarrow f(u, v) + \Delta，f(v,w)←f(v,w)+Δf(v, w) \leftarrow f(v, w) + \Delta。
  3. 对于点 vv，入流净增 Δ\Delta，出流净增 Δ\Delta，其净流量 ∑x∈Vf(v,x)\sum_{x \in V} f(v, x) 保持不变（原先为 00，增广后仍为 00）。
  4. 对于 ss 和 tt，分别仅有出流或入流发生变化，符合流定义。

2. 割集与流量收敛性​

引理 (Flow-Cut Duality)：穿过任意割 (S,T)(S, T) 的净流量等于流的价值 ∣f∣|f|。 Proof: f(S,T)=∑u∈S∑v∈Tf(u,v)=∑u∈S(∑v∈Vf(u,v)−∑v∈Sf(u,v))=∑u∈S∑v∈Vf(u,v)\text{Proof: } f(S, T) = \sum_{u \in S} \sum_{v \in T} f(u, v) = \sum_{u \in S} \left( \sum_{v \in V} f(u, v) - \sum_{v \in S} f(u, v) \right) = \sum_{u \in S} \sum_{v \in V} f(u, v) 由于斜对称性，∑u∈S∑v∈Sf(u,v)=0\sum_{u \in S} \sum_{v \in S} f(u, v) = 0。且根据守恒性，只有 u=su=s 时 ∑f(s,v)\sum f(s, v) 非零，故 f(S,T)=∣f∣f(S, T) = |f|。

二、 算法收敛性分析 (Convergence Analysis)​

1. Dinic 算法：距离单调性与收敛界限​

Dinic 的高效性建立在分层图 (Level Graph) 的严格单调性上。

Dinic 距离单调性证明

引理：在 Dinic 的一轮迭代（BFS + 多路 DFS 增广）后，下一轮 BFS 得到的 dist(s,t)dist(s, t) 严格增加。 证明要点：

  1. 在残量网络 GfG_f 中，只有当 (u,v)(u, v) 满足 dist(u)+1=dist(v)dist(u) + 1 = dist(v) 时才可能被增广。
  2. 增广后，原有层间的饱和边消失，而可能产生反向边 (v,u)(v, u)。
  3. 反向边 (v,u)(v, u) 满足 dist(v)=dist(u)+1dist(v) = dist(u) + 1，即它是指向前一层的，不会缩短 s→ts \to t 的最短距离。
  4. 只有当 s→ts \to t 在当前分层图中所有路径都饱和时，才需要重新 BFS 增加层数。 结论：由于 dist(s,t)≤ndist(s, t) \le n，算法最多进行 nn 轮 BFS，总复杂度 O(V2E)O(V^2E)。

三 最大流最小割定理 (Max-Flow Min-Cut)​

定理 2.1：最大流价值 ∣f∣|f| 等于最小割容量 c(S,T)c(S, T)。 证明要点：

  1. 任意流 ≤\le 任意割。
  2. 当残量网络 GfG_f 无增广路时，定义 SS 为 ss 可达点集，通过构造性证明 ∣f∣=c(S,T)|f| = c(S, T)，从而建立等价性。

四、 建模进阶：上下界网络流​

对于边 (u,v)(u, v) 有下界 luvl_{uv} 和上界 cuvc_{uv}：

1. 无源汇可行流 (Circulation)​

建立新源汇 S′,T′S', T'。

  • 流量平衡：对于点 uu，设 in_sumin\_sum 为进入 uu 的所有下界之和，out_sumout\_sum 为离开 uu 的下界之和。
  • 连边：
    • 若 in_sum−out_sum>0in\_sum - out\_sum > 0，连边 (S′,u)(S', u)，容量为 in_sum−out_sumin\_sum - out\_sum。
    • 若 in_sum−out_sum<0in\_sum - out\_sum < 0，连边 (u,T′)(u, T')，容量为 out_sum−in_sumout\_sum - in\_sum。
  • 结论：若 S′→T′S' \to T' 满流，则存在可行流。

五、 精选练习与解析​

练习 1：最小路径覆盖 (DAG)​

给定一个 DAG，用最少的互不相交的路径覆盖所有顶点。

Check Solution

解析：

  1. 拆点：将每个点 uu 拆为 uinu_{in} 和 uoutu_{out}。
  2. 建模：
    • 对于原图中的边 (u,v)(u, v)，连边 (uout,vin)(u_{out}, v_{in})，容量 11。
    • S→uoutS \to u_{out}，uin→Tu_{in} \to T，容量均位 11。
  3. 计算：最小路径数 = 总顶点数 - 最大匹配数。

练习 2：最大权闭合子图​

给定带权图，选择一些点，若选择了点 uu，则必须选择其所有后继点。求总权值最大。

Check Solution

解析：

  1. 建模：
    • S→正权点S \to \text{正权点}，容量为点权。
    • 负权点→T\text{负权点} \to T，容量为点权的绝对值。
    • 原图中的边 (u,v)(u, v)，连边 (u,v)(u, v)，容量 ∞\infty。
  2. 计算：∑PositiveWeights−MinCut\sum \text{PositiveWeights} - \text{MinCut}。

练习 3：混合图欧拉回路​

给定一个部分边有向、部分边无向的图，判定是否存在欧拉回路。

Check Solution

解析：

  1. 预处理：给无向边任意定向，并计算每个点的度数差 D=in-degree−out-degreeD = \text{in-degree} - \text{out-degree}。若有奇数度数点，必无解。
  2. 建模：
    • 目标是将某些无向边重定向，使所有点 D=0D=0。
    • 连边 (S,u)(S, u)（若 D>0D>0）或 (u,T)(u, T)（若 D<0D<0），容量为 ∣D∣/2|D|/2。
    • 对于原无向边定向 (u,v)(u, v)，连边 (u,v)(u, v)，容量 11（表示可以反向）。
  3. 判定：若最大流为满流，则存在欧拉回路。

练习 4：网络流 24 题 - 航空路线问题​

找两条从起点到终点的点不相交路径，使得路径权值和最大。

Check Solution

解析：

  1. 拆点：每个点 uu 拆为 uin,uoutu_{in}, u_{out}，连边 (uin,uout)(u_{in}, u_{out})，容量 11（起点终点为 22），权值为 11。
  2. 连边：原边 (u,v)(u, v) 连边 (uout,vin)(u_{out}, v_{in})，容量 11，权值 00。
  3. 求解：最大费用最大流。