网络流：管道能通多少？

Part 2”量”建立了度量工具：最短路径衡量两点之间有多远，中心性判断谁最重要，社区发现找出谁和谁抱团。但”量”回答的是图是什么样的——描述性的。现在我们进入 Part 3”优”：图上该怎么做——决策性的。

上一篇 Art. 11: 最小生成树用贪心策略以最小代价连通所有节点，是 Part 3 的第一站。本文是第二站——给定一个有容量限制的网络，从源头到目的地，最多能输送多少？瓶颈在哪？ 这就是网络流问题。MST 关注”最便宜的连通”，本文关注”最大的流量”。而且我们将看到，最大流和最小割之间有一个极其优美的对偶关系——最大流量恰好等于最窄瓶颈截面的总容量。

算法范式：增广路（Ford-Fulkerson, Edmonds-Karp, Dinic）、对偶性（Max-flow = Min-cut）

核心问题：管道能通多少？

想象一个管道网络：水从水源 $s$ （source，源）出发，流经若干中转站，最终汇入水库 $t$ （sink，汇）。每段管道有一个容量上限——它每秒最多能通过多少水。问题是：从 $s$ 到 $t$ ，整个网络每秒最多能输送多少水？

这个问题远不止供水网络。把”水”换成数据包，就是通信网络的带宽分析；换成货物，就是供应链的吞吐量优化；换成电流，就是电路的负载分析。网络流是图上组合优化的核心工具，后续的匹配、图划分都是它的特例或推广。

流网络的定义

形式化地，一个流网络（flow network）是一个有向图 $G = (V, E)$ ，附带：

容量函数 $c : E \to \mathbb{R}^+$ ，每条边 $e$ 的容量 $c(e) \geq 0$
一个源点 $s \in V$ （只出不进）和一个汇点 $t \in V$ （只进不出）

一个可行流（feasible flow）是一个函数 $f : E \to \mathbb{R}^+$ ，满足两个约束：

容量约束：对每条边 $e$ ， $0 \leq f(e) \leq c(e)$ （流量不能超过容量）
流量守恒：对每个非源非汇节点 $v$ ，流入 $v$ 的总流量 = 流出 $v$ 的总流量

$\sum_{(u,v) \in E} f(u,v) = \sum_{(v,w) \in E} f(v,w), \quad \forall v \in V \setminus \{s, t\}$

流的值（value） $|f|$ 定义为从源点 $s$ 流出的净流量：

$|f| = \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s)$

最大流问题就是找一个可行流 $f$ ，使得 $|f|$ 最大。

上图展示了一个流网络的例子。每条边上标注的 flow/capacity 表示当前流量和容量上限。红色边已经饱和（流量 = 容量），灰色边没有流量。源点 $s$ （绿色）只有出边，汇点 $t$ （红色）只有入边。

最大流最小割定理

在讲算法之前，先理解一个贯穿全文的核心定理——它不仅指导算法设计，还揭示了最大流和网络瓶颈之间的深刻联系。

什么是割？

$s$ - $t$ 割（cut）是把节点集 $V$ 分成两个不相交的子集 $S$ 和 $T = V \setminus S$ ，使得 $s \in S$ ， $t \in T$ 。割的容量是所有从 $S$ 到 $T$ 的边的容量之和：

$c(S, T) = \sum_{u \in S, v \in T, (u,v) \in E} c(u, v)$

注意：只计算从 $S$ 到 $T$ 方向的边，不包括从 $T$ 到 $S$ 的边。

直觉上，割就是一刀切断网络，把源和汇分开。割的容量就是这一刀切断的所有管道的总容量——它是流量的一个上界，因为所有从 $s$ 到 $t$ 的流都必须通过这些被切断的管道。

定理：最大流 = 最小割

最大流最小割定理（Max-flow Min-cut Theorem, Ford & Fulkerson, 1956）：

$\max_f |f| = \min_{S,T} c(S,T)$

即：最大流的值恰好等于最小割的容量。

为什么成立？ 两个方向：

$\max |f| \leq \min c(S,T)$ （弱对偶）：对任意割 $(S, T)$ 和任意流 $f$ ，所有流都要从 $S$ 流到 $T$ ，受限于割的容量。因此任意流的值不超过任意割的容量。
$\max |f| \geq \min c(S,T)$ （强对偶）：当不存在增广路时（稍后定义），可以构造一个割，其容量等于当前流的值。这就证明了等式成立。

具体地，当 Edmonds-Karp 或 Dinic 算法终止时，从 $s$ 出发在残余图中能到达的节点集合就是 $S$ ，其余节点就是 $T$ ——这个割的容量恰好等于算法找到的最大流值。

