什么是残余图

残余图的概念与作用

在网络流问题中，残余图是一种用来描述当前流量状态的辅助图。它是从原始流网络（即包含所有节点和有向边、每条边都有容量限制的图）衍生出来的，主要用于判断在已有流的基础上还能向哪些方向继续增大流量。

1. 为什么需要残余图

当我们已经在网络中分配了一部分流量后，某些边可能已经满载，无法再继续向前推进；而有些边虽然已经有流量，但仍然可以把这部分流量“撤回”或“重新分配”。残余图把这两种可能性都显式地表现出来，帮助算法（如 Ford‑Fulkerson）寻找可以进一步提升总流量的路径。

2. 残余图的构造方式

残余图的边分为两类：

• 正向残余边
  对于原始网络中的每一条有向边，如果该边上已经使用的流量小于它的容量，那么在残余图中会保留一条同向的残余边。它的“剩余容量”就是原始容量减去已经使用的流量，表示还能再向该方向继续输送多少流量。
• 反向残余边
  为了能够把已经发送的流量撤回或重新分配，残余图会在每条原始边上额外加入一条相反方向的边。它的容量等于原始边上已经发送的流量，意味着可以把这部分流量从下游节点送回上游节点，进而在别的路径上重新使用。

通过这两类边的组合，残余图完整地刻画了在当前流状态下所有可能的增量或调整方向。

3. 残余图在算法中的角色

在 Ford‑Fulkerson 及其实现（如 Edmonds‑Karp）中，算法的核心步骤是不断在残余图中寻找一条从源点到汇点的 增广路径——即所有边的剩余容量都大于零的路径。找到这样一条路径后，就可以沿着它把流量再向前推进，随后更新原始网络和残余图的容量信息。只要残余图中仍然存在增广路径，算法就继续循环；当残余图不再包含任何从源点到汇点的可行路径时，当前的流已经是最大流。

4. 关键特性

• 动态更新：每次增大流量后，残余图会相应地增减正向和反向边的容量，保持对当前流状态的准确反映。
• 支持回退：反向残余边的存在使得算法能够把已经分配的流量撤回，从而在不同路径之间重新平衡流量，避免局部饱和导致的死路。
• 决定最大流：当残余图中不存在从源点到汇点的路径时，依据最大流‑最小割定理，此时的流已经达到网络能够承载的最大值。

5. 小结

残余图是网络流算法的核心工具，它把原始网络的容量限制和当前流量状态融合在一起，以图的形式直观展示了哪些方向还能继续输送流量，哪些方向可以撤回已有流量。通过在残余图中不断寻找增广路径，算法能够逐步逼近并最终得到网络的最大流。