最大流

容量限制每条有向通道能承载多少，中间顶点只转运、不生产也不消耗，目标是提高源到汇的净输送量。流不是一条路线：它可以在顶点处分叉与汇合，多条路线也会共享同一容量约束。

残量网络描述当前方案附近仍允许的改动。正向记录是尚未使用的余量，反向记录是撤销早先选择的权利；后者使算法能从局部不佳的路由中退回，而不必清空整张流重新开始。

流分解定理公理库流分解定理Flow decomposition theorem将有限网络中的可行源汇流写成简单源汇路径流与有向环流的非负组合。为弧上的数值提供路线解释。在没有进入源点的弧、没有离开汇点的弧这一常见约定下，可行流可以拆成源到汇路径流与环流的非负组合。本页允许这些弧，因此对任意可行流作分解时还可能出现汇到源的路径流，它们对净流值贡献为负。例如仅在 $t\to s$ 上放一单位流就是可行流，值为 $-1$，不能解释成非负的源到汇路径流之和。求最大值时可以去掉这些反向路径流，不会降低目标。

这种路线解释不要求算法显式保存每个单位沿哪条路径移动；单商品流只区分总量，不追踪身份。残量反向边撤回的是某条弧的流量，而不是要求现实中真的把某个带身份的包裹送回去。

考虑容量

令 $f(s,a)=3,f(s,b)=2,f(a,t)=2,f(a,b)=1,f(b,t)=3$，中间点均守恒，流值为 $5$。源出弧总容量也是 $3+2=5$，因此任何流都不可能更大；这个同值流与割给出了可复算的最优证书。

一次必须撤销旧选择的增广 ​

再看所有容量均为 $1$ 的网络 $s\to a,s\to b,a\to b,a\to t,b\to t$。若先沿 $s\to a\to b\to t$ 送一单位，继续只看原图的未满正向弧便找不到源汇路，但这不是最大流。残量图中存在 $s\to b\to a\to t$，其中 $b\to a$ 是原弧 $a\to b$ 的反向记录。

沿此路增广一单位后，$f(a,b)$ 从 $1$ 减到 $0$，$f(s,b)$ 与 $f(a,t)$ 从 $0$ 增到 $1$，其他已有流保持。结果变成两条路线 $s\to a\to t$ 与 $s\to b\to t$，总流值为 $2$。每个内部点沿残量路一进一出，故守恒不变；步长不超过各条残量容量，故原弧上的上下界也不被破坏。

平行弧可以分别承载流；若只关心最大值与顶点守恒，把同方向平行弧合并为容量之和不会改变最优值，但会丢失逐弧输出。反平行弧不能与残量反向记录混同。自环对净流量和守恒两侧贡献相同，可以删除而不改变最大流值。

容量只是上界，不要求每条弧用满；负容量让约束区间为空，标准模型不允许。所谓“无穷容量”在有限实现中应由问题结构证明出的有限上界代替；例如当源的所有出弧容量均有限时，它们的容量和就是流值上界。随意使用机器最大整数可能在加法中溢出。带下界、费用、顶点容量或多商品的流都改变可行域，需先给出相应归约或新模型。

最大流最小割定理公理库最大流最小割定理Max-flow min-cut theorem以净跨割恒等式和残量可达集证明最大流等于最小割，并给出独立可检查的最优性证书。把无残量增广路转成与流同值的割证书。Ford–Fulkerson 方法公理库Ford–Fulkerson 方法Ford–Fulkerson method沿残量网络中的增广路反复增加流量直至不存在增广路。逐条选择增广路，任意实容量下的终止性取决于选路规则；Dinic 算法公理库Dinic 算法Dinic's algorithm分层残量网络上反复计算阻塞流的最大流算法。按残量距离分阶段求阻塞流，得到与流值无关的一般多项式界；Push–Relabel公理库Push–relabel 最大流算法Push-relabel algorithm · Preflow-push algorithm维护预流、超额和有效高度标签，以局部推送与重标号求最大流的算法。维护预流、超额与高度，按局部操作推进。算法复杂度必须注明 $|V|$、原弧记录数、容量类型与算术模型。

若所有容量为整数，存在每条弧流量也为整数的最大流。这是“存在整数最优解”，不是说任意使用浮点近似的实现会自动返回整数，也不把依赖最大流值的伪多项式迭代数变成输入位数的多项式。

带下界与需求的环流公理库带下界与需求的可行环流circulation with demands · flow with lower bounds把边流量下界和节点供需转成超级源汇最大流，并以饱和条件判定可行性。通过消去下界、计算顶点需求并加入超级源汇来检查可行性，不能直接把下界当残量。全局最小割公理库全局最小割问题Global minimum cut在无向非负加权图中寻找任意非平凡顶点划分的最小割容量。使用无向图且不固定 $s,t$，虽可通过多次点对最小割联系，却不是一次固定源汇最大流的同一问题。多商品流还让多种商品竞争共享容量，需要新的变量与约束。

若若干源、汇只关心合计流量，可加入超级源和超级汇，并用各端点允许的供给、接收上界作为连接容量；若这些上界本身不存在，则要先从原网络推导安全有限界。该归约仍是单商品流，不能保留“某个源的单位必须送到某个指定汇”这类配对身份。

单源同时向多个终点发送同一批符号时，中间节点可采用线性网络编码公理库线性网络编码Linear network coding让中间节点转发有限域线性组合，以接收矩阵的满秩性刻画无噪多播的恢复条件。。蝴蝶网络在中央瓶颈发送一个 XOR，让拥有不同辅助符号的两个终点都补齐缺口。此时验收对象是各终点传输矩阵的秩；把多个终点分别求出的流直接叠加，可能重复占用同一条边。