这个定理的威力在于对偶性：求最大流（一个优化问题）等价于求最小割（看似完全不同的一个组合问题）。这种”一个问题的最优解 = 另一个互补问题的最优解”的模式在组合优化中反复出现。

Ford-Fulkerson 方法

残余图（Residual Graph）

要设计算法，我们需要一个关键工具——残余图（residual graph） $G_f$ 。给定当前流 $f$ ，残余图描述了”每条边还能再推多少流”。

对于原图中每条边 $(u, v)$ （容量 $c(u,v)$ ，当前流 $f(u,v)$ ），残余图 $G_f$ 包含：

正向残余边 $(u, v)$ ，残余容量 $c_f(u,v) = c(u,v) - f(u,v)$ ——还能再推多少
反向残余边 $(v, u)$ ，残余容量 $c_f(v,u) = f(u,v)$ ——能撤回多少

如果残余容量为 0，对应的残余边不存在。

直觉：正向边说”管道还有富余容量”，反向边说”你可以把已经推过去的流撤回来”。反向边是 Ford-Fulkerson 方法最关键的设计——它允许算法”反悔”之前的决策。

增广路（Augmenting Path）

在残余图 $G_f$ 中，从 $s$ 到 $t$ 的一条路径称为增广路（augmenting path）。沿这条路径，我们可以推送额外的流量，推送量等于路径上最小的残余容量（瓶颈，bottleneck）。

Ford-Fulkerson 方法

Ford-Fulkerson（1956）的方法非常简单：

Ford-Fulkerson(G, s, t):
    初始化 f(e) = 0 for all e
    while 残余图 G_f 中存在 s→t 增广路 p:
        bottleneck = 路径 p 上最小的残余容量
        沿 p 更新流量（正向边 +bottleneck，反向边 -bottleneck）
    return f

每次找到增广路并推送流量后，残余图发生变化，可能出现新的增广路。当残余图中不再存在 $s \to t$ 路径时，当前流就是最大流。

增广路定理（Ford-Fulkerson 定理）：以下三个条件等价：

$f$ 是最大流
残余图 $G_f$ 中不存在 $s \to t$ 增广路
存在一个割 $(S, T)$ 使得 $|f| = c(S, T)$

这三者的等价性就是最大流最小割定理的完整版本。

为什么需要反向边？

这是初学者最容易困惑的地方：为什么残余图需要反向边？不能只用正向边吗？

上图展示了一个经典反例。图有 4 个节点，所有边容量为 1，最大流应该是 2（两条不相交路径 $s \to A \to t$ 和 $s \to B \to t$ ）。但如果第一轮贪心选了 $s \to A \to B \to t$ （流量 1），没有反向边的话就卡住了—— $s \to A$ 和 $B \to t$ 都已经满了，而 $s \to B$ 和 $A \to t$ 不连通。

有了反向边 $B \to A$ （残余容量 = 1，允许撤回 $A \to B$ 的流量），第二轮可以找到增广路 $s \to B \to A \to t$ 。结果等价于两条不相交路径，总流 = 2。

反向边的本质是允许”反悔”——撤回之前不够好的流量分配，重新分配到更好的路径上。

Ford-Fulkerson 的局限

Ford-Fulkerson 只说了”找一条增广路”，没有规定怎么找。如果用 DFS 随意找，在容量为无理数的情况下算法可能不终止（Zwick, 1995）。即使容量为整数，如果用 DFS 找增广路，最坏情况下需要 $O(|f^*|)$ 次增广（ $f^*$ 是最大流值），每次 $O(E)$ ，总时间 $O(E \cdot |f^*|)$ ——当最大流值很大时极其低效。

关键改进：规定增广路的选择策略。

Edmonds-Karp 算法

Edmonds-Karp（1972）的改进非常简洁：用 BFS 找增广路（即找残余图中从 $s$ 到 $t$ 的最短增广路，以边数衡量）。

这个简单的改变带来了巨大的复杂度提升：

Edmonds-Karp(G, s, t):
    初始化 f(e) = 0 for all e
    while true:
        用 BFS 在残余图 G_f 中找 s→t 最短路径 p
        if p 不存在: break
        bottleneck = min{c_f(e) : e ∈ p}
        沿 p 更新流量
    return f

为什么 BFS 更好？

关键引理（Edmonds & Karp, 1972）：在 Edmonds-Karp 算法中，残余图中 $s$ 到任意节点 $v$ 的 BFS 距离 $d(s, v)$ 随着增广单调不减。

这意味着增广路的长度只会越来越长（不会变短）。由于最短路径长度最多为 $|V| - 1$ ，每个长度级别最多进行 $O(E)$ 次增广（每次增广至少让一条边饱和从分层图中消失），所以总增广次数最多 $O(VE)$ 。每次 BFS 花费 $O(E)$ ，总时间为：

