6.4 Maximum Flow：残量网络、增广路径与最小割证书

6.4 · Maxflow覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“6.4 · Maxflow”如何用容量、流量、残量网络与增广路径建立最大流和最小割的双向证书
能逐项核对最大流、最小s-t割、残量网络、增广路径、最大流最小割定理、二分图匹配，并区分作者站内容与本页独立补充
能按“残量 r(e)=capacity-flow（正向）或 flow（反向）；增广量为路径最小残量”手算一个最小输入，逐步检查“每条边满足 0≤flow≤capacity，非源汇点流量守恒，最终残量图中汇点不可达”
能注入“只保留正向剩余容量而遗漏反向残量边，使早期错误选择无法撤销”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“6·4 · Maxflow”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“6·4 · Maxflow”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“6·4 · Maxflow”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：6.4 · Maxflow

1. 最大流：在本页通过“初始化零流”连接解释、交互状态和练习验收。
2. 最小s-t割：在本页通过“在残量图找 s-t 路径”连接解释、交互状态和练习验收。
3. 残量网络：在本页通过“计算瓶颈”连接解释、交互状态和练习验收。
4. 增广路径：在本页通过“更新正反向残量”连接解释、交互状态和练习验收。
5. 最大流最小割定理：在本页通过“验证守恒与最小割”连接解释、交互状态和练习验收。
6. 二分图匹配：在本页通过“初始化零流”连接解释、交互状态和练习验收。

从“走错的流量能不能撤回来”开始

最大流（maximum flow）不是简单找一条widest path。Flow可同时走many paths，而且early path choice可能占用后续更重要的capacity。

先预测：若第一次把5 units送过edge u→v，后来发现更好solution需要把其中2 units改走另一branch，algorithm是否必须从头重算？不必。Residual network提供v→u的backward capacity 5，让下一条增广路径撤销一部分旧flow。

一个flow state必须先可行，再谈optimal。Flow value是source net outflow，也等于sink net inflow。

6.4.1 Flow network与feasible flow

Flow network (G=(V,E)) 有source s、sink t。每条directed edge (e=(v,w)) 有nonnegative capacity (c(e)) 与flow (f(e))。

Capacity constraint：

0\le f(e)\le c(e)

对每个internal vertex (v\ne s,t)，flow conservation：

\sum_{e:\,e.to=v}f(e) = \sum_{e:\,e.from=v}f(e)

Flow value：

|f| =\sum_{e:\,e.from=s}f(e)-\sum_{e:\,e.to=s}f(e)

Official FlowNetwork把同一FlowEdge object加入both endpoints的adjacency lists，因为residual traversal必须从tail和head都能看到它。Parallel edges与self-loops允许；遍历all edges时要避免把同一edge重复计数。

6.4.2 FlowEdge：一个original edge，两种residual directions

对original edge (e=v\to w)：

c_f(v,w)=c(e)-f(e)

是forward residual capacity，可继续增加flow；

c_f(w,v)=f(e)

是backward residual capacity，可取消已有flow。

Official API以destination endpoint表达direction：

double residualCapacityTo(int vertex) {
    if      (vertex == v) return flow;              // backward
    else if (vertex == w) return capacity - flow;   // forward
    else throw new IllegalArgumentException();
}
 
void addResidualFlowTo(int vertex, double delta) {
    if      (vertex == v) flow -= delta;
    else if (vertex == w) flow += delta;
    else throw new IllegalArgumentException();
}

同一edge不需要显式创建two residual edge objects，但algorithm概念上必须看到both directions。Residual update后仍要保证flow在0和capacity之间；official code把距离boundary (10^-10) 内的value snap到0或capacity。

6.4.3 Residual networks：当前flow还能怎样改变

残量网络（residual networks）记作 (G_f)。

Residual path不等于original directed path。若path从w沿backward arc到v，augmentation会减少original (v\to w) flow。Cancellation是Ford-Fulkerson correctness的关键；没有backward arcs，greedy first path可永久锁死suboptimal decision。

Residual adjacency在official implementation中遍历G.adj(v)，对incident edge取other(v)，再问residualCapacityTo(w)。只有strictly positive residual capacity的arc可搜索。

