概念

网络流

最大流最小割定理断言网络吞吐瓶颈恰为最小割，最小费用流在流中引入成本优化，与线性规划对偶理论紧密相连。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

网络流图论

01定义

网络流研究带容量的有向图上的流量分配。最大流最小割定理断言：从源到汇的最大流量恰等于分隔源汇的最小割容量——瓶颈与吞吐精确对偶，是线性规划对偶在组合优化中的最美化身。

最大流最小割：流量 5 恰被容量 5 的割卡住

Ford-Fulkerson 沿增广路径迭代（Edmonds-Karp 用 BFS 保证多项式时间）；Dinic 分层加速；Push-Relabel 适合稠密网络。

最大流 = 最小割是线性规划强对偶的离散化身；「流守恒 + 容量上界」的对偶变量恰是割的 0-1 指示。

最小费用流（容量 + 单位成本，消圈算法）、多商品流、带下界的流通——供应链、指派、运输问题尽在其中。

\max\{|f|:f\ \text{为}\ s\text{-}t\ \text{流}\}=\min\{c(S):S\ \text{为}\ s\text{-}t\ \text{割}\}

Hitchcock 与 Koopmans 1940 年代研究运输问题；Ford 与 Fulkerson 1956 年证明最大流最小割定理，开创组合优化与线性规划的融合。

物流调度与运输规划、二分匹配与项目指派、图像分割（graph cuts）、棒球淘汰判定、网络带宽分配。

最大流：Ford-Fulkerson 增广路逐步增广：每条路径受最小剩余容量限制

step 增广次数0