基于线性规划的图最大流问题的预流推进算法求解示例

我将为您详细讲解如何用预流推进算法解决图的最大流问题。这个算法结合了线性规划的思想，通过维护一个"预流"来逐步达到最大流。

问题描述
给定一个有向图G=(V,E)，其中V是顶点集合，E是边集合。每条边(u,v)∈E有一个非负容量c(u,v)。指定一个源点s∈V和一个汇点t∈V。目标是找到从s到t的最大流量，满足：

1. 容量约束：每条边上的流量不超过其容量
2. 流量守恒：除s和t外，每个顶点的流入量等于流出量

解题过程

第一步：算法基本概念
预流推进算法维护一个"预流"函数f: V×V→R，它满足：

• 容量约束：0 ≤ f(u,v) ≤ c(u,v) 对所有边(u,v)成立
• 松弛的流量守恒：除s和t外，每个顶点的净流量非负（即流入≥流出）

算法还维护每个顶点的高度函数h: V→Z，以及每个顶点的超额流e: V→R。

第二步：初始化

1. 初始化高度函数：

   • h(s) = |V|（顶点数）
   • h(v) = 0 对所有v∈V-{s}

2. 初始化流函数：

   • 对所有从s出发的边(s,v)，设f(s,v) = c(s,v)
   • 其他边f(u,v) = 0

3. 初始化超额流：

   • e(s) = -∑f(s,v)（s的出流总和）
   • e(v) = f(s,v) 对所有v∈V-{s}

第三步：基本操作定义
算法通过两种基本操作推进流：

1. 推进操作(Push)
   当顶点u有超额流(e(u)>0)，且存在边(u,v)满足：

   • 剩余容量c_f(u,v) = c(u,v) - f(u,v) > 0
   • h(u) = h(v) + 1

   则推进量δ = min(e(u), c_f(u,v))
   更新：

   • f(u,v) += δ
   • f(v,u) -= δ（反向边）
   • e(u) -= δ
   • e(v) += δ

2. 重标高度操作(Relabel)
   当顶点u有超额流，但无法推进到任何相邻顶点时（即对所有满足c_f(u,v)>0的边，都有h(u) ≤ h(v)）
   更新：h(u) = 1 + min{h(v) | (u,v)∈E 且 c_f(u,v)>0}

第四步：算法执行流程

1. 初始化如第二步所述
2. 当存在有超额流的顶点（除s和t外）时：
   a. 选择有超额流的顶点u
   b. 尝试对u执行推进操作：
   • 如果存在满足条件的边(u,v)，执行推进操作
   • 否则，执行重标高度操作
3. 当没有顶点（除s和t外）有超额流时，算法终止

第五步：具体实例演示
考虑图：V={s,a,b,t}，边容量：

• s→a: 3, s→b: 2
• a→b: 2, a→t: 2
• b→t: 3

执行过程：

1. 初始化：h(s)=4, h(a)=h(b)=h(t)=0
   f(s,a)=3, f(s,b)=2, 其他边流量为0
   e(a)=3, e(b)=2, e(s)=-5, e(t)=0

2. 处理顶点a：

   • 检查边a→b：剩余容量2>0，但h(a)=0 ≤ h(b)=0，不能推进
   • 检查边a→t：剩余容量2>0，但h(a)=0 ≤ h(t)=0，不能推进
   • 执行重标高度：h(a)=1+min{h(b),h(t)}=1

3. 处理顶点a→t推进：

   • 满足条件：剩余容量2>0，h(a)=1 = h(t)=0+1
   • 推进量δ=min(e(a)=3, 2)=2
   • 更新：f(a,t)=2, e(a)=1, e(t)=2

4. 继续处理顶点a→b推进：

   • 满足条件：剩余容量2>0，h(a)=1 = h(b)=0+1
   • 推进量δ=min(e(a)=1, 2)=1
   • 更新：f(a,b)=1, e(a)=0, e(b)=3

5. 处理顶点b：

   • 检查边b→t：剩余容量3>0，h(b)=0 ≤ h(t)=0，不能推进
   • 执行重标高度：h(b)=1+min{h(t)}=1

6. 处理顶点b→t推进：

   • 满足条件：剩余容量3>0，h(b)=1 = h(t)=0+1
   • 推进量δ=min(e(b)=3, 3)=3
   • 更新：f(b,t)=3, e(b)=0, e(t)=5

第六步：结果验证
最终流量：f(s,a)=3, f(s,b)=2, f(a,b)=1, f(a,t)=2, f(b,t)=3
最大流值：5
验证流量守恒和容量约束均满足。

这个算法的时间复杂度为O(|V|²|E|)，在实践中通常表现很好，特别是对于稀疏图。