6.4.4 Augmenting path与bottleneck

增广路径（augmenting paths）P可增加的maximum amount是bottleneck：

\Delta=\min_{e\in P}c_f(e)

沿P每个forward residual arc增加 (\Delta)，每个backward residual arc减少 (\Delta)。至少一条residual arc被saturate，flow value增加 (\Delta)。

double bottle = Double.POSITIVE_INFINITY;
for (int v = t; v != s; v = edgeTo[v].other(v))
    bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
 
for (int v = t; v != s; v = edgeTo[v].other(v))
    edgeTo[v].addResidualFlowTo(v, bottle);
value += bottle;

Augmentation保持feasibility：bottleneck不超过任何arc residual，所以edge bounds不破；path internal vertices获得一入一出equal delta，conservation不变；source净outflow与sink净inflow各增加delta。

6.4.5 Ford-Fulkerson与Edmonds-Karp

Ford-Fulkerson framework反复：

在residual network找任意s→t path。
求bottleneck。
Augment。
无path时stop。

Path strategy影响termination与complexity。Official FordFulkerson.java用BFS找fewest-edge residual path，也就是Edmonds-Karp：

Queue<Integer> queue = new Queue<>();
queue.enqueue(s);
marked[s] = true;
while (!queue.isEmpty() && !marked[t]) {
    int v = queue.dequeue();
    for (FlowEdge e : G.adj(v)) {
        int w = e.other(v);
        if (e.residualCapacityTo(w) > 0 && !marked[w]) {
            edgeTo[w] = e;
            marked[w] = true;
            queue.enqueue(w);
        }
    }
}

BFS一次O(E+V)。Edmonds-Karp augmentation count O(VE)，total：

O\bigl(VE(E+V)\bigr)

Connected/sparse conventions下常写O(VE²)。Official section概括为 (E^2V)，current class documentation给更完整 (EV(E+V))。Extra marked、edgeTo与queue O(V)。

If all capacities/initial flows areintegers，bottleneck integer，all intermediate flows保持integer，得到integral maxflow。Official floating implementation说明：若integer arithmetic exact且maxflow不超过 (2^52)，double能精确表示这些integers；一般real capacities需审慎tolerance。

6.4.6 Minimum s-t cut：任何cut都是flow上界

最小s-t割（minimum s-t cut）((S,T)) 的capacity：

c(S,T)=\sum_{e:\,e.from\in S,\ e.to\in T}c(e)

对任意feasible flow：

|f|\le c(S,T)

Proof：Internal flows在S内cancel，net离开S的flow等于flow value；S→T edges各不超过capacity，T→S flow只会减少net crossing。所以每个cut都给primal flow的upper bound。

6.4.7 无augmenting path时，final BFS给出min cut

Algorithm终止时，令S为residual network中从s reachable的vertices，T为其余vertices。T含sink，因为无augmenting path。

对every original edge crossing S→T，forward residual必须0，否则head也reachable，所以它saturated。对every edge crossing T→S，backward residual必须0，否则tail可被reached，所以其flow为0。

因此：

|f| =f(S,T)-f(T,S) =c(S,T)

Feasible flow达到某cut upper bound，二者同时optimal。

6.4.8 Maxflow-mincut theorem与双证书

最大流最小割定理（maxflow-mincut theorem）给出比“algorithm停止”更强的可检验证据。

Certificate由两部分组成：

Primal：每条edge flow、capacity bounds、all internal conservation、reported value。
Dual：vertex set S，满足s in S、t outside S，cut capacity等于reported value。

Verifier不必重跑maxflow；只需O(E+V)检查feasibility、partition与equality，就能证明optimal。Official check()正是先isFeasible，再核对source/sink cut membership，最后sum crossing capacities并与value比较。

6.4.9 Bipartite matching reduction

二分图匹配（bipartite matching）可归约为unit-capacity maxflow：

新建source s，向每个left vertex连capacity 1。
每条allowed left-right edge设capacity 1。
每个right vertex向sink t连capacity 1。

Integral maxflow中的unit flow left→right edges形成matching：left/source edge与right/sink edge capacity 1阻止重复使用vertex。反过来，size-k matching可构造value-k flow，所以maximum values equal。

