想象这样一座城市：自来水厂通过粗细不一的管道向居民区供水，中途经过加压站、蓄水池和各种阀门。工程师最关心的两个问题是——这套管网最多能输送多少水？如果必须紧急切断一部分管道让水厂一滴水都送不到居民区，最少要“剪断”多大的输送能力？数学家把第一个问题写成“最大流”，把第二个问题写成“最小割”。更令人拍案叫绝的是：最大能送到的水量，恰好等于必须剪断的最小总粗细。这就是网络流与最小割定理。本文顺着这条供水管网，从“画地图”开始，一步步看懂流、割、残留网络与 Ford-Fulkerson 算法，把一场城市供水的调度故事讲成一张严谨的数学蓝图。

岗位关联

对 AI 从业者而言，网络流是图模型的通用翻译器：从物流调度到图像分割、从二分图匹配到社交网络瓶颈分析，它把真实世界问题抽象成可求解的数学结构，掌握它就是多了一套解决组合优化问题的核心工具箱。

目录
  1. 可视化演示
  2. 流网络定义
  3. 流量约束
  4. 割与割容量
  5. 核心定理
  6. 增广方法
  7. 残留网络
  8. 应用与建模
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

网络流研究流网络中的流量分配，最大流最小割定理是其核心结论。本文详解流与割的概念定义、容量约束与守恒约束、Fo... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

流网络的基本：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

流网络定义

市政工程师要规划供水，第一步永远是拿出一张城市管网图：自来水厂画在最左边，居民区画在最右边，中间的加压站、蓄水池、分岔阀门统统画成一个个圆点，管道画成带箭头的线段，箭头表示水流允许流动的方向。这张图就是数学里的“流网络”——圆点叫顶点，箭头叫有向边，而每根管道能承受的最大粗细，叫做容量。

翻译成严谨定义：一个有向图 $G=(V,E)$，其中 $V$ 是所有顶点的集合，$E$ 是所有有向边的集合。图中特别指定两个顶点：源点 $s$（自来水厂，只出不进）和汇点 $t$（居民区，只进不出）。每条边 $(u,v)$ 上挂着一个非负实数 $c(u,v)$，表示从 $u$ 到 $v$ 方向的容量，也就是这条管道每单位时间最多能通过多少水量。

有了这张“水管地图”，工程师就完成了网络流建模的第一步：抽象。在 AI 与算法工作中，这一步对应“把实际问题翻译成图结构”——节点、边、容量分别由业务对象、关系、上限约束决定。

G=(V,E),c:V×V→R≥0\displaystyle G = (V, E), \qquad c: V \times V \to \mathbb{R}_{\ge 0}
这个公式的意思是：流网络由顶点集、边集和一个“容量函数”组成。容量函数就是给每一条可能的“管道”分配一个最大输送值。
  1. 顶点集合$V$ 包含网络中所有节点，即水厂、加压站、居民区等。
    V={v1,v2,…,vn}V = \{ v_1, v_2, \ldots, v_n \}
  2. 有向边集合$E$ 是所有带方向的管道，$(u,v)$ 表示水只能从 $u$ 流向 $v$。
    E⊆V×VE \subseteq V \times V
  3. 容量函数$c(u,v)$ 给出从 $u$ 到 $v$ 方向的最大输送量，非负实数。
    c(u,v)≥0c(u,v) \ge 0

流量约束

地图画好了，水真的开始流。很快工程师发现两条铁律：第一，任何管道里的水都不能超过它的粗细，否则会爆管；第二，中间那些加压站和蓄水池不能蓄水、也不能凭空变出水来——单位时间内流进去多少，就必须流出来多少。这两条铁律在数学上分别叫容量约束与流量守恒约束。

实际水流的大小用函数 $f(u,v)$ 表示，$f(u,v)$ 是边 $(u,v)$ 上的流量。容量约束要求 $0 \le f(u,v) \le c(u,v)$，即每条边上的水非负且不超过管道粗细。守恒约束要求对任意既不是源点也不是汇点的中间顶点 $u$，流入总量等于流出总量：$\sum_v f(u,v) = \sum_w f(w,u)$。整张网络中，源点的净流出量正好等于汇点的净流入量，这个共同值就是网络的总流量 $|f|$。

