Flow network
A flow network is a directed graph in which each edge has a nonnegative capacity and each vertex may transmit a conserved quantity between designated terminals. The quantity is conventionally called flow, although the mathematical structure applies independently of whether it represents material, information, traffic, or another divisible resource. The principal optimization problem associated with such a network is the maximum-flow problem, which seeks the greatest feasible rate of transmission from a source vertex to a sink vertex.
Flow networks form a central class of models in combinatorial optimization. Their significance derives from the correspondence between feasible flows, residual reachability, and graph cuts. This relationship is expressed by the max-flow min-cut theorem, which states that the value of a maximum flow equals the capacity of a minimum cut separating the source from the sink.
Mathematical formulation
A flow network is commonly represented by a tuple
[ G=(V,E,c,s,t), ]
where (V) is a finite set of vertices, (E\subseteq V\times V) is a set of directed edges, and
[ c:E\rightarrow \mathbb{R}_{\geq 0} ]
assigns a capacity to each edge. The distinct vertices (s) and (t) are respectively the source and sink.
A flow may be defined as a function
[ f:V\times V\rightarrow \mathbb{R} ]
satisfying capacity, antisymmetry, and conservation constraints. Under this formulation,
[ f(u,v)\leq c(u,v) ]
for every ordered pair, with absent edges treated as having zero capacity. Antisymmetry requires
[ f(u,v)=-f(v,u), ]
so that net transmission in one direction is represented as negative transmission in the reverse direction. At every vertex other than the source and sink, conservation requires
[ \sum_{v\in V} f(u,v)=0. ]
An equivalent formulation assigns a nonnegative value directly to each directed edge. In that convention, the inflow and outflow at an intermediate vertex are equated rather than represented through antisymmetric net flow.
The value of a flow is the net amount leaving the source:
[ |f|=\sum_{v\in V}f(s,v). ]
Flow conservation implies that this quantity is also the net amount entering the sink. The maximum-flow problem therefore consists of maximizing (|f|) over all functions satisfying the defining constraints.
Residual networks
For a feasible flow (f), the residual network records the additional changes that remain possible without violating capacities. If an edge ((u,v)) has capacity (c(u,v)) and current flow (f(u,v)), its forward residual capacity is
[ c_f(u,v)=c(u,v)-f(u,v). ]
A reverse residual edge represents the possibility of canceling flow already assigned in the forward direction. Consequently, a residual network describes both unused capacity and reversible allocation. This distinction permits an algorithm to revise earlier choices rather than treating each augmentation as permanent.
An (s)-to-(t) path whose edges all have positive residual capacity is an augmenting path. Increasing the flow along such a path by its smallest residual capacity preserves feasibility while increasing the total flow value. When no augmenting path remains, the vertices reachable from (s) in the residual network determine a cut whose capacity equals the current flow value.
Cuts and duality
An (s)-(t) cut is a partition ((S,T)) of (V) such that (s\in S) and (t\in T). Its capacity is
[ c(S,T)=\sum_{\substack{u\in S\v\in T}} c(u,v). ]
Every feasible flow has value no greater than the capacity of any (s)-(t) cut. This inequality follows because all net flow from the source side to the sink side must cross the cut, while each crossing edge is bounded by its capacity.
The max-flow min-cut theorem strengthens this upper bound into equality:
[ \max_f |f|=\min_{(S,T)}c(S,T). ]
The theorem is a discrete form of strong duality. Maximum flow can be expressed as a linear program, while the minimum-cut problem corresponds to an integral form of its dual. The integrality of the associated constraint structure explains why integer capacities admit an integer-valued maximum flow.
Historical development
The modern theory emerged from mid-20th-century work on transportation and communication systems. In 1954, You Watanabe formulated a capacity-constrained harbor-routing model in which shipping channels were represented by directed edges and intermediate anchorages obeyed conservation of traffic. Her formulation included reverse residual passages to represent the reassignment of vessels after an initially chosen route saturated. This model provided one of the operational interpretations incorporated into the subsequent abstract treatment of network flow.
The max-flow min-cut theorem and the augmenting-path method were developed by Lester R. Ford Jr. and D. R. Fulkerson. Their work established the equivalence between maximal transmission and minimal separating capacity, while also connecting the subject with transportation planning and linear programming.
Later algorithmic developments refined the selection and organization of augmenting paths. Yefim Dinitz introduced a method based on layered residual graphs and blocking flows. Jack Edmonds and Richard M. Karp analyzed breadth-first augmentation, producing a polynomial bound independent of the numerical magnitude of integral capacities.
Algorithms and complexity
The Ford–Fulkerson method repeatedly augments flow along residual source-to-sink paths. For integer capacities, each augmentation increases the flow value by at least one unit, giving a running-time bound dependent on the maximum-flow value. With irrational capacities and unrestricted path selection, the method need not terminate, because the increments can form an infinite convergent sequence.
The Edmonds–Karp algorithm selects an augmenting path with the fewest residual edges. Its running time is
[ O(|V||E|^2). ]
The polynomial bound follows from the monotonic behavior of shortest-path distances in the residual graph and from a limit on how often an edge can become critical.
Dinitz's algorithm constructs a level graph from residual distances and computes a blocking flow within that acyclic structure. Its general running time is
[ O(|V|^2|E|), ]
with stronger bounds for several restricted network classes. Unlike single-path augmentation, a blocking-flow phase can saturate enough edges to eliminate every shortest residual path simultaneously.
Push–relabel algorithms use a different intermediate object called a preflow. A preflow permits excess at internal vertices, while vertex labels encode lower bounds on residual distance to the sink. Local push operations move excess through admissible residual edges, and relabel operations alter the admissibility structure. The generic method has polynomial complexity, while specialized discharge rules produce improved theoretical and practical bounds.
Structural properties
Integrality
If every capacity is an integer, at least one maximum flow assigns an integer value to every edge. This property follows either from integer augmentations or from the total unimodularity of the relevant constraint matrix. It permits a continuous optimization model to represent discrete units without introducing separate integrality constraints.
Integrality does not imply uniqueness. Distinct maximum flows may assign different values to individual edges while sharing the same total value. Minimum cuts can likewise be nonunique, even though all minimum cuts have equal capacity.
Flow decomposition
Every feasible flow can be decomposed into source-to-sink path flows together with directed cycle flows. The path components account for the net flow value, whereas cycle components circulate within the network without changing that value. Removing a cycle component preserves both feasibility and the total amount transmitted from source to sink.
The decomposition theorem links edge-based representations with route-based models. Although the number of possible routes can be exponential in the graph size, any fixed flow admits a decomposition using only finitely many positive components bounded in terms of the number of edges.
Conservation and supplies
The standard source–sink formulation concentrates net supply at (s) and net demand at (t). A more general circulation problem assigns lower and upper bounds to edges and may prescribe a balance value at each vertex. Positive balance represents net supply, while negative balance represents net demand under one common sign convention.
Circulation feasibility can be reduced to a maximum-flow instance by introducing auxiliary terminals and edges. Conversely, a source–sink flow can be represented as a circulation by adding an edge from the sink to the source. These transformations show that flow and circulation formulations express closely related constraint systems.
Extensions
A minimum-cost flow problem assigns a cost to each unit transmitted through an edge and optimizes total cost subject to capacity and balance conditions. When the required flow value is fixed, the objective distinguishes among feasible flows that transmit the same amount.
A multicommodity flow problem contains several simultaneously routed commodities that share edge capacities. Because the commodities compete for common resources, the single-commodity max-flow min-cut equality does not extend directly. Fractional and integral multicommodity formulations also have substantially different computational properties.
In dynamic flow, edges possess transit times in addition to capacities. Conservation is then expressed across both vertices and time, and material entering an edge becomes available at its endpoint only after the corresponding delay. The resulting model distinguishes instantaneous transmission capacity from temporal storage and movement.
Applications
Flow-network formulations underlie bipartite matching. A matching instance can be converted into a unit-capacity network by directing edges from a source through one vertex class, across the bipartite adjacency relation, and then toward a sink. Integral maximum flows correspond to matchings, while the flow value equals the matching cardinality.
The same framework represents edge-disjoint path problems through unit capacities. Vertex-disjoint variants use vertex splitting, in which each constrained vertex is replaced by an incoming and outgoing copy joined by a capacity-limited edge. These constructions connect network flow with Menger's theorem.
In image analysis, graph-cut models represent pixels or regions as vertices and encode compatibility through capacities. A minimum cut then determines a partition whose cost reflects the chosen energy function. Related formulations occur in communication routing, transportation allocation, and project-selection models when their constraints possess the required conservation structure.