这个归约展示maxflow不只是routing：edge-disjoint paths、vertex-disjoint paths（vertex splitting）、baseball elimination、image segmentation等都可编码为capacity constraints。

6.4.10 Modeling boundaries与failure modes

建模前需明确：

Directed vs undirected：undirected capacity通常转two directed edges，但semantics要确认。
Lower bounds/demands：普通FlowEdge只处理0 lower bound。
Multiple sources/sinks：加super-source/super-sink。
Vertex capacities：split each vertex into in/out with capacity edge。
Costs：minimum-cost flow不是plain maxflow。
Gains/losses：conservation equation要变，不能直接套用。

FlowNetwork允许parallel edges和self-loops。Verifier必须按edge identity而不是endpoint pair聚合更新，否则parallel flows会被错误合并。

Floating residual comparison > 0可能把tiny numerical noise当path。Official edge snaps near boundary，feasibility/check使用epsilon；production应根据capacity scale定义tolerance或使用integer/rational units。

6.4.11 Independent certificate

for (const edge of edges) assert(0 <= edge.flow && edge.flow <= edge.capacity);
 
for (const vertex of internalVertices)
  assert(nearlyEqual(inflow(vertex), outflow(vertex)));
 
assert(cut.has(source) && !cut.has(sink));
const cutCapacity = edges
  .filter((e) => cut.has(e.from) && !cut.has(e.to))
  .reduce((sum, e) => sum + e.capacity, 0);
assert(nearlyEqual(flowValue, cutCapacity));

Mutation tests应覆盖capacity violation、internal leak、wrong reported value、cut未分离s/t、wrong cut membership、missing parallel edge与backward residual update sign。只检查no augmenting path不够，因为candidate initial flow可能本身infeasible。

6.4.12 逐步运行路线

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“6.4 · Maxflow”的两个最小情境间切换，再逐项选择正式概念。预测“残量 r(e)=capacity-flow（正向）或 flow（反向）；增广量为路径最小残量”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

6.4 · Maxflow：对象、操作与不变量

用容量、流量、残量网络与增广路径建立最大流和最小割的双向证书

选择最小情境

切换正式概念

撤销旧流: 早期增广占用了后续更优路径需要的边
当前观察: maximum flow：反向残量边允许减少旧流并重新路由

残量 r(e)=capacity-flow（正向）或 flow（反向）；增广量为路径最小残量

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

最大流：在实验 1 中指出对应状态，并写出一个通过条件。
最小s-t割：在实验 2 中指出对应状态，并写出一个通过条件。
残量网络：在实验 3 中指出对应状态，并写出一个通过条件。
增广路径：在实验 1 中指出对应状态，并写出一个通过条件。
最大流最小割定理：在实验 2 中指出对应状态，并写出一个通过条件。
二分图匹配：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“残量 r(e)=capacity-flow（正向）或 flow（反向）；增广量为路径最小残量”不是孤立结论？

问题 3：故障恢复。 怎样证明“只保留正向剩余容量而遗漏反向残量边，使早期错误选择无法撤销”已经修复？

保存容量/流量、残量边、增广路径、瓶颈、守恒差、最终 s-cut 与 cut capacity作为正常基线；注入该故障并标记第一个违反“每条边满足 0≤flow≤capacity，非源汇点流量守恒，最终残量图中汇点不可达”的状态；撤销后用完全相同的输入、版本和随机种子重放。只有全部状态与独立预言机重新一致，才可发布修复结论。

小结

Maximum flow要求capacity constraints与internal flow conservation。
Residual networks为每条original edge提供forward unused capacity与backward cancellable flow。
Augmenting paths在residual network中连接s到t，bottleneck是minimum residual capacity。
Official FordFulkerson使用BFS shortest augmenting paths，即Edmonds-Karp。
No augmenting path时final BFS marked set给minimum s-t cut的source side。
Maxflow-mincut theorem说明maximum flow value等于minimum cut capacity。
Feasible flow与equal-capacity cut组成O(E+V)可验的optimality certificate。
Unit-capacity network把bipartite matching归约为integral maxflow。
Parallel edges、floating tolerance与model transformation必须写进contract。