Transcript Slide 1

Max Flow Problem
• Given network N=(V,A), two nodes s,t of V, and capacities
on the arcs: uij is the capacity on arc (i,j).
• Find non-negative flow fij for each arc (i,j) such that for
each node, except s and t, the total incoming flow is equal
to the total outgoing flow (flow conservation), such that
• fij is at most the capacity uij on arc (i,j);
• The total amount of flow going out of s (which is equal to
the total amount of flow coming into t ) is maximized
1
3
2
4
3
2
1
3
1
s
t
1
2
4
2
4
4
the black numbers next to an arc is its capacity
1
3
2
4
3
2
1
3
1
s
t
1
2
4
2
4
4
Cts= -1
Set costs all other arcs at 0
The minimum cost flow circulation (Af=0)
maximises the s-t flow
1
3
2
4
3
2
1
3
1
s
t
1
2
4
2
4
4
the black numbers next to an arc is its capacity
Push flow over the path s-1-4-t
The bottlenecks on this path are the edges {1,4} and
{4,t}. So we can send flow 2 along this path
1
3
2
4
2 3
2 2
1
3
1
s
t
1
2 2
4
2
4
4
the black number next to an arc is its capacity
the green number next to an arc is the flow on it
We can push another extra flow of 1 on the path
s-1-3-t. The bottleneck is now {s,1} with remaining
capacity 1.
1
3
1 2
1 4
3 3
2 2
1
3
1
s
t
1
2 2
4
2
4
4
the black number next to an arc is its capacity
the green number next to an arc is the flow on it
Since {4,t} is on its capacity, the only path remaining through
which we can send extra flow is s-2-4-3-t. Here {4,3} is the
bottleneck and thus we can send extra flow of 1
1
3
1 2
2 4
3 3
2 2
1
3
1 1
s
t
1
2 2
1 4
2
1 4
4
the black number next to an arc is its capacity
the green number next to an arc is the flow on it
There are no s-t paths left on which we can send extra
flow. So is this the maximal flow?
the residual graph
1
3
1 1 2
2 2 4
3 3
22
1 1
3 3
1 1
s
t
1 1
2 2
1 3 4
2
1 3 4
4
blue arcs (i,j) are forward arcs (fij<uij)
green arcs (j,i) are backward arcs (fij>0)
the blue number is the residual capacity of a blue arc
the green number is the capacity of a green arc
the black number is the original capacity of the arc
the residual graph
1
3
1 1
2 2
3
2
1
3
1
s
t
1
2
1 3
2
1 3
4
red arcs form an s-t-path in the residual graph
and therefore a flow-augmenting path in the
original network
the residual graph
1
3
1 1
2 2
3
2
1
3
1
s
t
1
2
1 3
2
1 3
4
red arcs form an augmenting path
Augment the flow by the minimum capacity of a
red arc, i.e, 1
the residual graph
1
3
1 1
2 2
3
2
1
3
1
s
t
1
2
1 3
2
1 3
4
Augment the flow by the minimum capacity of a
red arc, i.e, 1:
- increase the flow by 1 on all arcs corresponding to
forward red arcs
- decrease the flow by 1 on all arcs corresponding to
backward red arcs
the residual graph
1
3
2
3 1
3
1
3
1 1
1
s
t
1
2
2 2
2
2 2
4
Augment the flow by the minimum capacity of a
red arc, i.e, 1:
- increase the flow by 1 on all arcs corresponding to
forward red arcs
- decrease the flow by 1 on all arcs corresponding to
backward red arcs
Construct the new residual graph
1
3
2
4
2
2
1
3
1
s
t
1
2
4
2
4
4
An s-t cut is defined by a set S of the nodes with
s in S and t not in S.
1
3
2
4
2
2
1
3
1
s
t
1
2
4
2
4
4
S={s,1,2}
An s-t cut is defined by a set S of the nodes with
s in S and t not in S.
1
3
2
4
2
2
1
3
1
s
t
1
2
4
2
4
4
S={s,1,2}
An s-t cut is defined by a set S of the nodes with
s in S and t not in S
Size of cut S is the sum of the capacities on the
arcs from S to N\S.
1
3
2
4
2
2
1
3
1
s
t
1
2
4
2
4
4
C(S)=u13+u14+u24= 2+2+4=8
An s-t cut is defined by a set S of the nodes with
s in S and t not in S
Size of cut S is the sum of the capacities on the
arcs from S to N\S.
S1
1
3
2
4
2
2
1
3
1
s
t
1
2
4
2
C(S1)=us1+u24= 2+4=6
4
4
S1
1
S2
2
3
4
2
2
1
3
1
s
t
1
2
4
2
4
4
C(S1)=us1+u24= 2+4=6
C(S2)=u13+u43+u4t= 2+1+2=5
1
S2
2
3
4
2
2
1
3
1
s
t
1
2
4
2
4
4
C(S2)=u13+u43+u4t= 2+1+2=5
Max Flow ≤ Min Cut
1
S2
2
3
4
2
2
1
3
1
s
t
1
2
4
2
4
4
C(S2)=u13+u43+u4t= 2+1+2=5
Max Flow ≤ Min Cut
fs1+fs2 ≤ Min Cut ≤ 5
the residual graph
1
S2
2
3 1
3
1
3
1 1
1
s
t
1
2
2 2
2
fs1+fs2=2+3=5
4
2 2
= C(S )=u +u +u = 2+1+2=5
2
13
43
Max Flow = Min Cut
4t
the residual graph
1
S2
2
3 1
3
1
3
1 1
1
s
t
1
2
2 2
2
fs1+fs2=2+3=5
4
2 2
= C(S )=u +u +u = 2+1+2=5
2
13
43
4t
Max Flow = Min Cut
Theorem: Max Flow = Min Cut
Proof sketch of Max Flow=Min Cut
S2
1
2
3 1
3
1
3
1 1
1
s
2
2 2
2
fs1+fs2=2+3=5
t
1
4
2 2
= C(S )=u +u +u = 2+1+2=5
2
13
43
4t
There is no s-t-path in the residual graph!!!
S2={s,1,2,4} the set of nodes reachable from S
Proof sketch of Max Flow=Min Cut
S2 3
1
22
43
22
30
21
10
11
s
22
4 3
2
fs1+fs2=2+3=5
t
10
4
42
= C(S )=u +u +u = 2+1+2=5
2
from S2={s,1,2,4} to {3,t}
f13 = u13 = 2
f43 = u43 = 1
f4t = u4t = 2
13
43
4t
Proof sketch of Max Flow=Min Cut
S2 3
1
22
43
22
30
21
10
11
s
22
4 3
2
fs1+fs2=2+3=5
t
10
4
42
= C(S )=u +u +u = 2+1+2=5
2
from S2={s,1,2,4} to {3,t}
f13 = u13 = 2
f43 = u43 = 1
f4t = u4t = 2
Full capacity of cut is used
13
43
4t
Proof sketch of Max Flow=Min Cut
S2 3
1
22
43
22
30
21
10
11
s
22
4 3
2
fs1+fs2=2+3=5
t
10
4
42
= C(S )=u +u +u = 2+1+2=5
2
13
43
4t
from S2={s,1,2,4} to {3,t} from {3,t} to {S2={s,1,2,4}
f32 = 0
f13 = u13 = 2
f34 = 0
f43 = u43 = 1
f4t = u4t = 2
Full capacity of cut is used
Proof sketch of Max Flow=Min Cut
S2 3
1
22
43
22
30
21
10
11
s
22
4 3
2
fs1+fs2=2+3=5
t
10
4
42
= C(S )=u +u +u = 2+1+2=5
2
13
43
4t
from S2={s,1,2,4} to {3,t} from {3,t} to {S2={s,1,2,4}
f32 = 0
f13 = u13 = 2
f34 = 0
f43 = u43 = 1
f4t = u4t = 2
Full capacity of cut is used
nothing flows back across the cut
Proof sketch of Max Flow=Min Cut
S2 3
1
22
43
22
30
21
10
11
s
22
4 3
2
fs1+fs2=2+3=5
t
10
4
42
= C(S )=u +u +u = 2+1+2=5
2
13
43
4t
from S2={s,1,2,4} to {3,t} from {3,t} to {S2={s,1,2,4}
f32 = 0
f13 = u13 = 2
f34 = 0
f43 = u43 = 1
f4t = u4t = 2
Capacity of the cut is equal to the flow from s to t