$O(VE^2)$

数值走查

下面的交互走查展示 Edmonds-Karp 在一个 6 节点网络上的完整执行过程。注意观察：

每一轮 BFS 如何找到增广路
推送流量后残余图如何变化
最终没有增广路时算法终止

网络流走查 (Edmonds-Karp)总流量: 0

残余容量: sA:10sB:8AC:7AB:4BD:10Ct:9CD:3Dt:12

步骤 1/8: 初始状态：所有边流量为 0。

1 / 8

走查的关键观察：

每轮增广都沿 BFS 找到的最短路径推送流量
残余容量在每轮后更新——某些边饱和（变为 0），同时反向残余容量增加
当残余图中 $s$ 无法到达 $t$ 时，算法终止——此时的流即为最大流

Dinic 算法

Dinic（1970）在 Edmonds-Karp 的基础上更进一步：不是每次只找一条增广路，而是一次性找到残余图中的所有最短增广路。

核心思想：分层图 + 阻塞流

BFS 分层：从 $s$ 出发在残余图上做 BFS，得到每个节点的距离 $d[v]$ 。构建分层图（layered graph）：只保留满足 $d[v] = d[u] + 1$ 的残余边 $(u, v)$ 。
找阻塞流：在分层图上用 DFS 找阻塞流（blocking flow）——一个流，使得分层图中每条 $s \to t$ 路径上至少有一条边被饱和。
更新残余图：把阻塞流加到当前总流上，重新 BFS 分层，重复。

为什么更快？

关键定理：每次找到阻塞流并更新后，分层图中 $s$ 到 $t$ 的距离严格增加至少 1。

由于 $s$ 到 $t$ 的距离最多为 $|V| - 1$ ，所以最多进行 $O(V)$ 轮分层。每轮中：

BFS 分层： $O(E)$
找阻塞流（DFS + 删边）： $O(VE)$

总时间：

$O(V^2 E)$

对比 Edmonds-Karp 的 $O(VE^2)$ ，Dinic 在稠密图上更快（ $V^2 E < VE^2$ 当 $V < E$ 时）。

Dinic 在单位容量图和二部图上的加速

Dinic 算法有两个重要的特殊情况加速：

单位容量图（所有边容量为 1）： $O(E\sqrt{V})$ 。因为每轮阻塞流用时 $O(E)$ ，且距离增长更快。
二部图匹配（本质是单位容量网络流）： $O(E\sqrt{V})$ ——这就是 Hopcroft-Karp 匹配算法的本质（Art. 13 将展开讨论）。

最小费用最大流

标准最大流问题只关心流量。但如果每条边不仅有容量 $c(e)$ ，还有单位费用 $w(e)$ （推一个单位的流经过这条边花费 $w(e)$ ），怎么办？

最小费用最大流（Minimum-Cost Maximum Flow, MCMF）问题：在所有最大流中，找一个总费用最小的。

$\min \sum_{e \in E} w(e) \cdot f(e) \quad \text{s.t.} \quad |f| = |f^*| \text{(最大流值)}$

核心方法：把 Edmonds-Karp 中的 BFS 替换为 SPFA（或 Bellman-Ford），每次找最短费用增广路（即残余图中以费用为权重的最短路径）。

由于边费用可以为负（反向边费用 = $-w(e)$ ），需要能处理负权边的最短路算法——这就是 Bellman-Ford 的用武之地。

MCMF 的时间复杂度为 $O(V^2 E^2)$ （最坏情况），但在实际应用中通常远快于此。

复杂度对比

算法	时间复杂度（最坏）	增广策略	特点
Ford-Fulkerson (DFS)	$O(E \cdot \lvert f^* \rvert)$	任意 DFS	可能不终止（无理数容量）
Edmonds-Karp	$O(VE^2)$	BFS 最短路	一定终止，简单实用
Dinic	$O(V^2 E)$	分层图 + 阻塞流	实践中最快之一
Dinic (单位容量)	$O(E\sqrt{V})$	同上	匹配的理论基础
MCMF (SPFA)	$O(V^2 E^2)$	最短费用路	同时优化流量和费用

选型建议：

一般最大流：Dinic 是首选（代码量适中，速度快）
简单实现：Edmonds-Karp（用标准 BFS）
有费用约束：MCMF
二部匹配：Dinic 或 Hopcroft-Karp（Dinic 在单位容量图上的特例）

应用场景

交通网络容量分析

一个城市的道路网络中，每条路有一个通行能力（车辆/小时）。从某个区域到另一个区域的最大通行能力就是一个最大流问题。交通规划师用最大流分析找出”瓶颈道路”（对应最小割中的边），针对性地扩容。

