残差网络
残差网络记录了当前流还能在哪些边上增加或减少流量，是Ford-Fulkerson方法中寻找增广路径的基础结构。
定义
形式化定义
给定流网络 ，容量函数 ，以及一个流 ，残差网络 定义如下：
- 残差容量：对于每条边 ，残差容量 ，表示该边还能增加多少流量
- 反向残差容量：对于每条有流量的边 ，反向边 的残差容量 ，表示该边可以”撤销”多少流量
- 残差边集合：
增广操作：沿增广路径 增广流量 ，得到新流 ：
- 对于 上的每条正向边 ：
- 对于 上的每条反向边 ：
- 不在 上的边：
增广后流的值恰好增加 。
核心性质
| 性质 | 描述 |
|---|---|
| 正向边 | 表示还能增加流量，容量为 |
| 反向边 | 表示可以撤销已分配的流量，容量为 |
| 增广效果 | 沿增广路径增广后，流值恰好增加 |
| 合法性保持 | 增广后的 仍满足容量约束和流守恒 |
| 最大流判据 | 中不存在增广路径当且仅当 是最大流 |
关系网络
graph LR A["流网络 G + 流 f"] --> B["残差网络 Gf"] B --> C["增广路径 p"] C --> D["增广操作"] D --> E["新流 f'"] E --> B B -- "无增广路径" --> F["f 是最大流"]
章节扩展
第24章：最大流
残差网络在24.2节中定义，是Ford-Fulkerson方法的核心数据结构。
残差网络的关键在于反向边的存在——它允许算法”纠正”之前不够优的流量分配。直观地说，残差网络就像一张”还能怎么调整流量”的地图。正向边表示还能增加流量，反向边表示可以减少（撤销）之前分配的流量。
当残差网络中不再存在从源 到汇 的路径时，由引理24.2可知当前流即为最大流。此时，令 为 中从 可达的所有顶点集合，，则割 满足 ，这正是最大流最小割定理的构造性证明。
补充
补充说明
残差网络的概念不仅用于最大流算法，也是最小费用流（Minimum Cost Flow）等网络流变体问题的基础。在最小费用流中，残差网络上的反向边费用为正向边费用的相反数，这使得算法可以在增广过程中自然地”撤销”高代价的流量分配。