想象一个蓄水池：进水管一瞬间涌进 100 立方米，出水管却只排出 60 立方米，多出的 40 立方米必然导致水池漫顶——这就是守恒约束在物理世界的朴素直觉。后续增广算法能放心地“在账本上移动流量”，正是因为守恒约束保证整体水量始终对得上。

0≤f(u,v)≤c(u,v)(容量约束)∑v∈Vf(u,v)=∑w∈Vf(w,u)(守恒约束, u≠s,t)\begin{aligned}0 \le f(u,v) &\le c(u,v) & &\text{(容量约束)} \\\sum_{v \in V} f(u,v) &= \sum_{w \in V} f(w,u) & &\text{(守恒约束, } u \ne s, t \text{)}\end{aligned}
上面两组不等式与等式定义了一个“可行流”：既不爆管（容量约束），又不中途丢水或变水（守恒约束）。
  1. 容量约束每条管道的水量不超过管径上限，也不允许出现负流量（水不会自己倒流）。
    0≤f(u,v)≤c(u,v)0 \le f(u,v) \le c(u,v)
  2. 守恒约束中间节点流入等于流出，这是“水不凭空消失”的数学表达。
    ∑v∈Vf(u,v)=∑w∈Vf(w,u)\sum_{v \in V} f(u,v) = \sum_{w \in V} f(w,u)
  3. 总流量口径总流量 $|f|$ 等于源点的总流出量，也等于汇点的总流入量。
    ∣f∣=∑v∈Vf(s,v)=∑u∈Vf(u,t)|f| = \sum_{v \in V} f(s,v) = \sum_{u \in V} f(u,t)

割与割容量

假设市政安全检查员要做一个极端演练：剪断若干管道，让自来水厂的水一滴都送不到居民区。他并不需要真的把所有管道都剪断，只要在图上画一条“分界线”，把水厂划到左边、居民区划到右边，凡是跨过分界线的管道统统剪断，就能保证两岸“断流”。这条分界线在数学上叫作割。

形式上，割是顶点集 $V$ 的一个二分 $(S, T)$：$S \cup T = V$、$S \cap T = \varnothing$，并且源点 $s \in S$、汇点 $t \in T$。割容量定义为所有从 $S$ 指向 $T$ 的边的容量之和——也就是安全检查员剪断管道后失去的总输送能力。注意：从 $T$ 指向 $S$ 的边不算数，因为水流方向是从 $S$ 到 $T$，反向边本来就送不到对岸。

检查员最后发现：分界线离水厂越近、剪的管道越粗，断供越彻底，但总代价也越大。最小割回答的就是“代价最小的断供方案是哪一条分界线”。之所以要先讲割，是因为它是理解最大流极限的钥匙——任何从 $s$ 到 $t$ 的水，都必然要跨过任意一条分界线。

c(S,T)=∑u∈S∑v∈Tc(u,v)\displaystyle c(S, T) = \sum_{u \in S} \sum_{v \in T} c(u, v)
割容量就是“从左边阵营指向右边阵营的所有边容量加起来”。分界线位置不同，剪断的管道也不同，割容量自然有大有小。
  1. 顶点划分把全体顶点分成互不重叠的 $S$、$T$ 两拨，源点必须属于 $S$，汇点必须属于 $T$。
    S∪T=V,S∩T=∅,s∈S, t∈TS \cup T = V, \quad S \cap T = \varnothing, \quad s \in S, \ t \in T
  2. 方向性求和只累加从 $S$ 中顶点指向 $T$ 中顶点的边的容量。
    ∑u∈S∑v∈Tc(u,v)\sum_{u \in S} \sum_{v \in T} c(u, v)
  3. 最小割问题在所有合法的割中，找割容量最小的那个，就是最省事的“断供方案”。
    min⁡(S,T)c(S,T)\min_{(S,T)} c(S,T)

核心定理

工程师做了无数次实验：无论怎么调度阀门，最大送水量始终稳定在一个数字上；无论检查员怎么画分界线，最小割容量也始终是同一个数字。两个数字完全相等。这不是巧合，而是著名的最大流最小割定理。它给出一个惊人的结论：网络的最大流值，等于最小割容量。

