流分解定理

形式陈述 ​

设 $f$ 是有限有向网络中的可行 $s$–$t$ 流公理库最大流Maximum flow在容量与流守恒约束下最大化源到汇净流量的问题。。存在简单 $s$–$t$ 路 $P_i$、简单有向环 $C_j$ 与系数 ${\alpha }_i,{\beta }_j>0$，使

$$f=\sum _i{\alpha }_i{\chi }^{P_i}+\sum _j{\beta }_j{\chi }^{C_j},|f|=\sum _i{\alpha }_i.$$

${\chi }^P$ 表示沿路径或环的单位流。总组件数至多为原流正支撑中的边数，因此不超过 $|E|$；若 $f$ 为整数流，可令全部系数为正整数。

构造证明在正流支撑图中进行。流值为正时从 $s$ 沿正流边前进；内部流守恒保证不会在非汇顶点无路可走，有限性使轨迹最终到达 $t$ 或先形成环。流值已经为零但支撑仍非空时，从任一正流边出发，守恒会导出有向环。取所得简单路或环上的最小正流 $\gamma$，减去 $\gamma \chi$，至少一条正流边归零且不会产生新正支撑。重复至零流即终止；整数情形每次最小值仍为整数。朴素地每轮用图搜索找路或环，至多 $|E|$ 轮，时间为 $O(|E|(|V|+|E|))$。

直觉 ​

边流记录汇总通过量，分解则把它追踪成若干批货物的完整路线。内部有向环可以携带流，却既不从源带出新货物，也不向汇增加净值；所以流值只由源汇路径系数之和决定。

路径与环公理库路与圈Path and cycle in a graph由相邻顶点序列形成的路，以及首尾闭合的圈。是守恒约束的原子形态。沿正支撑抽取而不是在原图任意选路，保证每次相减后所有边流仍非负。

例子与边界 ​

若 $s\to a\to t$ 各有流 $3$，$s\to b\to t$ 各有流 $2$，另有 $a\to b\to a$ 环流 $1$，则可分成系数 $3$、$2$ 的两条源汇路径和系数 $1$ 的环。总流值为 $5$，环不改变源净流出。

同一流的分解通常不唯一：当正支撑中多条路径共享边时，先抽哪条会改变后续组件。定理保证存在稀疏分解，不提供唯一的“每单位流实际走过的路线”。

最大流也可能叠加正环流；最大性只约束源汇净值，不自动删除循环。无向网络若用一对反向弧表示，分解前需先固定有向流约定并消去同边双向抵消，否则“环”可能只是表示冗余。

推论与应用 ​

流分解把边变量模型与路径变量模型连接起来，用于多商品流、路径采样、运输解释和积分流证书。它也说明任何正值可行流都至少包含一条正流源汇路径。

组件数界来自每轮消去一条正边，而不是路径数量单独总小于 $|E|$ 后再额外无限加入环。引用时应写“路径与环的总组件数”或给更精细条件。

参考资料

• Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, Network Flows, Prentice Hall, 1993, §3.5.
• Alexander Schrijver, Combinatorial Optimization, Springer, 2003, Ch. 10.