A Flow Network is a weighted digraph where the edges have a flow and capacity, and there is exactly one source vertex, and one sink vertex
- The sink vertex has exactly outdegree.
- The source vertex has exactly indegree
The capacity is a function denoted which assigns each edge in the flow network a non-negative real number.
A flow in a flow network is a function that assigns each arc in the flow network to a non-negative real number (called the flow of an arc) such that the following constraints hold
- Capacity Constraint - the flow of each arc is no greater than the capacity of each arc.
- Flow Conservation Constraint - for each vertex, the total flow that comes in the vertex is the same as the total net flow leaving the vertex.
The value of a flow between vertices and is calculated as

Augmenting Paths and Residual Networks

A pseudo-flow is a function on each network which satisfies.
- The capacity constraint.
- For arc ,
The residual capacity of an arc under the pseudo-flow is the difference between the capacity and the flow of the arc.
The residual network represents the amount of flow that can be transferred across the flow network.
- It is obtained by having each arc in the flow network have the residual capacities as their weight.
An augmenting path is a path in the residual network from the source and sink and where a flow is available from to satisfying the constraints of flow.
The bottleneck of a flow network is the minimum residual capacity of all edges in a given augmenting path.
The maximum flow in a flow network is the maximum value of a flow from source to sink.
- A network is in maximum flow if and only if there are no augmenting paths.
The minimum cut of a flow network is an edge cut that separates the source and skink in such a way that the capacity of the cut is minimized.
Computing the max flow can be formulated as a Linear Programming problem.

Key theorems

Max-Flow Min Cut Theorem - In any flow network, the maximum flow is equal to the capacity of the minimum cut.
- The capacity constraint restricts .
- Generating a residual network by finding an augmenting path of bottleneck and increase the flow up to a limit by increasing the flow from to by and decreasing the flow from to by .
- The new flow no longer contains the augmenting path . We either augment with or with the maximum capacity of the new flow.
- When the process terminates, we have the maximum flow, and at least the minimum capacity. Hence ,
The Max-Flow Min-Cut Theorem is an analogue to the Primal-Dual Scheme with the Max-Flow problem as the primal and the Min-Cut problem as the dual.