Flow conservation

Flow conservation requires the total flow entering each vertex to equal the total flow leaving it, except at designated sources and sinks.

Flow network: A directed graph whose edges have capacities and carry quantities of flow from sources to sinks. Its vertices and directed edges provide the setting for conservation constraints.
Directed graph: A graph whose edges have specified orientations from one vertex to another. Flow conservation is imposed at vertices of a directed network.
Ford–Fulkerson algorithm: A method for finding maximum flow by repeatedly augmenting paths in a residual network. Every augmentation preserves balance at intermediate vertices.
Flow capacity constraint: A restriction requiring flow on an edge to remain within its permitted lower and upper bounds. Capacity limits edge quantities, whereas conservation balances quantities at vertices.
Maximum flow: The greatest flow that can be sent through a capacitated network from a source to a sink. Conservation ensures flow cannot appear or disappear at intermediate vertices.
Vertex (graph theory): A point in a graph connected to other points by edges. The conservation rule is applied separately at each network vertex.
Maximum flow problem: The optimization problem of maximizing flow from a chosen source to a chosen sink subject to capacities and conservation. It uses vertex conservation as a defining feasibility condition.
Circulation (network flow): A feasible network flow with balanced inflow and outflow at every vertex and no designated source or sink. It satisfies conservation everywhere, including vertices that would otherwise serve as terminals.
Flow decomposition theorem: A theorem expressing any feasible flow as a sum of source-to-sink paths and cycles. Conservation lets a feasible flow be separated into paths and cycles.
Edge (graph theory): A connection between two vertices in a graph, directed or undirected. Each directed edge carries flow into one endpoint and out of another.

Linked from 11 pages