基于线性规划的图最大流问题的多项式时间最高标号预流推进算法求解示例
字数 3531 2025-12-12 23:27:54

基于线性规划的图最大流问题的多项式时间最高标号预流推进算法求解示例

1. 问题描述

假设我们有一个有向图 \(G=(V, E)\)，其中 \(V\) 是顶点集合，\(E\) 是边集合。图中有两个特殊顶点：源点 \(s\) 和汇点 \(t\)。每条边 \((u, v) \in E\) 都有一个容量 \(c(u, v) \geq 0\)，表示该边能通过的最大流量。最大流问题的目标是找到从源点 \(s\) 到汇点 \(t\) 的最大可能流量，即找到一种分配流量的方式，使得：

  • 容量约束：每条边上的流量不超过其容量。
  • 流量守恒：除源点和汇点外，每个顶点的流入量等于流出量。

最高标号预流推进算法 是 Goldberg 和 Tarjan 提出的一种高效算法，其最坏情况时间复杂度为 \(O(|V|^2 \sqrt{|E|})\)，是一种多项式时间算法，在处理大型稠密图时尤其高效。

2. 算法核心思想

算法不直接寻找从 \(s\) 到 \(t\) 的路径，而是先尽可能地“推”流，允许中间顶点暂时不满足流量守恒（即流入可能大于流出），形成一个“预流”。同时，每个顶点被赋予一个“高度”或“距离标号”，流只能从较高顶点推往较低顶点。算法通过不断调整“高度”和“推进”流，最终消除所有不满足流量守恒的顶点（源点和汇点除外），得到最大流。

3. 关键定义

  1. 预流： 一个函数 \(f: E \rightarrow R^+\) 满足：

    • 容量约束：对每条边 \((u, v) \in E\)，有 \(0 \leq f(u, v) \leq c(u, v)\)。
    • 松弛的守恒约束：对每个顶点 \(u \in V \setminus \{s, t\}\)，有 \(e(u) = \sum_{v: (v, u) \in E} f(v, u) - \sum_{v: (u, v) \in E} f(u, v) \geq 0\)，其中 \(e(u)\) 称为顶点 \(u\) 的超额流。源点和汇点无守恒约束。

  2. 距离标号： 一个函数 \(h: V \rightarrow N\)，满足：

    • \(h(s) = |V|\)，\(h(t) = 0\)。
    • 对每条残留边 \((u, v)\)（即 \(c_f(u, v) = c(u, v) - f(u, v) > 0\)），有 \(h(u) \leq h(v) + 1\)。

  3. 可允许边： 一条残留边 \((u, v)\) 如果满足 \(h(u) = h(v) + 1\)，则称为可允许边。算法只沿着可允许边推进流。

4. 算法详细步骤

我们用一个具体例子说明。假设有向图如下（数字表示容量）：

     s
    / \
   1   2
  /     \
 v1     v2
  \     /
   2   1
    \ /
     t

即：边 (s, v1)=1, (s, v2)=2, (v1, v2)=0, (v1, t)=2, (v2, t)=1。

初始化：

  1. 设置初始流 \(f = 0\)。
  2. 设置距离标号：\(h(s) = 4\)（顶点数），\(h(v1) = h(v2) = h(t) = 0\)。
  3. 从源点向所有邻点推尽可能多的流，使源点的出边饱和，形成初始预流。
    • 推流到 v1：推 1 单位，\(e(v1) = 1\)。
    • 推流到 v2：推 2 单位，\(e(v2) = 2\)。
  4. 将所有顶点（除了 s 和 t）放入一个队列（或列表）中，这些顶点是“活跃的”（有超额流 e(u) > 0）。初始活跃顶点：{v1, v2}。

算法主循环：
只要存在活跃顶点，就重复以下步骤：

  1. 选择高度最高的活跃顶点 u（“最高标号”规则）。
  2. 尝试对 u 执行推进操作：
    • 检查 u 的所有出边（残留容量 > 0）。如果存在一条可允许边 (u, v)（即 h(u) = h(v) + 1），则将尽可能多的超额流从 u 推向 v。推送量 δ = min(e(u), c_f(u, v))。更新 f(u, v)，e(u)，e(v)。如果 v 不是 s 或 t 且变得活跃，则将其加入活跃顶点列表。
    • 如果 u 的超额流 e(u) 变为 0，则 u 变为不活跃，回到步骤1。
  3. 如果 u 仍有超额流但无可允许边（即所有残留出边都满足 h(u) ≤ h(v)），则执行重标操作：将 h(u) 增加到 min{ h(v) + 1 | (u, v) 是残留边 }。这保证了至少创造一条可允许边。重标后，u 仍然是活跃的，算法继续尝试对其推进。

