THE UNIVERSITY OF
NEW SOUTH WALES
5. FLOW NETWORKS
Raveen de Silva, [email protected]
office: K17 202
Course Admin: Anahita Namvar, [email protected]
School of Computer Science and Engineering
UNSW Sydney
Term 2, 2022
Table of Contents
1. Flow Networks
2. Solving the Maximum Flow Problem
3. Applications of Network Flow
4. Puzzle
Flow Networks
Definition
A flow network G = (V ,E ) is a directed graph in which each edge
e = (u, v) ∈ E has a positive integer capacity c(u, v) > 0.
There are two distinguished vertices: a source s and a sink t; no
edge leaves the sink and no edge enters the source.
s
v1
v2
v3
v4
t
16
12
20
13
14
4
10 4
9
7
Flow Networks
Examples of flow networks (possibly with several sources and many
sinks):
transportation networks
gas pipelines
computer networks
and many more.
Flow Networks
Definition
A flow in G is a function f : E → [0,∞), f (u, v) ≥ 0, which
satisfies
1. Capacity constraint: for all edges e(u, v) ∈ E we require
f (u, v) ≤ c(u, v),
i.e. the flow through any edge does not exceed its capacity.
2. Flow conservation: for all vertices v ∈ V {s, t} we require∑
(u,v)∈E
f (u, v) =
∑
(v ,w)∈E
f (v ,w),
i.e. the flow into any vertex (other than the source and the
sink) equals the flow out of that vertex.
Flow Networks
Definition
The value of a flow is defined as
|f | =
∑
v :(s,v)∈E
f (s, v) =
∑
v :(v ,t)∈E
f (v , t),
i.e. the flow leaving the source, or equivalently, the flow arriving at
the sink.
Given a flow network, our goal is to find a flow of maximum value.
Maximum Flow
Integrality Theorem
If all capacities are integers (as we assumed earlier), then there is a
flow of maximum value such that f (u, v) is an integer for each
edge (u, v) ∈ E .
Note
This means that there is always at least one solution entirely in
integers. We will only consider integer solutions hereafter.
Maximum Flow
In the following example, f /c represents f units of flow sent
through an edge of capacity c .
s
v1
v2
v3
v4
t
11/16
12/12
15/20
8/13
11/14
4/4
0/10 1/4
4/9
7/7
The pictured flow has a value of 19 units, and it does not appear
possible to send another unit of flow. But we can do better!
Maximum Flow
Here is a flow of value 23 units in the same flow network.
s
v1
v2
v3
v4
t
11/16
12/12
19/20
12/13
11/14
4/4
0/10 1/4
0/9
7/7
Maximum Flow
This example demonstrates that the most basic greedy
algorithm – send flow one unit at a time along arbitrarily
chosen paths – does not always achieve the maximum flow.
What went wrong in the first attempt
We sent 19 units of flow to vertex v3, only to send four units
back to v2.
It would have been better to send those four units of flow to t
directly, but this may not have been obvious at the time this
decision was made.
We need a way to correct mistakes! We would like to send
flow from v2 back to v3 so as to “cancel out” the earlier
allocation.
Residual Flow Network
Definition
Given a flow in a flow network, the residual flow network is the
network made up of the leftover capacities.
Flow network Residual flow network
s
v1
v2
v3
v4
t
11/16
12/12
15/20
8/13
11/14
4/4
0/10 1/4
4/9
7/7 s
v1
v2
v3
v4
t
5
11
12
5
15
5
8
3
11
4
11 3
4
5
7
Residual Flow Network
Suppose the original flow network has an edge from v to w
with capacity c , and that f units of flow are being sent
through this edge.
The residual flow network has two edges:
1. an edge from v to w with capacity c f , and
2. an edge from w to v with capacity f .
These capacities represent the amount of additional flow in
each direction. Note that sending flow on the “virtual” edge
from w to v counteracts the already assigned flow from v to
w .
Edges of capacity zero (when f = 0 or f = c) need not be
included.
Residual Flow Network
Suppose the original flow network has an edge from v to w
with capacity c1 and flow f1 units, and an edge from w to v
with capacity c2 and flow f2 units.
What are the corresponding edges in the residual graph
How much flow can be sent from v to w (and vice versa)
The forward edge allows c1 f1 additional units of flow, and
we can also send up to f2 units to cancel the flow through the
reverse edge.
Thus we create edges from v to w with capacity c1 f1 + f2
and similarly from w to v with capacit
y c2 f2 + f1.
Augmenting Paths
Definition
An augmenting path is a path from s to t in the residual flow
network.
The residual flow network below corresponds to the earlier example
of a flow of value 19 units. An augmenting path is pictured in red.
s
v1
v2
v3
v4
t
5
11
12
5
15
5
8
3
11
4
11 3
5
4
7
Augmenting Paths
The capacity of an augmenting path is the capacity of its
“bottleneck” edge, i.e., the edge of smallest capacity.
We can now send that amount of flow along the augmenting
path, recalculating the flow and the residual capacities for
each edge used.
Suppose we have an augmenting path of capacity f , including
an edge from v to w . We should:
cancel up to f units of flow being sent from w to v ,
add the remainder of these f units to the flow being sent
from v to w ,
increase the residual capacity from w to v by f , and
reduce the residual capacity from v to w by f .
Augmenting Paths
Recall that the augmenting path was as follows.
s v2 v3 t
5
8
4
5
5
15
After sending four units of flow along this path, the new residual
flow network is pictured below.
s
v1
v2
v3
v4
t
5
11
12
1
19
1
12
3
11
4
11 3
9
0
7
Augmenting Paths
The flow used to be as follows.
s
v1
v2
v3
v4
t
11/16
12/12
15/20
8/13
11/14
4/4
0/10 1/4
4/9
7/7
Augmenting Paths
Pictured below is the new flow, after sending four units of flow
along the path s → v2 → v3 → t.
s
v1
v2
v3
v4
t
11/16
12/12
19/20
12/13
11/14
4/4
0/10 1/4
0/9
7/7
Note that the four units of flow previously sent from v3 to v2 have
been cancelled out.
Table of Contents
1. Flow Networks
2. Solving the Maximum Flow Problem
3. Applications of Network Flow
4. Puzzle
Ford-Fulkerson algorithm
Keep adding flow through new augmenting paths for as long
as it is possible.
When there are no more augmenting paths, you have achieved
the largest possible flow in the network.
Ford-Fulkerson algorithm: Example (1/5)
s
v1
v2
v3
v4
t
0/16
0/12
0/20
0/13
0/14
0/4
0/10 0/4
0/9
0/7
s
v1
v2
v3
v4
t
16
12
20
13
14
4
10 4
9
7
Ford-Fulkerson algorithm: Example (2/5)
s
v1
v2
v3
v4
t
4/16
4/12
0/20
0/13
4/14
4/4
0/10 0/4
4/9
0/7
s
v1
v2
v3
v4
t
12
4
8
4 20
13 10
4
4
10 4
5
4
7
Ford-Fulkerson algorithm: Example (3/5)
s
v1
v2
v3
v4
t
11/16
4/12
7/20
0/13
11/14
4/4
7/10 0/4
4/9
7/7
s
v1
v2
v3
v4
t
5
11
8
4 13
7
13 3
11
4
3 11
5
4
7
Ford-Fulkerson algorithm: Example (4/5)
s
v1
v2
v3
v4
t
11/16
12/12
15/20
8/13
11/14
4/4
0/10 1/4
4/9
7/7
s
v1
v2
v3
v4
t
5
11
12
5
15
5
8 3
11
4
11 3
5
4
7
Ford-Fulkerson algorithm: Example (5/5)
s
v1
v2
v3
v4
t
11/16
12/12
19/20
12/13
11/14
4/4
0/10 1/4
0/9
7/7
s
v1
v2
v3
v4
t
5
11
12
1
19
1
12 3
11
4
11 3
9
7
Ford-Fulkerson algorithm
Why does this procedure terminate
Why can’t we get stuck in a loop, which keeps adding
augmenting paths forever
If all the capacities are integers, then each augmenting path
increases the flow through the network by at least 1 unit.
However, the total flow is finite. In particular, it cannot be
larger than the sum of all capacities of all edges leaving the
source.
We conclude that the process must terminate eventually.
Ford-Fulkerson algorithm
Even if the procedure does terminate, why does it produce a
flow of the largest possible value
Maybe we have created bottlenecks by choosing bad
augmenting paths; maybe better choices of augmenting paths
could produce a larger total flow through the network
This is not at all obvious, and to show that this is not the
case we need a mathematical proof!
Cuts in a Flow Network
The proof is based on the notion of a minimal cut in a flow
network.
Definition
A cut in a flow network is any partition of the vertices of the
underlying graph into two subsets S and T such that:
1. S ∪ T = V
2. S ∩ T =
3. s ∈ S and t ∈ T .
Cuts in a Flow Network
Definition
The capacity c(S ,T ) of a cut (S ,T ) is the sum of capacities of all
edges leaving S and entering T , i.e.
c(S ,T ) =
∑
(u,v)∈E
{c(u, v) : u ∈ S , v ∈ T}.
Note that the capacities of edges going in the opposite direction,
i.e. from T to S , do not count.
Cuts in a Flow Network
Definition
Given a flow f , the flow f (S ,T ) through a cut (S ,T ) is the total
flow through edges from S to T minus the total flow through
edges from T to S , i.e.
f (S ,T ) =
∑
(u,v)∈E
{f (u, v) : u ∈ S , v ∈ T}