定理同时给出三个等价的表述：存在一个可行流 $f$ 达到最大值；存在一个割 $(S,T)$ 使 $|f| = c(S,T)$；在残留网络中不存在从 $s$ 到 $t$ 的增广路。这三条只要有一条成立，其余全部成立。这为算法设计提供了终止判据——当残留网络中再也找不到任何可增广路径时，当前流就已经是最大流。

为什么最大流受限？因为任何从 $s$ 到 $t$ 的水都必须穿过任意一条分界线，所以最大流永远不超过任何割容量；而最大流之所以上不去，本质是某条分界线上的管道被全部灌满，堵住了所有去路。瓶颈即天花板——这就是定理最直观的物理图景，也是后续求最小割的思路来源。

max⁡f∣f∣  =  min⁡(S,T)c(S,T)\displaystyle \max_{f} |f| \;=\; \min_{(S, T)} c(S, T)
这个公式把两个看似无关的优化问题焊在一起：左边是“最多能送多少水”，右边是“最少剪断多大总容量”，两者恒等。
  1. 最大流在所有满足容量与守恒约束的可行流中，总流量的上确界就是最大流。
    max⁡f∣f∣\max_{f} |f|
  2. 最小割在所有合法的顶点二分中，割容量的下确界就是最小割。
    min⁡(S,T)c(S,T)\min_{(S, T)} c(S, T)
  3. 等式成立两个极值相等，说明“送水上限”恰好由“最窄瓶颈”决定。
    max⁡f∣f∣=min⁡(S,T)c(S,T)\max_{f} |f| = \min_{(S, T)} c(S, T)

增广方法

知道了“瓶颈即天花板”，怎么把水真正送满？Ford-Fulkerson 方法给出一个笨拙却有效的策略：每次找一条从水厂到居民区还有余量的路线，把能灌的水尽量灌进去，反复进行，直到找不到任何一条余量路线为止。 这条有余量的路线叫增广路，它的“余量”由路径上最细的管道决定，称为瓶颈值。

算法流程是：从零流量开始，在残留网络中反复找 $s$ 到 $t$ 的增广路 $p$，计算路径上最小的残留容量 $\delta$，然后把路径上每条边的流量都增加 $\delta$，同时更新残留网络。当残留网络中不存在 $s$ 到 $t$ 的路径时，由核心定理保证当前流就是最大流。形象地说，每次增广就像“往一条还有富余的管线里再灌一桶水”，直到所有管线都被灌到极限。

Ford-Fulkerson 的复杂度与 $\delta$ 的取值方式密切相关。若每次用 BFS 找最短增广路（Edmonds-Karp 改进），复杂度为 $O(VE^2)$，与容量数值无关；若盲目选路且容量为无理数，算法甚至可能无限循环。因此实际工程与竞赛中，常用 BFS 版或更快的 Dinic 算法，原理仍然是“反复增广直到无路可走”。

f′(u,v)=f(u,v)+δ,δ=min⁡(x,y)∈pcf(x,y)\displaystyle f'(u,v) = f(u,v) + \delta, \qquad \delta = \min_{(x,y) \in p} c_f(x,y)
公式说明：一次增广把所有位于增广路径 $p$ 上的边的流量统一加上 $\delta$，而 $\delta$ 是这条路径上最小的残留容量。
  1. 瓶颈值$\delta$ 是增广路 $p$ 上所有边残留容量的最小值，决定这次能灌多少水。
    δ=min⁡(x,y)∈pcf(x,y)\delta = \min_{(x, y) \in p} c_f(x, y)
  2. 流量更新路径上每条边的流量统一增加 $\delta$，同时反向边的残留容量也相应增加。
    f′(u,v)=f(u,v)+δf'(u,v) = f(u,v) + \delta
  3. 终止条件当残留网络中 $s$ 无法到达 $t$ 时，不存在增广路，算法结束。
    ∄ s-t 路径 in Gf\nexists\, s \text{-} t \text{ 路径 in } G_f

残留网络

增广时工程师遇到一个难题：某条管道已经灌满了水，可后来发现的更优路线需要“借用”这条管道的容量，怎么办？答案是：允许“退水”。之前流过的水量可以在账本上记一笔“可退还额度”，相当于在反方向画一条虚拟管道。这张包含了正向余量和反向额度的图，就是残留网络，也叫余量网络。

