Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut.
Cut capacity = 30
2 9
Flow value 30
5
10
4
15
15
10
s A
5
3
8
6
10
t
15
4
6
15
10
4
30
7
Capacity = 30
15
Flows and Cuts
Weak duality. Let f be any flow. Then, for any s-t cut (A, B) we have v(f) cap(A, B). Pf.
Value of flow = 28 Cut capacity = 28
9 2 10 10 4 s 5 3 4 0 9 1 15 8 8 4 6 5 9
Flow value 28
15
0
10 9 10 10 10 t
A
15 14
4 0
6 14
15 0
4
30
7
17
Towards a Max Flow Algorithm
15 11
4 0
6 11
15 0
4
30
7
Value = 24
9
Maximum Flow Problem
Max flow problem. Find s-t flow of maximum value.
9 2 10 10 4 s 5 3 4 0 9 1 15 8 8 4 6 5 9
15
0
10 9 10 10 10 t
cap( A, B)
2 9
c(e)
e out ofA
5

s A
10
4
15
15
10
5
3
8
6
10
t
15
4
6
15
10
4
30
7
Capacity = 10 + 5 + 15 = 30
5
Cuts
Def. An s-t cut is a partition (A, B) of V with s A and t B. Def. The capacity of a cut (A, B) is:
Greedy algorithm. Start with f(e) = 0 for all edge e E. Find an s-t path P where each edge has f(e) < c(e). Augment flow along path P. Repeat until you get stuck.
f (e) f (e) v( f )
e out ofA
2 10
e in to A
6 9 0 15 8 5 6

s A
10 3 5
4 4
15
0
10 8
3
8 1
6
10 10 10
t
15 11
4 0
6 11
15 0
4
30
7
Value = 24
11
Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount leaving s.

e in tov
e out ofv
Def. The value of a flow f is: v( f )

2 4 10 0 s 5 3 4 4 0 9 5
f (e) .
e out of s
0
4 8 0
0
15
15
0
10 4
6
10 0 10
t
capacity flow
15 0

e in tov
e out ofv
Def. The value of a flow f is: v( f )

2 10 10 3 s 5 3 4 4 6 9 5
f (e) .
e out of s
0
8 8 1
6
15
15
0
10 8
6
10 10 10
t
capacity flow

1
0 20
0 10
s
30 0
t
10 0
2
20 0
Flow value = 0
18
Towards a Max Flow Algorithm
Greedy algorithm. Start with f(e) = 0 for all edge e E. Find an s-t path P where each edge has f(e) < c(e). Augment flow along path P. Repeat until you get stuck.
e out ofs
by flow conservation
f (e) f (e) v A e out ofv e in to v f (e) f (e).
e out ofA e in to A
14
Flows and Cuts
Capacity = 10 + 8 + 10 = 28
2 9 5
10
4
15
15
10
s
5
3
8
6
10
t
A
15
4
6
15
7
Flows
Def. An s-t flow is a function that satisfies: For each e E: 0 f (e) c(e) [capacity] For each v V – {s, t}: f (e) f (e) [conservation]
Design and Analysis of Algorithms
3. Maximum Flow
Mingyu XIAO
School of Computer Science and Engineering University of Electronic Science and Technology of China
capacity flow
15 14
4 0
6 14
15 0
4
30
7
Value = 28
10
Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount leaving s.
Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then
f ( e) f (e ) v( f ) .
e out ofA e in toA
Pf.
v( f )
f (e)
Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount leaving s.
A
4 8
v( f )
f (e ) f ( e)
e out ofA e in toA
s
B
t
f (e )
e out ofA
c( e )
e out ofA
7
6
▪
cap( A, B)
16
Certificate of Optimality
Corollary. Let f be any flow, and let (A, B) be any cut. If v(f) = cap(A, B), then f is a max flow and (A, B) is a min cut.








3
Minimum Cut Problem
Flow network. Abstraction for material flowing through the edges. G = (V, E) = directed graph, no parallel edges. Two distinguished nodes: s = source, t = sink. c(e) = capacity of edge e.

Nontrivial applications / reductions. Data mining. Network reliability. Open-pit mining. Distributed computing. Project selection. Egalitarian stable matching. Airline scheduling. Security of statistical data. Bipartite matching. Network intrusion detection. Baseball elimination. Multi-camera scene Image segmentation. reconstruction. Network connectivity. Many many more …