Residual Graph

定义 Definition

残量图（residual graph）：在网络流问题中，由当前流量状态导出的“可继续调整/增广”的图。它用残量容量表示每条边还能增加多少流（正向边），以及在需要回退时能减少多少流（反向边）。残量图是寻找增广路（augmenting path）的核心工具。

发音 Pronunciation

IPA: /rɪˈzɪdʒuəl ɡræf/

例句 Examples

The residual graph shows where more flow can be sent.
残量图显示了还能把更多流量发送到哪些地方。

After pushing flow along an augmenting path, we rebuild the residual graph to reflect updated forward and backward capacities.
沿着一条增广路推送流量后，我们会重建残量图，以反映更新后的正向与反向残量容量。

词源 Etymology

residual 来自拉丁语 residuum（“剩余物、残余”），表示“剩下的、可用的余量”；graph 源自希腊语词根 graphein（“书写、描绘”），在数学与计算机科学中引申为“图（由点和边组成的结构）”。合起来强调：这是描述“剩余可调整容量”的那张图。

相关词 Related Words

• Residual
• Flow Network
• Residual Capacity
• Augmenting Path
• Max Flow
• Ford–Fulkerson
• Edmonds–Karp
• Capacity

文学与名著 Literary Works

• Introduction to Algorithms（CLRS，《算法导论》）：最大流章节系统讲解残量网络/残量图与增广路思想。
• Network Flows: Theory, Algorithms, and Applications（Ahuja, Magnanti, Orlin，《网络流：理论、算法与应用》）：以残量图为核心工具之一讨论多种网络流算法。
• Ford & Fulkerson 的经典最大流相关论文与专著（如 Flows in Networks）：残量图概念与增广方法的源头性表述之一。