The Central Idea
A network-flow problem asks how much can be sent from a source to a sink through a directed graph without exceeding edge capacities.
The central optimization question is
\[ \boxed{\text{What is the greatest feasible flow from source to sink?}} \]Flow Networks Are Directed
A standard flow network is a directed graph.
An edge
\[ u\to v \]permits flow from \(u\) toward \(v\).
The reverse direction requires a separate directed edge or residual capacity created during an algorithmic calculation.
Source and Sink
A flow network has two distinguished vertices:
- the source \(s\), where flow originates;
- the sink \(t\), where flow is collected.
The goal is to move as much flow as possible from
\[ s \]to
\[ t. \]Capacity
Each directed edge \(u\to v\) has a nonnegative capacity
\[ c(u,v)\ge0. \]The capacity is the maximum permitted amount of flow on that edge.
For example,
\[ c(u,v)=8 \]means that at most \(8\) units may travel from \(u\) to \(v\).
Flow on an Edge
Let
\[ f(u,v) \]denote the actual amount of flow assigned to edge \(u\to v\).
Capacity feasibility requires
\[ \boxed{0\le f(u,v)\le c(u,v)}. \]A First Flow Network
Consider a network with source \(s\), sink \(t\), and intermediate vertices \(a\) and \(b\).
Suppose the capacities are
\[ c(s,a)=7,\qquad c(s,b)=5,\qquad c(a,b)=3,\qquad c(a,t)=4,\qquad c(b,t)=6. \]The Network as a Picture
Capacity Constraint
If the edge
\[ s\to a \]has capacity \(7\), then a proposed flow must satisfy
\[ 0\le f(s,a)\le7. \]A proposed value such as
\[ f(s,a)=9 \]is impossible because it exceeds capacity.
Flow Conservation
At every intermediate vertex, the total incoming flow must equal the total outgoing flow.
For a vertex \(v\ne s,t\),
\[ \boxed{ \sum_{u}f(u,v) = \sum_{w}f(v,w) }. \]Why Conservation Matters
An intermediate vertex does not create or destroy the modeled quantity.
If \(5\) units enter a junction, then \(5\) units must leave that junction, unless the model explicitly includes storage or loss.
Example: Conservation at a Vertex
Suppose \(5\) units enter vertex \(a\) from the source.
If
\[ f(a,t)=3 \]and
\[ f(a,b)=2, \]then
\[ 3+2=5. \]Conservation holds.
Flow Value
The value of a flow is the total net flow leaving the source.
Under the usual source convention,
\[ \boxed{ |f|=\sum_v f(s,v) }. \]The same amount must eventually arrive at the sink.
Example: Flow Value
If
\[ f(s,a)=4 \]and
\[ f(s,b)=5, \]then the total flow value is
\[ \boxed{|f|=4+5=9}. \]Feasible Flow
A feasible flow satisfies both major rules:
- capacity constraints on every edge;
- flow conservation at every intermediate vertex.
A proposed assignment that violates either rule is not a valid flow.
Maximum Flow
A maximum flow is a feasible flow whose value is as large as possible.
If \(\mathcal{F}\) is the set of all feasible flows, then
\[ \boxed{ |f_{\max}|=\max_{f\in\mathcal{F}}|f| }. \]Incoming Capacity Limits the Sink
The total capacity of edges entering the sink gives an immediate upper bound on maximum flow.
In the running network,
\[ c(a,t)+c(b,t)=4+6=10. \]Therefore,
\[ |f_{\max}|\le10. \]Outgoing Capacity Limits the Source
The total capacity leaving the source is also an upper bound.
In the running network,
\[ c(s,a)+c(s,b)=7+5=12. \]Hence
\[ |f_{\max}|\le12. \]The tighter of the two simple bounds is \(10\).
Bottlenecks
A bottleneck is a capacity restriction that limits how much flow can pass through part of the network.
A network may have large capacity near the source but still have a small maximum flow because of a narrow downstream cut.
Residual Capacity
If edge \(u\to v\) has capacity \(c(u,v)\) and current flow \(f(u,v)\), then the remaining forward capacity is
\[ \boxed{ c_f(u,v)=c(u,v)-f(u,v) }. \]This is called the residual capacity.
Example: Residual Capacity
Suppose
\[ c(u,v)=9 \]and
\[ f(u,v)=6. \]Then the unused forward capacity is
\[ \boxed{9-6=3}. \]Residual Networks
A residual network records how flow can still be adjusted.
It includes:
- forward residual edges for unused capacity;
- reverse residual edges that allow previously assigned flow to be reduced or rerouted.
Why Reverse Residual Edges Matter
An early flow choice may later prove inefficient.
Reverse residual capacity allows an algorithm to undo part of that choice and redirect flow through a better route.
This flexibility is essential to reliable maximum-flow algorithms.
Augmenting Path
An augmenting path is a path from source \(s\) to sink \(t\) in the residual network along edges with positive residual capacity.
Additional flow can be sent along such a path.
Bottleneck Capacity of an Augmenting Path
The amount by which a flow can be increased along an augmenting path is limited by the smallest residual capacity on that path.
If the residual capacities are
\[ 5,\qquad3,\qquad7, \]then the augmenting amount is
\[ \boxed{3}. \]Augmenting a Flow
Once an augmenting path is found:
- find its smallest residual capacity;
- increase forward-edge flows by that amount;
- decrease flows when a reverse residual edge is used;
- update the residual network.
Ford-Fulkerson Principle
The Ford-Fulkerson method repeatedly finds augmenting paths and increases the flow along them.
When no augmenting path remains, the current flow is maximum under the standard finite-capacity setting.
Edmonds-Karp Refinement
The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson idea.
It chooses augmenting paths with the fewest residual edges, typically using breadth-first search.
This gives a predictable polynomial-time procedure.
What Is a Cut?
An \(s\)-\(t\) cut divides the vertices into two sets
\[ S \]and
\[ T, \]with
\[ s\in S,\qquad t\in T. \]The cut separates the source side from the sink side.
Capacity of a Cut
The capacity of an \(s\)-\(t\) cut is the sum of capacities of directed edges going from \(S\) to \(T\).
\[ \boxed{ c(S,T)= \sum_{\substack{u\in S\\v\in T}}c(u,v) }. \]Why Cuts Bound Flow
Every unit of flow traveling from source to sink must cross any source-sink cut.
Therefore the value of any feasible flow satisfies
\[ \boxed{|f|\le c(S,T)} \]for every \(s\)-\(t\) cut.
Minimum Cut
A minimum cut is an \(s\)-\(t\) cut with the smallest possible capacity.
Its capacity gives the strongest cut-based upper bound on the maximum flow.
Max-Flow Min-Cut Theorem
One of the central theorems of network optimization states:
\[ \boxed{ \text{maximum flow value} = \text{minimum cut capacity} }. \]Thus an optimal flow and an optimal bottleneck cut have the same numerical value.
Why the Theorem Is Powerful
A feasible flow provides a lower bound on the optimum.
A cut provides an upper bound.
If a flow has value equal to the capacity of some cut, then both must be optimal.
Certifying Optimality
Suppose we construct a feasible flow with value
\[ 14 \]and also find a cut of capacity
\[ 14. \]Since no flow can exceed that cut,
\[ \boxed{|f_{\max}|=14}. \]Integer Capacities
If every capacity is an integer, then there exists a maximum flow in which every edge flow is also an integer.
This integrality property makes flow models especially useful in discrete routing and assignment applications.
Network Flow as Transportation
Vertices may represent junctions, warehouses, or distribution points.
Edge capacities may represent:
- vehicles per hour;
- tons per day;
- units shipped per period;
- available lane or route capacity.
Network Flow as Communication
In a communication network, capacities may represent data-transfer limits.
A maximum-flow calculation estimates the greatest total throughput that can be routed from a source node to a destination node under those capacity constraints.
Network Flow as Assignment
Many assignment and matching problems can be transformed into flow networks.
Vertices represent groups or choices, and unit capacities enforce limits on how many assignments may pass through each part of the construction.
The next lesson on bipartite matching develops this connection directly.
Multiple Sources or Sinks
A model with several sources can often be converted to a standard single-source network by adding a super-source.
Likewise, several sinks can be combined by adding a super-sink.
Capacitated versus Uncapacitated Edges
In a standard flow network, every usable edge has a stated finite capacity.
If a connection is effectively unlimited relative to the problem, it may be modeled using a sufficiently large capacity.
Common Error: Exceeding Capacity
A flow assignment is invalid if
\[ f(u,v)>c(u,v). \]Capacity is a hard upper bound.
Common Error: Violating Conservation
Suppose \(7\) units enter an intermediate vertex but only \(5\) units leave.
Unless storage or loss is explicitly part of the model, the assignment violates flow conservation.
Common Error: Adding Capacities along a Path
The capacity of one path is not the sum of its edge capacities.
A path can carry at most its bottleneck capacity:
\[ \boxed{ \min\{c(e):e\text{ lies on the path}\} }. \]Common Error: Ignoring Direction
Capacity on
\[ u\to v \]does not automatically provide capacity from
\[ v\to u. \]Direction is part of the network structure.
Common Error: Treating a Large Source Capacity as the Answer
Large capacity leaving the source does not guarantee equally large flow to the sink.
Downstream bottlenecks may impose a much smaller maximum.
Common Error: Ignoring Reverse Residual Capacity
Residual networks are not merely copies of the unused forward capacity.
Reverse residual edges are what allow an algorithm to undo and reroute earlier flow decisions.
A Reliable Procedure for Checking a Flow
- Check every edge capacity.
- Confirm \(0\le f(u,v)\le c(u,v)\).
- At each intermediate vertex, total incoming flow must equal total outgoing flow.
- Compute the total flow leaving the source.
- Verify that the same total reaches the sink.
A Reliable Procedure for Maximum-Flow Problems
- Identify the source \(s\), sink \(t\), and all capacities.
- Begin with a feasible flow, often zero flow.
- Construct or update the residual network.
- Find an augmenting path from \(s\) to \(t\).
- Find the smallest residual capacity on that path.
- Augment the flow by that amount.
- Repeat until no augmenting path remains.
- Use a minimum cut or residual structure to verify optimality.
Example: Full Feasibility Check
Suppose a network has
\[ c(s,a)=6,\qquad c(s,b)=4,\qquad c(a,t)=5,\qquad c(b,t)=4,\qquad c(a,b)=2. \]Consider the flow
\[ f(s,a)=5,\qquad f(s,b)=4, \] \[ f(a,t)=5,\qquad f(b,t)=4, \]with
\[ f(a,b)=0. \]All capacities are respected.
Vertex \(a\) receives and sends \(5\), while \(b\) receives and sends \(4\).
Therefore the flow is feasible and has value
\[ \boxed{|f|=9}. \]Example: Bottleneck Path
Suppose an augmenting path has residual capacities
\[ 8,\qquad5,\qquad6,\qquad2. \]The path can be augmented by at most
\[ \boxed{2} \]units because the smallest residual capacity controls the entire path.
Practice 1: Capacity Constraint
An edge has capacity \(9\).
Is a flow of \(7\) units on that edge feasible with respect to capacity?
Practice 2: Capacity Violation
An edge has capacity \(6\), but a proposed flow assigns \(8\) units.
Is the assignment valid?
Practice 3: Flow Conservation
An intermediate vertex receives \(3\) units from one edge and \(4\) from another.
How much total flow must leave the vertex?
Practice 4: Flow Value
A source sends \(5\) units along one outgoing edge and \(7\) along another.
Find the flow value.
Practice 5: Residual Capacity
An edge has capacity \(12\) and current flow \(8\).
Find its forward residual capacity.
Practice 6: Augmenting Bottleneck
An augmenting path has residual capacities
\[ 4,\qquad9,\qquad3,\qquad7. \]By how much may the flow be increased along the path?
Practice 7: Cut Bound
An \(s\)-\(t\) cut has capacity \(15\).
Can any feasible flow have value \(18\)?
Practice 8: Optimality Certificate
You find a feasible flow of value \(11\) and an \(s\)-\(t\) cut of capacity \(11\).
What can you conclude?
Practice 9: Path Capacity
A path contains edges with capacities
\[ 10,\qquad6,\qquad9. \]What is the maximum amount that can be sent along that path alone?
Practice 10: Identify the Error
A student says, “This source has \(20\) units of outgoing capacity, so the maximum flow must be \(20\).”
Explain the error.
Practice Answers
Practice 1
Since
\[ 0\le7\le9, \]the assignment respects capacity.
\[ \boxed{\text{Yes}}. \]Practice 2
Since
\[ 8>6, \]the proposed flow exceeds capacity.
\[ \boxed{\text{No}}. \]Practice 3
The total incoming flow is
\[ 3+4=7. \]Conservation requires
\[ \boxed{7} \]units to leave.
Practice 4
The source sends
\[ 5+7=12. \] \[ \boxed{|f|=12}. \]Practice 5
Residual capacity is
\[ 12-8=4. \] \[ \boxed{4}. \]Practice 6
The smallest residual capacity is
\[ \min(4,9,3,7)=3. \] \[ \boxed{3}. \]Practice 7
Any feasible flow is bounded above by the capacity of every \(s\)-\(t\) cut.
Therefore,
\[ \boxed{\text{No flow can exceed }15}. \]Practice 8
The feasible flow gives a lower bound of \(11\), and the cut gives an upper bound of \(11\).
Therefore,
\[ \boxed{|f_{\max}|=11}. \]Practice 9
The path is limited by its smallest capacity:
\[ \min(10,6,9)=6. \] \[ \boxed{6}. \]Practice 10
Outgoing source capacity is only an upper bound.
Downstream edges or cuts may have smaller total capacity and create a bottleneck.
Therefore the maximum flow may be less than \(20\).
What to Remember
- A flow network is a directed graph with a source, sink, and edge capacities.
- Every edge flow must satisfy \(0\le f(u,v)\le c(u,v)\).
- Intermediate vertices obey flow conservation.
- The flow value is the total net flow sent from source to sink.
- A maximum flow is a feasible flow with greatest possible value.
- Residual capacity records how much additional flow can still be sent or rerouted.
- An augmenting path is an \(s\)-\(t\) path in the residual network.
- The bottleneck residual capacity determines the augmentation amount.
- Every \(s\)-\(t\) cut gives an upper bound on feasible flow.
- The max-flow min-cut theorem equates maximum flow value with minimum cut capacity.
Where We Go Next
Network flows model how much can move through a capacitated network. A closely related family of problems asks how members of one group can be paired with compatible members of another group.
The next lesson, Bipartite Graphs and Matching, develops two-part graph structures, matchings, perfect matchings, augmenting paths, and their connection to flow networks.