xxx 最大流问题（Push-Relabel 算法）
字数 2896 2025-11-25 06:16:15

xxx 最大流问题（Push-Relabel 算法）

题目描述
给定一个有向图 \(G = (V, E)\)，其中每条边 \((u, v) \in E\) 有一个非负容量 \(c(u, v) \geq 0\)。指定两个特殊顶点：源点 \(s\) 和汇点 \(t\)。最大流问题的目标是找到从 \(s\) 到 \(t\) 的最大流量，满足以下约束：

  1. 容量约束：每条边的流量不超过其容量，即 \(0 \leq f(u, v) \leq c(u, v)\)。
  2. 流量守恒：除 \(s\) 和 \(t\) 外，每个顶点的流入量等于流出量。

Push-Relabel 算法通过维护一个预流（允许顶点的流入量暂时大于流出量）和高度标签，最终将预流转化为最大流。与增广路径类算法（如 Ford-Fulkerson）不同，Push-Relabel 通过局部操作（推送流量、调整顶点高度）逐步优化，具有高效的理论性能（如 \(O(V^2 \sqrt{E})\) 的复杂度）。

解题过程

1. 基本概念

  • 预流（Preflow）：允许顶点的流入量 ≥ 流出量（除汇点 \(t\) 外）。定义超额流量 \(e(u) = \text{流入量} - \text{流出量}\)。若 \(e(u) > 0\)，称 \(u\) 为溢出顶点。
  • 高度函数（Height Function）：为每个顶点 \(u\) 分配一个整数高度 \(h(u)\)，满足：
    • \(h(s) = |V|\)，\(h(t) = 0\)（初始设定）。
    • 对于残量边 \((u, v)\)，要求 \(h(u) \leq h(v) + 1\)。
  • 残量图：定义与 Ford-Fulkerson 类似，残量容量 \(r(u, v) = c(u, v) - f(u, v) + f(v, u)\)。

2. 初始化

  • 设置高度：\(h(s) = |V|\)，\(h(u) = 0\)（对 \(u \neq s\)）。
  • 设置预流：从 \(s\) 出发的边流量设为容量（\(f(s, v) = c(s, v)\)），其他边流量为 0。
  • 计算超额流量：\(e(s) = -\sum_{v} f(s, v)\)，其他顶点根据流入量计算。

3. 核心操作
算法反复执行以下两个操作，直到无溢出顶点存在：

  • 推送（Push）：
    选择溢出顶点 \(u\)，若存在残量边 \((u, v)\) 满足 \(h(u) = h(v) + 1\) 且 \(r(u, v) > 0\)，则沿 \((u, v)\) 推送流量：

\[ \Delta = \min(e(u), r(u, v)), \quad f(u, v) \leftarrow f(u, v) + \Delta, \quad f(v, u) \leftarrow f(v, u) - \Delta \]

更新超额流量：\(e(u) \leftarrow e(u) - \Delta\)，\(e(v) \leftarrow e(v) + \Delta\)。

  • 若 \(\Delta = r(u, v)\)，称为饱和推送（残量边被填满）；否则为非饱和推送。

  • 重标记（Relabel）：
    若溢出顶点 \(u\) 无法推送（无相邻顶点满足 \(h(u) = h(v) + 1\) 且 \(r(u, v) > 0\)），则提高其高度：

\[ h(u) \leftarrow 1 + \min\{ h(v) \mid (u, v) \in E_f \} \]

其中 \(E_f\) 是残量图的边集。

4. 算法步骤

  1. 初始化预流和高度。
  2. 当存在溢出顶点（非 \(s, t\)）时：
    • 尝试对当前溢出顶点执行推送操作（满足高度条件）。
    • 若无法推送，则执行重标记操作。
  3. 当无溢出顶点时，预流已成为最大流，返回 \(t\) 的流入量作为最大流值。

5. 示例说明
考虑一个简单图：

  • 顶点集 \(V = \{s, a, b, t\}\)，边集 \(E = \{(s, a, 3), (s, b, 2), (a, b, 1), (a, t, 2), (b, t, 3)\}\)（三元组表示起点、终点、容量）。

初始化：

  • \(h(s) = 4\)，其他顶点高度为 0。
  • 从 \(s\) 推流：\(f(s, a) = 3\)，\(f(s, b) = 2\)，\(e(a) = 3\)，\(e(b) = 2\)，\(e(s) = -5\)。

