5Network problems
IB Optimisation
5.4 The maximum flow problem
Suppose we have a network (
V, E
) with a single source 1 and a single sink
n
.
There is no costs in transportation, but each edge has a capacity. We want to
transport as much stuff from 1 to n as possible.
We can turn this into a minimum-cost flow problem. We add an edge from
n
to 1 with
−
1 cost and infinite capacity. Then the minimal cost flow will
maximize the flow from
n
to 1 as possible. So the same amount of stuff will
have to flow from 1 to n through the network.
We can write this is problem as
maximize δ subject to
X
j:(i,j)∈E
x
ij
−
X
j(j,i)∈E
x
ji
=
δ i = 1
−δ i = n
0 otherwise
for each i
0 ≤ x
ij
≤ C
ij
for each (i, j) ∈ E.
Here δ is the total flow from 1 to n.
While we can apply our results from the minimum-cost flow problem, we
don’t have to do so. There are easier ways to solve the problem, using the
max-flow min-cut theorem.
First we need to define a cut.
Definition
(Cut)
.
Suppose
G
= (
V, E
) with capacities
C
ij
for (
i, j
)
∈ E
. A cut
of G is a partition of V into two sets.
For S ⊆ V , the capacity of the cut (S, V \ S) is
C(S) =
X
(i,j)∈(S×(V \S))∩E
C
ij
,
All this clumsy notation says is that we add up the capacities of all edges from
S to V \ S.
Assume
x
is a feasible flow vector that sends
δ
units from 1 to
n
. For
X, Y ⊆ V , we define
f
x
(X, Y ) =
X
(i,j)∈(X×Y )∩E
x
ij
,
i.e. the overall amount of flow from X to Y .
For any solution
x
ij
and cut
S ⊆ V
with 1
∈ S, n ∈ V \ S
, the total flow
from 1 to n can be written as
δ =
X
i∈S
X
j:(i,j)∈E
x
ij
−
X
j:(j,i)∈E
x
ji
.
This is true since by flow conservation, for any
i 6
= 1,
P
j:(i,j)∈E
x
ij
−
P
j:(j,i)∈E
x
ji
= 0,
and for i = 1, it is δ. So the sum is δ. Hence
δ = f
x
(S, V ) − f
x
(V, S)
= f
x
(S, S) + f
x
(S, V \ S) − f
x
(V \ S, S) − f
x
(S, S)
= f
x
(S, V \ S) − f
x
(V \ S, S)
≤ f
x
(S, V \ S)
≤ C(S)
This says that the flow through the cut is less than the capacity of the cut, which
is obviously true. The less obvious result is that this bound is tight, i.e. there is
always a cut S such that δ = C(S).
Theorem (Max-flow min-cut theorem). Let δ be an optimal solution. Then
δ = min{C(S) : S ⊆ V, 1 ∈ S, n ∈ V \ S}
Proof.
Consider any feasible flow vector
x
. Call a path
v
0
, · · · , v
k
an augmenting
path if the flow along the path can be increased. Formally, it is a path that
satisfies
x
v
i−1
v
i
< C
v
i−1
v
i
or x
v
i
v
i−1
> 0
for
i
= 1
, · · · , k
. The first condition says that we have a forward edge where
we have not hit the capacity, while the second condition says that we have a
backwards edge with positive flow. If these conditions are satisfied, we can
increase the flow of each edge (or decrease the backwards flow for backwards
edge), and the total flow increases.
Now assume that x is optimal and let
S = {1} ∪ {i ∈ V : there exists an augmenting path from 1 to i}.
Since there is an augmenting path from 1 to
S
, we can increase flow from 1 to
any vertex in S. So n 6∈ S by optimality. So n ∈ V \ S.
We have previously shown that
δ = f
x
(S, V \ S) − f
x
(V \ S, S).
We now claim that
f
x
(
V \ S, S
) = 0. If it is not 0, it means that there is a node
v ∈ V \ S
such that there is flow from
v
to a vertex
u ∈ S
. Then we can add
that edge to the augmenting path to u to obtain an augmenting path to v.
Also, we must have
f
x
(
S, V \ S
) =
C
(
S
). Or else, we can still send more
things to the other side so there is an augmenting path. So we have
δ = C(S).
The max-flow min-cut theorem does not tell us how to find an optimal path.
Instead, it provides a quick way to confirm that our path is optimal.
It turns out that it isn’t difficult to find an optimal solution. We simply keep
adding flow along augmenting paths until we cannot do so. This is known as
the Ford-Fulkerson algorithm.
(i) Start from a feasible flow x, e.g. x = 0.
(ii) If there is no augmenting path for x from 1 to n, then x is optimal.
(iii)
Find an augmenting path for
x
from 1 to
n
, and send a maximum amount
of flow along it.
(iv) GOTO (ii).
Example. Consider the diagram
- -
1 n
5
1
1
5
2
5
4
We can keep adding flow until we reach
- -
1 n
5
1
1
5
2
5
4
4
1
1
2
2
5
3
(red is flow, black is capacity). We know this is an optimum, since our total flow
is 6, and we can draw a cut with capacity 6:
- -
1 n
5
1
1
5
2
5
4