残留网络 $G_f$ 中，每条原边 $(u,v)$ 对应两条“账本边”：正向残留容量 $c_f(u,v) = c(u,v) - f(u,v)$，表示还差多少灌满；反向残留容量 $c_f(v,u) = f(u,v)$，表示最多还能退回多少。增广路正是在 $G_f$ 中查找 $s$ 到 $t$ 的路径。反向边的存在让算法可以“撤销”之前糟糕的流量分配，这是 Ford-Fulkerson 能收敛到最大流的关键。

把残留网络想象成供水公司的记账本：正向是“还能往这根管里灌多少”，反向是“这笔水之前在别处送过、可以调回来”。真实水流永远从源到汇，但账本允许流量在中间环节重新分配，这正是增广算法灵活性的来源。

cf(u,v)=c(u,v)−f(u,v),cf(v,u)=f(u,v)\displaystyle c_f(u,v) = c(u,v) - f(u,v), \qquad c_f(v,u) = f(u,v)
两个式子分别给出“还能灌多少”与“还能退多少”。残留网络把所有正向余量和反向额度画在一张图上，增广路就在这张图上寻找。
  1. 正向残留$u$ 到 $v$ 方向还剩多少容量，等于原容量减去已用流量。
    cf(u,v)=c(u,v)−f(u,v)c_f(u,v) = c(u,v) - f(u,v)
  2. 反向残留$v$ 到 $u$ 方向的额度等于已流过的流量，代表可以退还的水量。
    cf(v,u)=f(u,v)c_f(v,u) = f(u,v)
  3. 阻塞流判定若 $G_f$ 中 $s$ 无法到达 $t$，说明不存在增广路，当前流是最大流。
    distGf(s,t)=∞  ⟹  f 是最大流\text{dist}_{G_f}(s, t) = \infty \implies f \text{ 是最大流}

应用与建模

这套供水逻辑一旦抽象成“节点—边—容量”三元组，就能搬到无数领域。最经典的应用是二分图最大匹配：把左侧节点（如求职者）连到源点，右侧节点（如岗位）连到汇点，左右之间的可行配对边容量设为 1，跑一次最大流，流量值就是最大匹配数。其次是最小割转化：许多带惩罚的划分问题可以建模成“最小割”，例如图像分割中把像素当顶点、相邻像素间连容量为“不相似度”的边，用户标出前景与背景种子后，最小割给出干净的分割边界。竞赛中求最小割的标准做法是：先跑一次最大流，再从源点在残留网络中做 BFS，所有可达顶点构成 $S$，最小割就是 $(S, V \setminus S)$。

建模时的核心公式是净流量恒等式：对任意割 $(S,T)$，跨割的净流量等于总流量，因此最大流恰好把最小割的所有正向边灌满、反向边归零。

从供水管网到算法竞赛，所有的故事都在讲同一件事：把真实系统的“上限”翻译成容量，把“流动关系”翻译成边，然后让最大流最小割定理替我们回答“极限是多少、瓶颈在哪里”。建模的功力，往往比算法的优化更决定最终效果。

∣f∣=∑u∈S∑v∈Tf(u,v)−∑a∈S∑b∈Tf(b,a)\displaystyle |f| = \sum_{u \in S} \sum_{v \in T} f(u,v) - \sum_{a \in S} \sum_{b \in T} f(b,a)
该式说明：总流量等于“从 $S$ 流向 $T$ 的流量”减去“从 $T$ 流向 $S$ 的流量”。当达到最大流时，跨最小割的正向边全部满流，反向边流量为 0。
  1. 净流量跨越任意分界线的净水流等于总流量，这是守恒约束的直接推论。
    ∣f∣=∑u∈S∑v∈Tf(u,v)−∑b∈T∑a∈Sf(b,a)|f| = \sum_{u \in S} \sum_{v \in T} f(u,v) - \sum_{b \in T} \sum_{a \in S} f(b,a)
  2. 满流条件若 $|f| = c(S,T)$，则所有 $S \to T$ 边都达到容量上限。
    f(u,v)=c(u,v),∀(u,v)∈(S×T)∩Ef(u,v) = c(u,v), \quad \forall (u,v) \in (S \times T) \cap E
  3. 最小割还原最大流结束后，从源点在残留网络中可达的顶点集合即为最小割的 $S$ 侧。
    S={v∣s⇝v in Gf}S = \{ v \mid s \rightsquigarrow v \text{ in } G_f \}

