Residual graph

A residual graph represents the capacity and cost of possible changes to a flow in a network. It includes forward edges for unused capacity and reverse edges for flow that can be canceled.

Flow network: A directed graph whose edges have capacities and whose vertices route a conserved quantity from a source to a sink. It supplies the capacities and current flow from which residual edges are derived.
Ford–Fulkerson algorithm: A method for finding maximum flow by repeatedly augmenting flow along source-to-sink paths. Each augmentation is chosen in the current residual graph.
Network flow: The study of assigning quantities to directed edges subject to capacity and conservation constraints. Residual graphs represent possible changes to an existing network flow.
Original graph: The directed network of edges and capacities specified before any flow adjustments are represented. Unlike the residual graph, it does not directly show cancellation options.
Residual capacity: The amount of additional flow that can pass along an edge, or be canceled along its reverse edge. It determines how much each residual edge can carry.
Edmonds–Karp algorithm: A maximum-flow algorithm that uses breadth-first search to select shortest augmenting paths by edge count. Its repeated searches are performed on residual graphs.
Flow capacity: An upper bound on the quantity that may pass through an edge in a flow network. Unused capacity becomes forward residual capacity.
Flow decomposition: A representation of a feasible flow as a combination of source-to-sink paths and cycles. It describes existing flow rather than the changes still available.
Augmenting path: A source-to-sink path in a residual graph whose edges all have positive residual capacity. Sending flow along this path changes the original flow by its bottleneck capacity.
Dinic's algorithm: A maximum-flow algorithm that repeatedly builds level graphs and sends blocking flows. Its level graphs are formed from edges available in the residual graph.

Linked from 10 pages