迭代过程：

  1. 选择溢出顶点 \(a\)：
    • 检查边 \((a, b)\)：\(h(a) = 0\)，\(h(b) = 0\)，不满足 \(h(a) = h(b) + 1\)，无法推送。
    • 检查边 \((a, t)\)：高度条件同样不满足。
    • 对 \(a\) 重标记：\(h(a) = 1 + \min(h(b), h(t)) = 1\)。
  2. 选择溢出顶点 \(a\)：
    • 沿 \((a, t)\) 推送（\(h(a) = 1\)，\(h(t) = 0\)，满足条件）：推送 \(\Delta = \min(3, 2) = 2\)。更新后 \(f(a, t) = 2\)，\(e(a) = 1\)，\(e(t) = 2\)。
  3. 选择溢出顶点 \(a\)：
    • 沿 \((a, b)\) 推送（\(h(a) = 1\)，\(h(b) = 0\)，满足条件）：推送 \(\Delta = \min(1, 1) = 1\)。更新后 \(f(a, b) = 1\)，\(e(a) = 0\)，\(e(b) = 3\)。
  4. 选择溢出顶点 \(b\)：
    • 沿 \((b, t)\) 推送（\(h(b) = 0\)，\(h(t) = 0\)，不满足条件）→ 重标记 \(b\)：\(h(b) = 1 + h(t) = 1\)。
    • 沿 \((b, t)\) 推送：\(\Delta = \min(3, 3) = 3\)。更新后 \(e(b) = 0\)，\(e(t) = 5\)。
  5. 无溢出顶点，算法终止。最大流值为 5。

6. 复杂度与优化

  • 基础 Push-Relabel 的复杂度为 \(O(V^2 E)\)。
  • 常用优化包括：
    • FIFO 队列：按顺序处理溢出顶点。
    • 最高标签优先：总是处理高度最大的溢出顶点，复杂度可优化至 \(O(V^2 \sqrt{E})\)。
    • 间隙启发式：通过高度分组快速识别不可达顶点。

总结
Push-Relabel 算法通过高度标签控制流量方向，逐步将预流转化为最大流。其优势在于避免频繁寻找增广路径，尤其适合稠密图或特定优化场景。

