带下界与需求的可行环流

边下界先固定一份基础流。它满足每条边的最低运量，却未必满足各站点的供需：有的站点收到过多，有的仍缺货。超级源汇网络检验剩余容量能否补平这些差额，因而把边上的下界约束转成了节点上的剩余需求。

图中是 $b=0$ 的环流例，除 $a\to b:[2,5],b\to c:[1,4]$ 外还有 $c\to a:[0,2]$。剩余需求为 $(2,-1,-1)$，补流为 $(0,1,2)$，恢复后原三弧各流两单位。下文的运输例另取非零供需，超级边方向因此不同。

有源汇与费用边界 ​

把要求非负流值的有源 $s$、汇 $t$ 流问题转成环流，可加入回边 $t\to s$，让送达汇点的流返回源点。流量自由时，回边上界可取源出弧上界之和；要求恰好发送 $F\ge 0$ 时，把回边下界、上界都设为 $F$。若还要最小化费用，需在可行性之外优化费用，并把基础流的常数费用 $\sum _e{c}_e{l}_e$ 计回目标值。

饱和判据证明 ​

若超级源所有出边饱和，删除 $s^{\ast },t^{\ast }$ 后，剩余流在每个原节点恰补足 $r(v)$，加回下界流即满足节点需求和边界。反过来，任意原问题可行流减去下界后给出一份补偿流，可扩展为把所有超级源边饱和的流。这证明了饱和判据的充要性。

总需求不平衡时超级源出容量与入超级汇容量不同，直接无解。若归约写了无穷容量，实际使用前应证明一个适用的有限上界，并防止整数溢出。

三节点运输的数值变换 ​

设边 $a\to b$ 的容量区间为 $[2,5]$，边 $b\to c$ 为 $[1,4]$；节点需求为 $b(a)=-3,b(b)=0,b(c)=3$，即从 $a$ 向 $c$ 运送 3 单位。基础流造成的净流入依次为 $(-2,1,1)$，所以剩余需求为 $r=(-1,-1,2)$。两条原边的剩余容量均为 3，超级边则是容量 1 的 $s^{\ast }\to a$、容量 1 的 $s^{\ast }\to b$ 和容量 2 的 $c\to t^{\ast }$。

在原边上分别补送 1、2 单位，就能把超级源的 2 单位全部送到超级汇。加回下界后，两条铁路的最终流量均为 3，既落在各自容量区间内，也满足三个节点的供需。

构造时核对剩余容量 $u_e-l_e$ 非负，以及超级源总出容量等于超级汇总入容量。若最大流值小于这个共同总量，最大流最小割定理给出容量不足的割，作为无法补平全部需求的证书。

恢复原流时对每条原边写 $f_e=l_e+f_e^{\prime }$，去掉超级边。若容量和需求均为整数，最大流整数性还保证能得到整数可行环流。

从线性约束看，同一结论来自有向点弧关联矩阵的全幺模性理路全幺模矩阵与整数顶点Totally unimodular matrix · Total unimodularity · TU用所有方形子式的 0、±1 性质控制逆矩阵分母，证明整数右端的线性约束产生整数顶点。：加入整数上下界后仍保持整数多面体。这个解释也区分了“存在整数可行流”和“每个实数可行流都是整数”两种不同说法。

恢复原流后，给供给点 $b(v)<0$ 补一条流量为 $-b(v)$ 的超源入弧，给需求点 $b(v)>0$ 补一条流量为 $b(v)$ 的超汇出弧，便得到符合源汇流分解定理理路流分解定理Flow decomposition theorem将有限网络中的可行源汇流写成简单源汇路径流与有向环流的非负组合。条件的网络。分解后删去人工弧，就得到供给点到需求点的路径流及环流，便于追踪运输量。修改这些分量时仍要满足原边下界；纯环流也可能承担合同规定的最低运量。

这一归约把合同最低量、节点供需和普通容量统一为一次最大流可行性判定。