应用于示例：

  1. 初始活跃顶点：v1(h=0), v2(h=0)。选 v1。

    • 无可允许出边（因为 h(v1)=0，到 t 的边 (v1, t) 残留容量=2，但 h(t)=0，不满足 h(u)=h(v)+1）。
    • 重标 v1：最小邻点高度+1 = h(t)+1 = 1。更新 h(v1)=1。
    • 重新检查 v1：边 (v1, t) 现在可允许（1 = 0+1）。推进 δ = min(e(v1)=1, 2)=1 到 t。更新 e(v1)=0，e(t) 增加 1（但 t 是汇点，我们不关心其超额流）。v1 变为不活跃。活跃顶点：{v2}。

  2. 选 v2(h=0)。

    • 无可允许出边（到 t 的边 h(t)=0，不满足条件）。
    • 重标 v2：h(v2) = h(t)+1 = 1。
    • 检查 v2：边 (v2, t) 可允许（1 = 0+1）。推进 δ = min(e(v2)=2, 1)=1 到 t。更新 e(v2)=1，v2 仍活跃。此时活跃顶点：{v2}。

  3. 再次选 v2(h=1)。

    • 已无残留可允许出边（(v2, t) 已满，残留容量为0）。
    • 重标 v2：检查所有残留出边，但已没有残留出边指向任何顶点（因为到 t 的边已满）。按规定，此时 h(v2) 可设为 |V|+1 或保持，但通常设为大于任何顶点的高度。设 h(v2)=5（大于 h(s)=4）。
    • 活跃顶点仍是 v2。

  4. 再次选 v2(h=5)。

    • 检查残留入边？不，我们检查出边。但 v2 到 t 已满。此时，虽然没有出边，但 v2 仍有超额流 e(v2)=1。算法必须将流“退回”到其他顶点。但 v2 没有残留出边，所以它需要重标，但重标后高度会变得非常高。实际上，在这种情况下，算法会发现从 v2 无法将超额流推到任何地方。但注意，我们忽略了反向边。

关键补充：残留网络
在预流推进算法中，当我们沿着边 (u, v) 推进了流量，我们同时在残留网络中创建一条反向边 (v, u)，其残留容量等于正向流量。这允许算法“退回”流。
因此，在步骤3之后，残留网络中 v2 有一条到 s 的反向边（因为初始从 s 推了 2 到 v2），容量为 2（当前已用 1，所以残留容量 1），以及一条到 t 的正向边（已用1，容量1，已满）。所以 v2 的出边残留边包括：(v2, s) 残留容量 1（反向边），(v2, t) 残留容量 0。

  1. 继续步骤3后，v2 高度为 5。检查其残留出边：
    • (v2, s)：h(v2)=5，h(s)=4，满足 h(u) = h(v)+1？5 = 4+1，满足！这是可允许边。注意，这是反向边，允许将超额流推回源点。
    • 推进 δ = min(e(v2)=1, 1)=1 到 s。更新 e(v2)=0，e(s) 增加 1（但 s 是源点，忽略）。v2 变为不活跃。活跃顶点为空。

算法终止： 无活跃顶点，此时预流变为有效流（所有顶点 e(u)=0）。算法结束。最终流值 = 从 s 流出的总量 = 1（到 v1）+ 1（到 v2，因为退回了1）= 2。或者进入 t 的流量 = 1（从 v1）+ 1（从 v2）= 2。最大流为 2。

5. 多项式时间复杂性

最高标号规则（每次选择高度最高的活跃顶点）保证了算法的时间复杂度为 \(O(|V|^2 \sqrt{|E|})\)。原因简述：

  • 每个顶点的重标次数最多为 \(2|V|\) 次。
  • 推进操作分为饱和推进（使边满）和不饱和推进。饱和推进最多 \(O(|V||E|)\) 次，不饱和推进最多 \(O(|V|^2|E|)\) 次，但最高标号规则优化后，不饱和推进减少到 \(O(|V|^3)\) 次，结合数据结构优化可得到上述界。

6. 总结

