Max-flow

Definition / 定义

max-flow（最大流）：图论与网络优化中的概念，指在一个有容量限制的网络中，从源点（source）到汇点（sink）在不超过各边容量的前提下，能够输送的最大总流量。常与 min-cut（最小割） 定理一起出现。
（在工程语境中也可指“最大流量/最大流速”，但在算法领域通常指“最大流问题”。）

Pronunciation / 发音

/ˈmæks floʊ/

Examples / 例句

We used a max-flow algorithm to find the best way to route traffic.
我们用最大流算法来找出交通分流的最佳路线。

The max-flow value increases if we add capacity to the bottleneck edge, but it may still be limited by a different cut elsewhere in the network.
如果我们增加瓶颈边的容量，最大流值会提高，但它仍可能被网络中别处的另一条割所限制。

Etymology / 词源

max 是 maximum（最大值） 的常见缩写；flow 来自古英语 flōwan（“流动”）。合起来 max-flow 字面意思就是“最大流（量）”，在 20 世纪中期的网络流研究中成为标准术语。

Related Words / 相关词汇

• Maximum
• Flow
• Network
• Graph
• Capacity
• Min-cut
• Residual
• Augmenting Path
• Ford-Fulkerson
• Edmonds-Karp
• Dinic

Literary Works / 文学作品

• Maximal Flow Through a Network（Ford & Fulkerson，1956）：最大流经典论文，奠定了增广路方法的基础。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：常以 “Maximum flow” 章节系统介绍最大流与最小割。
• Network Flows: Theory, Algorithms, and Applications（Ahuja, Magnanti, Orlin）：网络流领域权威教材，涵盖最大流及其应用。