residualgraph

A residual graph, in the context of network flow theory, is a directed graph that represents how much additional flow can be pushed through a given flow in a network. It is derived from an original network with a designated set of capacities and a feasible flow. The residual graph depends on the current flow and is used to guide further augmentation of that flow.

Construction: Let G = (V, E) be a directed graph with capacity function c: E -> R+ and a feasible flow f: E -> R+ (with flow value |f|). For every original edge (u, v) ∈ E, define the residual capacity c_f(u, v) = c(u, v) - f(u, v). If c_f(u, v) > 0, include a residual edge (u, v) with capacity c_f(u, v). For every edge (u, v) with f(u, v) > 0, include the reverse edge (v, u) with residual capacity f(u, v). The resulting residual graph typically omits edges with zero residual capacity but may include reverse edges that allow undoing previous flow.

Purpose and use: The residual graph encodes all ways to increase or decrease the current flow. Augmenting path algorithms, such as Ford-Fulkerson and Edmonds-Karp, search for a path from the source to the sink in the residual graph and push as much flow as possible along that path. After augmentation, the residual graph is updated to reflect the new flow. A maximum flow is obtained when there is no s-t path with positive residual capacity.

Relation to related concepts: The terms residual graph and residual network are often used interchangeably in literature. The concept generalizes to various network types and remains a foundational tool for understanding and implementing maximum-flow algorithms.