形式陈述

流网络是有向图 $G=(V,E)$，带源点 $s$、汇点 $t$ 和容量函数 $c:E\to {\mathbb{R}}_{\ge 0}$。可把缺失边容量视为 $0$。流是函数 $f:V\times V\to \mathbb{R}$，满足反对称形式

$$f(u,v)=-f(v,u),$$

容量约束

$$f(u,v)\le c(u,v),$$

以及除 $s,t$ 外的流守恒

$$\sum _{v\in V}f(u,v)=0.$$

流值为

$$|f|=\sum _{v\in V}f(s,v).$$

最大流问题是在所有可行流中最大化 $|f|$。等价地也可只在边上定义非负流并分别写入流等于流出。

直觉

容量限制每条管道能通过多少量，中间顶点不生产也不吞噬流，目标是让源到汇的总输送量最大。反向流记号方便表达撤销先前选择。

例子与边界

残量容量

$$c_f(u,v)=c(u,v)-f(u,v)$$

表示还可沿方向 $(u,v)$ 增加多少净流；反向残量边允许减少已有流。仅沿原图中“看起来还能走”的边贪心可能卡在非最大流，增广算法必须使用完整残量网络。

推论与应用

最大流建模运输、分配、图割与匹配。若容量为整数，则存在整数最大流，Ford–Fulkerson 的整数增广保持整性；对任意实数容量，朴素路径选择可能不终止，算法复杂度需使用 Edmonds–Karp 等明确策略。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Chs. 24–25。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 7。