循环流

循环流（circulation，也称环流）是在有向网络每个顶点都满足流入等于流出的边流。它没有净供给的源点或净接收的汇点；流量可以沿有向环循环，也可以是多条循环的叠加。本文的边流非负，并可附加边容量上下界。

例如，沿三角环 $a\to b\to c\to a$ 每边送二单位，沿二边环 $c\to d\to c$ 每边送一单位。顶点 $c$ 的流入为 $2+1=3$，流出也为三；其余点同样守恒，因此二者叠加为一个循环流。

同一顶点可以属于多个循环，守恒检查的是全部入流与出流之和。

守恒与容量

设有向图 $G=(V,E)$，边的下界、上界满足 $0\le {\ell }_e\le u_e$。一个可行循环流满足 $${\ell }_e\le f_e\le u_e,\sum _{e\in {\delta }^{+}(v)}{f}_e-\sum _{e\in {\delta }^{-}(v)}{f}_e=0(v\in V).$$ 采用关联矩阵“起点负一、终点正一”的约定时，守恒也写为 $Bf=0$。若全部下界为零，零流总可行；只有加入正下界、费用目标或额外约束后，可行性与优化才可能成为非平凡问题。

“循环”不要求每条边都有正流，也不要求整个网络强连通。一个大图可以只有某个小环上有正流，其他边全为零；多个互不相连的分量中也可各自循环。

非负循环流分解成有向环

定理。 有限有向图中的任意非负循环流，都能写成若干个有向环的非负流量叠加。

证明。 若全流为零，不需任何环。否则取一条正流边，沿它走到终点。由于该点收到正流、又满足守恒，必有至少一条正流出边，可继续走。有限顶点保证最终出现重复顶点，从两次出现之间取出一个有向环 $C$。令 $\alpha =\underset{e\in C}{min}{f}_e>0$，从环上每条边都减去 $\alpha$。

各顶点在这个操作中流入和流出各减少同量，因此剩余流仍守恒；非负性由最小值选择保证；至少一条正流边归零。记录环流 $\alpha {\mathrm{𝟏}}_C$，然后对剩余正流重复。每轮至少消除一条正流边且不产生新的正流边，有限轮后全为零，原流便是所记录环流之和。

分解通常不唯一。即便边流固定，某个交会点后的流量可以按不同方式配成循环；可行流作为边向量是确定的，路径分组只是它的一种表示。上面的证明利用非负性来保证正流路线能继续，不适用于把带正负号的数值直接当作沿原方向的物理流量。

正下界转化为供需

要处理下界，令 $x_e=f_e-{\ell }_e$，则 $0\le x_e\le u_e-{\ell }_e$。将它代入守恒式，可得 $$\sum _{e\in {\delta }^{+}(v)}{x}_e-\sum _{e\in {\delta }^{-}(v)}{x}_e=\sum _{e\in {\delta }^{-}(v)}{\ell }_e-\sum _{e\in {\delta }^{+}(v)}{\ell }_e=:b_v.$$ 右端是预先放入下界流后，各点需要由剩余流补偿的净供给，且 $\sum _v{b}_v=0$。正的 $b_v$ 要求额外净流出，负值要求额外净流入。

增加超级源 $S$ 和超级汇 $T$：若 $b_v>0$，加边 $S\to v$，容量 $b_v$；若 $b_v<0$，加边 $v\to T$，容量 $-b_v$。在原边上使用剩余容量 $u_e-{\ell }_e$。原循环流可行，当且仅当这个辅助网络能从 $S$ 向 $T$ 送出总量 $\sum _{b_v>0}{b}_v$，即饱和全部超级源出边。

等价性的证明可逐点检查：超级边饱和时，辅助网络对原点的守恒恰好变成 $x$ 的净流出为 $b_v$；加回 $\ell$ 后净流出为零。反向由任意原可行流减去下界，按同一式补上超级边，即得到所需的辅助流。两端超级边的总容量相同，因为 $\sum b_v=0$。

下界算例与不可行变式

只取三角环 $a\to b\to c\to a$，每边上界三，边 $ab$ 下界二，其余下界零。先放入下界后，$a$ 流出多二，$b$ 流入多二，所以 $b_a=-2,b_b=2,b_c=0$。辅助网络加 $S\to b$ 和 $a\to T$，容量均二；沿 $S\to b\to c\to a\to T$ 送二，得到原流 $f_{ab}=f_{bc}=f_{ca}=2$，满足全部条件。

变式。 将边 $ca$ 的上界降为一。任意循环流在这个单环上三条边必须同流量，边 $ab$ 又要求至少二，而 $ca$ 至多一，矛盾。辅助网络也只能沿返回段送一单位，无法饱和二容量的超级源边。这把直接守恒矛盾与辅助最大流失败对应起来。

源汇流与循环流的转换

若已有从 $s$ 到 $t$、值为 $F$ 的源汇流，增加一条 $t\to s$ 并在其上送 $F$，就把源点、汇点的净流量也补平，成为循环流。反过来，删除这条回边，其流量就是源汇流值。若要求固定值，可给回边设置上下界都为 $F$；若只测试某个范围，则设置相应区间。回边容量必须确实覆盖目标流量，不能随意用一个未经论证的有限数代替无上界。

带费用的循环流以 $\sum _e{c}_e{f}_e$ 为目标。残量负环恰代表保持每点守恒而降低费用的一种调整，见最小费用流。无界容量的负费用环可能使最优费用趋向负无穷，流量守恒本身不会消除这种无界性。