xxx 最大流问题（Push-Relabel 算法） 题目描述 给定一个有向图 \( G = (V, E) \)，其中每条边 \( (u, v) \in E \) 有一个非负容量 \( c(u, v) \geq 0 \)。指定两个特殊顶点：源点 \( s \) 和汇点 \( t \)。最大流问题的目标是找到从 \( s \) 到 \( t \) 的最大流量，满足以下约束： 容量约束 ：每条边的流量不超过其容量，即 \( 0 \leq f(u, v) \leq c(u, v) \)。 流量守恒 ：除 \( s \) 和 \( t \) 外，每个顶点的流入量等于流出量。 Push-Relabel 算法通过维护一个 预流 （允许顶点的流入量暂时大于流出量）和 高度标签 ，最终将预流转化为最大流。与增广路径类算法（如 Ford-Fulkerson）不同，Push-Relabel 通过局部操作（推送流量、调整顶点高度）逐步优化，具有高效的理论性能（如 \( O(V^2 \sqrt{E}) \) 的复杂度）。 解题过程 1. 基本概念 预流（Preflow） ：允许顶点的流入量 ≥ 流出量（除汇点 \( t \) 外）。定义超额流量 \( e(u) = \text{流入量} - \text{流出量} \)。若 \( e(u) > 0 \)，称 \( u \) 为 溢出顶点 。 高度函数（Height Function） ：为每个顶点 \( u \) 分配一个整数高度 \( h(u) \)，满足： \( h(s) = |V| \)，\( h(t) = 0 \)（初始设定）。 对于残量边 \( (u, v) \)，要求 \( h(u) \leq h(v) + 1 \)。 残量图 ：定义与 Ford-Fulkerson 类似，残量容量 \( r(u, v) = c(u, v) - f(u, v) + f(v, u) \)。 2. 初始化 设置高度：\( h(s) = |V| \)，\( h(u) = 0 \)（对 \( u \neq s \)）。 设置预流：从 \( s \) 出发的边流量设为容量（\( f(s, v) = c(s, v) \)），其他边流量为 0。 计算超额流量：\( e(s) = -\sum_ {v} f(s, v) \)，其他顶点根据流入量计算。 3. 核心操作 算法反复执行以下两个操作，直到无溢出顶点存在： 推送（Push） ： 选择溢出顶点 \( u \)，若存在残量边 \( (u, v) \) 满足 \( h(u) = h(v) + 1 \) 且 \( r(u, v) > 0 \)，则沿 \( (u, v) \) 推送流量： \[ \Delta = \min(e(u), r(u, v)), \quad f(u, v) \leftarrow f(u, v) + \Delta, \quad f(v, u) \leftarrow f(v, u) - \Delta \] 更新超额流量：\( e(u) \leftarrow e(u) - \Delta \)，\( e(v) \leftarrow e(v) + \Delta \)。 若 \( \Delta = r(u, v) \)，称为 饱和推送 （残量边被填满）；否则为 非饱和推送 。 重标记（Relabel） ： 若溢出顶点 \( u \) 无法推送（无相邻顶点满足 \( h(u) = h(v) + 1 \) 且 \( r(u, v) > 0 \)），则提高其高度： \[ h(u) \leftarrow 1 + \min\{ h(v) \mid (u, v) \in E_ f \} \] 其中 \( E_ f \) 是残量图的边集。 4. 算法步骤 初始化预流和高度。 当存在溢出顶点（非 \( s, t \)）时： 尝试对当前溢出顶点执行推送操作（满足高度条件）。 若无法推送，则执行重标记操作。 当无溢出顶点时，预流已成为最大流，返回 \( t \) 的流入量作为最大流值。 5. 示例说明 考虑一个简单图： 顶点集 \( V = \{s, a, b, t\} \)，边集 \( E = \{(s, a, 3), (s, b, 2), (a, b, 1), (a, t, 2), (b, t, 3)\} \)（三元组表示起点、终点、容量）。 初始化 ： \( h(s) = 4 \)，其他顶点高度为 0。 从 \( s \) 推流：\( f(s, a) = 3 \)，\( f(s, b) = 2 \)，\( e(a) = 3 \)，\( e(b) = 2 \)，\( e(s) = -5 \)。 迭代过程 ： 选择溢出顶点 \( a \)： 检查边 \( (a, b) \)：\( h(a) = 0 \)，\( h(b) = 0 \)，不满足 \( h(a) = h(b) + 1 \)，无法推送。 检查边 \( (a, t) \)：高度条件同样不满足。 对 \( a \) 重标记：\( h(a) = 1 + \min(h(b), h(t)) = 1 \)。 选择溢出顶点 \( a \)： 沿 \( (a, t) \) 推送（\( h(a) = 1 \)，\( h(t) = 0 \)，满足条件）：推送 \( \Delta = \min(3, 2) = 2 \)。更新后 \( f(a, t) = 2 \)，\( e(a) = 1 \)，\( e(t) = 2 \)。 选择溢出顶点 \( a \)： 沿 \( (a, b) \) 推送（\( h(a) = 1 \)，\( h(b) = 0 \)，满足条件）：推送 \( \Delta = \min(1, 1) = 1 \)。更新后 \( f(a, b) = 1 \)，\( e(a) = 0 \)，\( e(b) = 3 \)。 选择溢出顶点 \( b \)： 沿 \( (b, t) \) 推送（\( h(b) = 0 \)，\( h(t) = 0 \)，不满足条件）→ 重标记 \( b \)：\( h(b) = 1 + h(t) = 1 \)。 沿 \( (b, t) \) 推送：\( \Delta = \min(3, 3) = 3 \)。更新后 \( e(b) = 0 \)，\( e(t) = 5 \)。 无溢出顶点，算法终止。最大流值为 5。 6. 复杂度与优化 基础 Push-Relabel 的复杂度为 \( O(V^2 E) \)。 常用优化包括： FIFO 队列 ：按顺序处理溢出顶点。 最高标签优先 ：总是处理高度最大的溢出顶点，复杂度可优化至 \( O(V^2 \sqrt{E}) \)。 间隙启发式 ：通过高度分组快速识别不可达顶点。 总结 Push-Relabel 算法通过高度标签控制流量方向，逐步将预流转化为最大流。其优势在于避免频繁寻找增广路径，尤其适合稠密图或特定优化场景。