最高标号预流推进算法是求解最大流问题的高效多项式算法。其核心在于维护距离标号和允许反向流的残留网络，通过“推流”和“重标”操作，最终将预流转化为最大流。最高标号规则极大地提升了性能，使其在实践中和理论上都表现优异。

基于线性规划的图最大流问题的多项式时间最高标号预流推进算法求解示例 1. 问题描述 假设我们有一个有向图 \( G=(V, E) \)，其中 \( V \) 是顶点集合，\( E \) 是边集合。图中有两个特殊顶点： 源点 \( s \) 和 汇点 \( t \) 。每条边 \( (u, v) \in E \) 都有一个 容量 \( c(u, v) \geq 0 \) ，表示该边能通过的最大流量。 最大流问题 的目标是找到从源点 \( s \) 到汇点 \( t \) 的最大可能流量，即找到一种分配流量的方式，使得： 容量约束：每条边上的流量不超过其容量。 流量守恒：除源点和汇点外，每个顶点的流入量等于流出量。 最高标号预流推进算法 是 Goldberg 和 Tarjan 提出的一种高效算法，其最坏情况时间复杂度为 \( O(|V|^2 \sqrt{|E|}) \)，是一种多项式时间算法，在处理大型稠密图时尤其高效。 2. 算法核心思想 算法不直接寻找从 \( s \) 到 \( t \) 的路径，而是先尽可能地“推”流，允许中间顶点暂时不满足流量守恒（即流入可能大于流出），形成一个“预流”。同时，每个顶点被赋予一个“高度”或“距离标号”，流只能从较高顶点推往较低顶点。算法通过不断调整“高度”和“推进”流，最终消除所有不满足流量守恒的顶点（源点和汇点除外），得到最大流。 3. 关键定义 预流 ： 一个函数 \( f: E \rightarrow R^+ \) 满足： 容量约束：对每条边 \( (u, v) \in E \)，有 \( 0 \leq f(u, v) \leq c(u, v) \)。 松弛的守恒约束：对每个顶点 \( u \in V \setminus \{s, t\} \)，有 \( e(u) = \sum_ {v: (v, u) \in E} f(v, u) - \sum_ {v: (u, v) \in E} f(u, v) \geq 0 \)，其中 \( e(u) \) 称为顶点 \( u \) 的 超额流 。源点和汇点无守恒约束。 距离标号 ： 一个函数 \( h: V \rightarrow N \)，满足： \( h(s) = |V| \)，\( h(t) = 0 \)。 对每条残留边 \( (u, v) \)（即 \( c_ f(u, v) = c(u, v) - f(u, v) > 0 \)），有 \( h(u) \leq h(v) + 1 \)。 可允许边 ： 一条残留边 \( (u, v) \) 如果满足 \( h(u) = h(v) + 1 \)，则称为可允许边。算法只沿着可允许边推进流。 4. 算法详细步骤 我们用一个具体例子说明。假设有向图如下（数字表示容量）： 即：边 (s, v1)=1, (s, v2)=2, (v1, v2)=0, (v1, t)=2, (v2, t)=1。 初始化 ： 设置初始流 \( f = 0 \)。 设置距离标号：\( h(s) = 4 \)（顶点数），\( h(v1) = h(v2) = h(t) = 0 \)。 从源点向所有邻点推尽可能多的流，使源点的出边饱和，形成初始预流。 推流到 v1：推 1 单位，\( e(v1) = 1 \)。 推流到 v2：推 2 单位，\( e(v2) = 2 \)。 将所有顶点（除了 s 和 t）放入一个队列（或列表）中，这些顶点是“活跃的”（有超额流 e(u) > 0）。初始活跃顶点：{v1, v2}。 算法主循环 ： 只要存在活跃顶点，就重复以下步骤： 选择 高度最高的活跃顶点 u（“最高标号”规则）。 尝试对 u 执行 推进操作 ： 检查 u 的所有出边（残留容量 > 0）。如果存在一条可允许边 (u, v)（即 h(u) = h(v) + 1），则将尽可能多的超额流从 u 推向 v。推送量 δ = min(e(u), c_ f(u, v))。更新 f(u, v)，e(u)，e(v)。如果 v 不是 s 或 t 且变得活跃，则将其加入活跃顶点列表。 如果 u 的超额流 e(u) 变为 0，则 u 变为不活跃，回到步骤1。 如果 u 仍有超额流但无可允许边（即所有残留出边都满足 h(u) ≤ h(v)），则执行 重标操作 ：将 h(u) 增加到 min{ h(v) + 1 | (u, v) 是残留边 }。这保证了至少创造一条可允许边。重标后，u 仍然是活跃的，算法继续尝试对其推进。 应用于示例 ： 初始活跃顶点：v1(h=0), v2(h=0)。选 v1。 无可允许出边（因为 h(v1)=0，到 t 的边 (v1, t) 残留容量=2，但 h(t)=0，不满足 h(u)=h(v)+1）。 重标 v1：最小邻点高度+1 = h(t)+1 = 1。更新 h(v1)=1。 重新检查 v1：边 (v1, t) 现在可允许（1 = 0+1）。推进 δ = min(e(v1)=1, 2)=1 到 t。更新 e(v1)=0，e(t) 增加 1（但 t 是汇点，我们不关心其超额流）。v1 变为不活跃。活跃顶点：{v2}。 选 v2(h=0)。 无可允许出边（到 t 的边 h(t)=0，不满足条件）。 重标 v2：h(v2) = h(t)+1 = 1。 检查 v2：边 (v2, t) 可允许（1 = 0+1）。推进 δ = min(e(v2)=2, 1)=1 到 t。更新 e(v2)=1，v2 仍活跃。此时活跃顶点：{v2}。 再次选 v2(h=1)。 已无残留可允许出边（(v2, t) 已满，残留容量为0）。 重标 v2：检查所有残留出边，但已没有残留出边指向任何顶点（因为到 t 的边已满）。按规定，此时 h(v2) 可设为 |V|+1 或保持，但通常设为大于任何顶点的高度。设 h(v2)=5（大于 h(s)=4）。 活跃顶点仍是 v2。 再次选 v2(h=5)。 检查残留入边？不，我们检查出边。但 v2 到 t 已满。此时，虽然没有出边，但 v2 仍有超额流 e(v2)=1。算法必须将流“退回”到其他顶点。但 v2 没有残留出边，所以它需要重标，但重标后高度会变得非常高。实际上，在这种情况下，算法会发现从 v2 无法将超额流推到任何地方。但注意，我们忽略了 反向边 。 关键补充：残留网络 在预流推进算法中，当我们沿着边 (u, v) 推进了流量，我们同时 在残留网络中创建一条反向边 (v, u) ，其残留容量等于正向流量。这允许算法“退回”流。 因此，在步骤3之后，残留网络中 v2 有一条到 s 的反向边（因为初始从 s 推了 2 到 v2），容量为 2（当前已用 1，所以残留容量 1），以及一条到 t 的正向边（已用1，容量1，已满）。所以 v2 的出边残留边包括：(v2, s) 残留容量 1（反向边），(v2, t) 残留容量 0。 继续步骤3后，v2 高度为 5。检查其残留出边： (v2, s)：h(v2)=5，h(s)=4，满足 h(u) = h(v)+1？5 = 4+1，满足！这是可允许边。注意，这是反向边，允许将超额流推回源点。 推进 δ = min(e(v2)=1, 1)=1 到 s。更新 e(v2)=0，e(s) 增加 1（但 s 是源点，忽略）。v2 变为不活跃。活跃顶点为空。 算法终止 ： 无活跃顶点，此时预流变为有效流（所有顶点 e(u)=0）。算法结束。最终流值 = 从 s 流出的总量 = 1（到 v1）+ 1（到 v2，因为退回了1）= 2。或者进入 t 的流量 = 1（从 v1）+ 1（从 v2）= 2。最大流为 2。 5. 多项式时间复杂性 最高标号规则（每次选择高度最高的活跃顶点）保证了算法的时间复杂度为 \( O(|V|^2 \sqrt{|E|}) \)。原因简述： 每个顶点的重标次数最多为 \( 2|V| \) 次。 推进操作分为饱和推进（使边满）和不饱和推进。饱和推进最多 \( O(|V||E|) \) 次，不饱和推进最多 \( O(|V|^2|E|) \) 次，但最高标号规则优化后，不饱和推进减少到 \( O(|V|^3) \) 次，结合数据结构优化可得到上述界。 6. 总结 最高标号预流推进算法是求解最大流问题的高效多项式算法。其核心在于维护距离标号和允许反向流的残留网络，通过“推流”和“重标”操作，最终将预流转化为最大流。最高标号规则极大地提升了性能，使其在实践中和理论上都表现优异。