供应链优化

供应链中，工厂（源）通过仓库网络向零售店（汇）发货。每段物流通道有容量限制（卡车数/天）。最大流告诉你系统的最大吞吐量，最小割告诉你瓶颈在哪条物流线路上。加权版本（最小费用最大流）还能同时优化运输成本。

图像分割

计算机视觉中，图割（graph cut）是经典的图像分割方法（Boykov & Kolmogorov, 2004）。把图像建模为图：

每个像素是一个节点
相邻像素之间有边，权重反映颜色/亮度相似度（越相似，权重越大——切断成本高）
添加源 $s$ （代表”前景”）和汇 $t$ （代表”背景”）， $s$ 连到可能是前景的像素， $t$ 连到可能是背景的像素

最小 $s$ - $t$ 割把像素分成前景和背景两组。被切断的边权重之和最小，意味着分割线优先沿着颜色差异大的地方走——这恰好是自然的物体边界。

这个方法在医学影像分析（器官分割）、遥感图像处理等领域广泛应用。Boykov 和 Kolmogorov 在 2004 年的 benchmark 论文中系统比较了多种最大流算法在图像分割任务上的性能——对于图像分割产生的特殊图结构，专门优化的实现比通用算法快一个数量级。

二部匹配

二部匹配（bipartite matching）是网络流的一个重要特例。给定二部图 $G = (L \cup R, E)$ ，添加源 $s$ 连到所有左侧节点（容量 1），汇 $t$ 连到所有右侧节点（容量 1），原始边容量为 1。在这个网络上求最大流，就得到了最大匹配数。

Dinic 在单位容量图上的 $O(E\sqrt{V})$ 复杂度，就是 Hopcroft-Karp 二部匹配算法的本质。下一篇 Art. 13: 匹配将详细展开匹配问题。

🔁 迭代机器视角 — Ford-Fulkerson / Edmonds-KarpOPT: 优化目标

Graph	残余图（动态变化）
State[v]	残余容量 c_f(u,v)
SELECT	BFS 找增广路（Edmonds-Karp）
COMBINE	沿增广路更新残余容量
重入	到不动点（无增广路）
TERMINATE	无增广路
求解方法	NESTED

嵌套结构：外层迭代找增广路 × 内层 BFS/DFS 搜索路径

→ 框架详解：Art. 0A — 图上的通用迭代机器

🔁 迭代机器视角 — Push-RelabelOPT: 优化目标

Graph	残余图
State[v]	excess(v) + height(v)
SELECT	活跃节点（excess > 0）
COMBINE	push: 沿可行边推送流量 / relabel: 提升高度
重入	到不动点（无活跃节点）
TERMINATE	无活跃节点（除 s, t）
求解方法	FI

→ 框架详解：Art. 0A — 图上的通用迭代机器

总结

本文建立了图上”流量”的完整工具箱：

流网络的基本框架：容量约束 + 流量守恒
最大流最小割定理：对偶性的力量——最大流 = 最小割，一个优化问题等价于一个组合问题
残余图和增广路：Ford-Fulkerson 方法的核心——在残余图中找增广路，推送流量，反向边允许”反悔”
Edmonds-Karp：BFS 找最短增广路， $O(VE^2)$ ，简单可靠
Dinic：分层图 + 阻塞流， $O(V^2 E)$ ，实践最快
MCMF：用最短费用路替代 BFS，同时优化流量和费用

从算法范式的角度：

增广路范式贯穿始终——每次在残余图中找到改善的路径，沿路径推进
对偶性（最大流 = 最小割）是理论核心——它不仅给出了终止条件，还揭示了最优解的结构

网络流是 Part 3”优”的基石。下一个自然的问题是：如何在图中找到最大匹配？ 下一篇 Art. 13: 匹配将展示，二部匹配就是单位容量网络流的特例——而一般匹配需要更精巧的工具。

实现指引

算法	库	函数/方法
最大流 (Edmonds-Karp)	NetworkX	`nx.maximum_flow(G, s, t, flow_func=edmonds_karp)`
最大流 (Dinic/默认)	NetworkX	`nx.maximum_flow(G, s, t)`
最大流值	NetworkX	`nx.maximum_flow_value(G, s, t)`
最小割	NetworkX	`nx.minimum_cut(G, s, t)`
最小费用最大流	NetworkX	`nx.max_flow_min_cost(G, s, t)`
最小费用流	NetworkX	`nx.min_cost_flow(G)`
最大流	scipy	`scipy.sparse.csgraph.maximum_flow(graph, source, sink)`
最大流	igraph	`g.maxflow(source, target, capacity)`
最小割	igraph	`g.mincut(source, target, capacity)`