AI 应用场景

物流网络吞吐量分析

阶段：数据处理与优化建模

解决的问题：传统物流排程靠人工经验判断瓶颈，当网络有数百个中转站时，根本无法算出“同时最多能发多少货”。把仓库当源点、客户区当汇点、路段运力上限当容量，建流网络后最大流直接给出理论吞吐上限，最小割则精准定位“绕不开的关键路段”。

具体案例：某同城生鲜配送公司每天凌晨从 3 个总仓向 200 多个前置仓发货，受潮汐限行影响，各路段容量随时间变化。算法工程师把路网建成带容量有向图，用 Edmonds-Karp 算出当天最大可发运量，再用最小割发现 5 条关键路段是“咽喉”，据此调整车辆调度，吞吐量提升约 30%。

图像交互式分割中的最小割

阶段：计算机视觉模型的数据预处理

解决的问题：训练语义分割模型需要大量干净的前景遮罩，手动抠图费时费力。图割（Graph Cut）把每个像素当顶点、相邻像素连边，边容量设为“颜色越不相似，惩罚越大”，用最小割把像素划分成前景与背景。

具体案例：经典的 GrabCut 方案中，用户在手机相册里圈出人脸区域，系统在像素图上建流网络，把用户标注的前景接到源点、背景接到汇点，跑一次最大流即可还原最小割，一秒内输出透明背景抠图。该技术常被用于自动生成 AI 训练集的初始标注，再由人工微调。

社交网络传播规模估算

阶段：网络分析与时序预测

解决的问题：运营团队想估算“活动从种子用户出发最多影响多少人”，但每个用户接收转发的意愿有上限。把用户当节点、关注关系当有向边、“每天最多接受几条传播”当容量，最大流给出传播规模的理论上界，最小割则找出最容易阻断传播扩散的关键关注关系。

具体案例：某内容平台的活动运营用 50 万用户的关注关系建流模型，发现一个百万粉 KOL 的粉丝接收容量是传播“瓶颈”，于是在该节点附近增投两个中腰部创作者，整体传播上限预估提升约 3 倍。

Python 演示

python54 行
from collections import defaultdict, deque class NetworkFlow:    def __init__(self, n):        self.n = n        self.graph = defaultdict(dict)     def add_edge(self, u, v, cap):        self.graph[u][v] = cap        self.graph[v].setdefault(u, 0)     def bfs(self, s, t, parent):        visited = {s}        q = deque([s])        while q:            u = q.popleft()            for v, cap in self.graph[u].items():                if v not in visited and cap > 0:                    parent[v] = u                    if v == t:                        return True                    visited.add(v)                    q.append(v)        return False     def max_flow(self, s, t):        flow = 0        parent = {}        while self.bfs(s, t, parent):            path_flow = float('inf')            v = t            while v != s:                u = parent[v]                path_flow = min(path_flow, self.graph[u][v])                v = u            v = t            while v != s:                u = parent[v]                self.graph[u][v] -= path_flow                self.graph[v][u] += path_flow                v = u            flow += path_flow        return flow  if __name__ == '__main__':    nf = NetworkFlow(4)    nf.add_edge(0, 1, 3)    nf.add_edge(0, 2, 2)    nf.add_edge(1, 2, 1)    nf.add_edge(1, 3, 2)    nf.add_edge(2, 3, 3)    ans = nf.max_flow(0, 3)    print('最大流 =', ans)
目的：用 Edmonds-Karp 算法（BFS 版 Ford-Fulkerson）求解一个 4 节点供水网络的 最大流，输出最大流值 5，与最小割容量一致。
  1. self.graph = defaultdict(dict)用邻接表存图，每个顶点映射到它的邻居与容量。
  2. self.graph[v].setdefault(u, 0)给每条边预置反向容量 0，残留网络需要双向记账。
  3. def bfs(self, s, t, parent)BFS 在残留网络中找一条从源点到汇点的增广路。
  4. if v not in visited and cap > 0只走还有正残留容量的边，满流边跳过。
  5. path_flow = min(path_flow, self.graph[u][v])取路径上最小的残留容量作为本次增广量。
  6. self.graph[u][v] -= path_flow正向残留容量减少，相当于“灌进去 δ 单位水”。
  7. self.graph[v][u] += path_flow反向残留容量增加，相当于账本上记下“可退还 δ”。
  8. flow += path_flow把本次增广量累加到总流量。
  9. nf.add_edge(0, 1, 3)建图：源点 0 到顶点 1 的容量为 3，对应供水管的粗细。
  10. ans = nf.max_flow(0, 3)从源点 0 到汇点 3 求最大流，得到答案 5。

