Ford–Fulkerson 方法

一次增广把整条残量路看成可同时调整的方向链，瓶颈是这次最多能推多少。正向记录使用尚空容量，反向记录撤销旧流；早期路径因此不是不可逆承诺。

停止证书来自全局不可达性，而非“刚才选的路已经满”。只要还有残量源汇路，就存在严格增加流值的可行改动；当所有这类路消失，残量可达集恰好暴露一个与当前流同值的割。

弧

容量均为 $1$。若先沿 $s\to a\to b\to t$ 增广，得到 $f(s,a)=f(a,b)=f(b,t)=1$。此时第二条残量路是

其中 $b\to a$ 是原弧 $a\to b$ 的反向记录。增广后 $f(a,b)$ 降为 $0$，同时 $f(s,b)=f(a,t)=1$，最终等价于两条单位路径 $s\to a\to t$ 与 $s\to b\to t$。若搜索只看原弧的正向余量，就会错误停在流值 $1$。

反平行原弧与残量反向记录方向可能相同，更新时必须通过配对索引找到各自原弧；只用端点定位会在撤销时改错记录。平行弧也应分别保存容量与残量，或在不需要逐弧输出时预先合并容量。

大整数容量说明终止不等于高效：容量用二进制写入时，$|f^{\ast }|$ 可相对输入位数呈指数级。Edmonds–Karp 固定选残量边数最少的路，计入初始化后给出 $O(|V|+|V||A{|}^2)$ 的组合界；Dinic 在每个最短距离层次中一次求阻塞流。二者的多项式性来自选路结构，不来自把容量声明为整数。

增广思想把二分图匹配中的交替路、单源单汇流与某些环流可行性算法放进同一残量语言。最小费用流还要比较增广费用并防止负费用圈，带下界环流要先恢复可行初始流；它们不能只沿任意残量路重复本页步骤。

Ford–Fulkerson 始终维护满足守恒的可行流，并按完整源汇路增加流值。Push–Relabel公理库Push–relabel 最大流算法Push-relabel algorithm · Preflow-push algorithm维护预流、超额和有效高度标签，以局部推送与重标号求最大流的算法。允许中间状态违反守恒而形成预流，只沿局部 admissible edge 推送超额；两者的状态空间、终止条件与复杂度势函数不同。

在源无正流入、汇无正流出的约定下，流分解定理公理库流分解定理Flow decomposition theorem将有限网络中的可行源汇流写成简单源汇路径流与有向环流的非负组合。把可行流写成非负的源汇路径流与环流之和。最大流页的更一般可行域还可能含汇到源的路径分量，须按其方向计入净值。分解解释路线语义，增广次数仍需独立的选路分析。