常见误区

误区我以为最小割就是找出几条最细的管子剪掉，“割”应该是一组被剪断的边，边越少越好吧？

正解割其实是顶点的二分 $(S,T)$，只要求源点在 $S$、汇点在 $T$，跨界的边才是被“剪断”的管道。同一个割对应唯一一组跨界边，但“割到什么”由分界线（顶点划分）决定，而不是由边决定。最小割比的是跨界边容量之和，与边数无关。

为何常见：“割”这个字天然让人联想到“切开”的动作和“切下来的物体”，初学者容易把数学对象误当成被切下的边集。

误区残留网络里画了反向边，难道水流真的会从居民区倒回水厂？物理上不合理吧？

正解反向边只是“账本额度”，表示先前沿该方向流过的流量可以被撤销、调配给其他路径。真实水流始终从源到汇，反向边是算法用来纠正次优决策的撤销机制，不是真实管道。

为何常见：残留网络把正向容量与反向退水量画在同一张图上，初学者一眼看去误以为存在双向物理管道。

误区每次找一条增广路，感觉迭代次数应该不会太多，复杂度应该和边数差不多吧？

正解若随意选路且容量为无理数，算法甚至可能不终止；即使容量为整数，最坏情况也可能需要与最大流值同量级的迭代次数。实际中常用 BFS 版（Edmonds-Karp）保证 $O(VE^2)$，或用 Dinic 等更高效算法。

为何常见：教材上常画“每次增广一大段”的示意图，让人误以为迭代次数等于增广路数量级，忽略了选路顺序对效率的致命影响。

误区最小割嘛，肯定就是剪断最少条管道就对了，跟管道粗细没关系。

正解割的“大小”是比较跨边界边的容量之和，不是比较边数。一条粗管道被剪断可能抵得上十条细管道，所以最小割要找的是“总粗细最小”的断供方案，而不是“根数最少”的方案。

为何常见：日常语言中“最小”常与“数量最少”绑定，而图论中“最小”针对的是有容量权重的总和，权重概念需要额外训练。

误区我觉得只要每条边上的流量都不超过容量，就是一个合法的流了。

正解还必须有守恒约束：除源点和汇点外，每个中间节点的流入量必须等于流出量。否则在数值上“合法”的方案在物理上不可能实现——水会在中间节点凭空出现或消失。两个约束缺一不可。

为何常见：容量约束写在定义最前面、最显眼，初学者容易把它当成唯一要检查的条件，忽略了守恒约束这个“看不见的平衡”。

面试题

Q1. 在流网络 $G=(V,E)$ 中，容量函数 $c(u,v)$ 的正确含义是？

单选题 · easy

  • A.从 $v$ 到 $u$ 方向的最大输送能力
  • B.从 $u$ 到 $v$ 方向的最大输送能力← 正确答案
  • C.整条管道的长度
  • D.单位时间的用电量

答案：B。容量函数 $c(u,v)$ 表示从顶点 $u$ 到顶点 $v$ 方向允许通过的最大流量，类似水管的粗细。A 把方向搞反了；C、D 与容量无关。

Q2. 流量守恒约束对中间节点 $u$ 的要求是？

单选题 · easy

  • A.流入等于流出← 正确答案
  • B.流入大于流出
  • C.流入小于流出
  • D.流量等于容量

答案：A。中间节点不能蓄水也不能变水，所以流入总量必须等于流出总量，就像蓄水池的进出水平衡。D 是容量约束而非守恒约束。

Q3. 残留网络中反向边 $c_f(v,u) = f(u,v)$ 的作用是什么？

单选题 · mid

  • A.表示真实水流从 $v$ 倒流回 $u$
  • B.提供撤销已流量的调节额度← 正确答案
  • C.表示 $v$ 到 $u$ 有物理管道
  • D.强制流量不超过容量

答案：B。反向边是账本上的“可退水量”，允许算法在后续增广时重新调配之前分配不好的流量，从而实现全局最优，而不是真实倒流。

Q4. 割 $(S,T)$ 的割容量 $c(S,T)$ 如何计算？

单选题 · mid

  • A.$S$ 与 $T$ 之间所有边容量之和（双向）
  • B.从 $S$ 指向 $T$ 的所有边容量之和← 正确答案
  • C.从 $T$ 指向 $S$ 的所有边容量之和
  • D.$S$ 与 $T$ 之间的边数

答案：B。割容量只统计从 $S$ 侧指向 $T$ 侧的边的容量之和，因为水流方向是从源到汇，反向边不影响 $s$ 到 $t$ 的连通。A 方向没区分，D 混淆了边数与容量权重。

Q5. Ford-Fulkerson 方法每次迭代在残留网络中寻找什么？

单选题 · single

  • A.最短路径
  • B.增广路← 正确答案
  • C.欧拉回路
  • D.哈密顿路径

答案：B。每次迭代找一条从 $s$ 到 $t$ 且所有边残留容量为正的路径，即增广路，然后按瓶颈值增加流量。直到找不到增广路时，由最大流最小割定理知当前流已是最大流。

Q6. 关于最大流最小割定理，下列说法正确的有？

多选题 · mid

  • A.最大流的值等于最小割的容量← 正确答案
  • B.残留网络中无增广路说明还没达到最大流
  • C.存在一个割使得 $|f| = c(S,T)$ 且 $f$ 是最大流← 正确答案
  • D.割边数最少的割就是最小割

答案：AC。定理保证 $\max |f| = \min c(S,T)$，且存在达到该等式的割与流，故 A、C 正确。B 说反了，无增广路恰恰说明已达最大流；D 错，最小割比较的是容量总和而非边数。

Q7. Edmonds-Karp 算法（BFS 选最短增广路）的时间复杂度是？

单选题 · mid

  • A.$O(VE)$
  • B.$O(VE^2)$← 正确答案
  • C.$O(V^2 E^2)$
  • D.$O(E^2)$

答案：B。BFS 版 Ford-Fulkerson 保证最多 $O(VE)$ 次增广，每次 BFS 花费 $O(E)$，总复杂度 $O(VE^2)$。A 少乘了一个 $E$，C、D 是常见错误记忆。

Q8. 图像分割中最小割建模的主要思路是？

单选题 · mid

  • A.把像素当顶点，分割当成顶点二分← 正确答案
  • B.把颜色值直接相加
  • C.用最大流求最短路径
  • D.把图像压缩成树

答案：A。图像分割把每个像素当顶点，相邻像素连边，边容量表示不相似度，用户标注的前景/背景接到源点/汇点，最小割即给出前景背景划分，这正是图割算法的核心思想。

Q9. 将二分图最大匹配转化为最大流，正确的建模方式包括？

多选题 · hard

  • A.源点连接每个左侧节点，容量为 1← 正确答案
  • B.左侧节点连接右侧节点，容量为 1← 正确答案
  • C.右侧每个节点连接汇点，容量为 1← 正确答案
  • D.源点直接连接汇点，容量为无穷

答案：ABC。标准转化是：源点→左部每个点容量 1，左部→右部按匹配关系连容量 1，右部→汇点容量 1，最大流值等于最大匹配数。D 会直接形成从源到汇的大流量捷径，破坏建模。

Q10. 在 Ford-Fulkerson 中，若每次增广量都是 1 且最大流值为 $K$，最坏情况下算法迭代次数的量级是？

单选题 · extreme

  • A.$O(1)$
  • B.$O(K)$← 正确答案
  • C.$O(E)$
  • D.$O(V)$

答案：B。每次增广只增加 1 单位流量时，需要约 $K$ 次迭代才能达到最大流，复杂度与流量数值 $K$ 相关，这正是朴素 Ford-Fulkerson 可能很慢的原因。因此实际常用 BFS 选最短路来避免这种退化。