Optimization recurrence Notes | EduRev

: Optimization recurrence Notes | EduRev

 Page 1


1
CSE 421
Algorithms g
Richard Anderson
Lecture 22
Network Flow
Review
• Network flow definitions
• Flow examples
• Augmenting Paths
• Residual Graph
• Ford Fulkerson Algorithm
•Cuts
• Maxflow-MinCut Theorem
Network Flow Definitions
• Flowgraph:  Directed graph with distinguished 
vertices s (source) and t (sink)
• Capacities on the edges,  c(e) >= 0
• Problem, assign flows f(e) to the edges such Problem,  assign flows f(e) to the edges such 
that:
– 0 <= f(e) <= c(e)
– Flow is conserved at vertices other than s and t
• Flow conservation: flow going into a vertex equals the flow 
going out
– The flow leaving the source is a large as possible
Find a maximum flow
a d g
5/5
20/20 20/20
20/20 20/20
0/5
0/5
0/5
0/5
s b
c f
e h
i
t
15/25
25/30
20/20
5/5
20/20
0/5
20/20
15/20
10/10
20/20
5/5
30/30
0/5
0/5
0/5
0/5
0/20
Residual Graph
• Flow graph showing the remaining capacity
• Flow graph G,  Residual Graph G
R
– G: edge e from u to v with capacity c and flow f
G d’f t ith it f – G
R
: edge e’ from u to v with capacity c – f
–G
R
: edge e’’ from v to u with capacity f
Residual Graph
u
15/20
15/30
0/10
u
510
15
s t
v
20/20
15/30
5/10
s t
v
15 
5 20
15
5
Page 2


1
CSE 421
Algorithms g
Richard Anderson
Lecture 22
Network Flow
Review
• Network flow definitions
• Flow examples
• Augmenting Paths
• Residual Graph
• Ford Fulkerson Algorithm
•Cuts
• Maxflow-MinCut Theorem
Network Flow Definitions
• Flowgraph:  Directed graph with distinguished 
vertices s (source) and t (sink)
• Capacities on the edges,  c(e) >= 0
• Problem, assign flows f(e) to the edges such Problem,  assign flows f(e) to the edges such 
that:
– 0 <= f(e) <= c(e)
– Flow is conserved at vertices other than s and t
• Flow conservation: flow going into a vertex equals the flow 
going out
– The flow leaving the source is a large as possible
Find a maximum flow
a d g
5/5
20/20 20/20
20/20 20/20
0/5
0/5
0/5
0/5
s b
c f
e h
i
t
15/25
25/30
20/20
5/5
20/20
0/5
20/20
15/20
10/10
20/20
5/5
30/30
0/5
0/5
0/5
0/5
0/20
Residual Graph
• Flow graph showing the remaining capacity
• Flow graph G,  Residual Graph G
R
– G: edge e from u to v with capacity c and flow f
G d’f t ith it f – G
R
: edge e’ from u to v with capacity c – f
–G
R
: edge e’’ from v to u with capacity f
Residual Graph
u
15/20
15/30
0/10
u
510
15
s t
v
20/20
15/30
5/10
s t
v
15 
5 20
15
5
2
Build the residual graph
s
d
e
g
h
t
3/5
2/4
3/3
1/5 1/5
1/1
3/3
2/5
1/1
s
d
e
g
h
t
Residual graph:
Augmenting Path Lemma
• Let P = v
1
, v
2
, …, v
k
be a path from s to t with 
minimum capacity b in the residual graph.  
• b units of flow can be added along the path P in 
the flow graph. gp
u
s t
v
15/20
20/20
15/30
0/10
5/10
u
s t
v
5
15 
10
5 20
15
15
5
Proof
• Add b units of flow along the path P
• What do we need to verify to show we 
have a valid flow after we do this?
–
–
Ford-Fulkerson Algorithm (1956)
while not done
Construct residual graph G
R
Find an s-t path P in G
R
with capacity b > 0
Add b units along in G
If the sum of the capacities of edges leaving S 
is at most C, then the algorithm takes at most 
C iterations
Cuts in a graph
• Cut:  Partition of V into disjoint sets S, T with s in 
S and t in T.
• Cap(S,T): sum of the capacities of edges from   
S to T
Fl (S T) t fl t f S • Flow(S,T): net flow out of S
– Sum of flows out of S minus sum of flows into S
• Flow(S,T) <= Cap(S,T)
What is Cap(S,T) and Flow(S,T)
a d g
5/5
20/20 20/20
20/20 20/20
S={s, a, b, e, h},    T = {c, f, i, d, g, t}
0/5
0/5
0/5
0/5
s b
c f
e h
i
t
15/25
25/30
20/20
5/5
20/20
0/5
20/20
15/20
10/10
20/20
5/5
30/30
0/20
0/5
0/10
Page 3


1
CSE 421
Algorithms g
Richard Anderson
Lecture 22
Network Flow
Review
• Network flow definitions
• Flow examples
• Augmenting Paths
• Residual Graph
• Ford Fulkerson Algorithm
•Cuts
• Maxflow-MinCut Theorem
Network Flow Definitions
• Flowgraph:  Directed graph with distinguished 
vertices s (source) and t (sink)
• Capacities on the edges,  c(e) >= 0
• Problem, assign flows f(e) to the edges such Problem,  assign flows f(e) to the edges such 
that:
– 0 <= f(e) <= c(e)
– Flow is conserved at vertices other than s and t
• Flow conservation: flow going into a vertex equals the flow 
going out
– The flow leaving the source is a large as possible
Find a maximum flow
a d g
5/5
20/20 20/20
20/20 20/20
0/5
0/5
0/5
0/5
s b
c f
e h
i
t
15/25
25/30
20/20
5/5
20/20
0/5
20/20
15/20
10/10
20/20
5/5
30/30
0/5
0/5
0/5
0/5
0/20
Residual Graph
• Flow graph showing the remaining capacity
• Flow graph G,  Residual Graph G
R
– G: edge e from u to v with capacity c and flow f
G d’f t ith it f – G
R
: edge e’ from u to v with capacity c – f
–G
R
: edge e’’ from v to u with capacity f
Residual Graph
u
15/20
15/30
0/10
u
510
15
s t
v
20/20
15/30
5/10
s t
v
15 
5 20
15
5
2
Build the residual graph
s
d
e
g
h
t
3/5
2/4
3/3
1/5 1/5
1/1
3/3
2/5
1/1
s
d
e
g
h
t
Residual graph:
Augmenting Path Lemma
• Let P = v
1
, v
2
, …, v
k
be a path from s to t with 
minimum capacity b in the residual graph.  
• b units of flow can be added along the path P in 
the flow graph. gp
u
s t
v
15/20
20/20
15/30
0/10
5/10
u
s t
v
5
15 
10
5 20
15
15
5
Proof
• Add b units of flow along the path P
• What do we need to verify to show we 
have a valid flow after we do this?
–
–
Ford-Fulkerson Algorithm (1956)
while not done
Construct residual graph G
R
Find an s-t path P in G
R
with capacity b > 0
Add b units along in G
If the sum of the capacities of edges leaving S 
is at most C, then the algorithm takes at most 
C iterations
Cuts in a graph
• Cut:  Partition of V into disjoint sets S, T with s in 
S and t in T.
• Cap(S,T): sum of the capacities of edges from   
S to T
Fl (S T) t fl t f S • Flow(S,T): net flow out of S
– Sum of flows out of S minus sum of flows into S
• Flow(S,T) <= Cap(S,T)
What is Cap(S,T) and Flow(S,T)
a d g
5/5
20/20 20/20
20/20 20/20
S={s, a, b, e, h},    T = {c, f, i, d, g, t}
0/5
0/5
0/5
0/5
s b
c f
e h
i
t
15/25
25/30
20/20
5/5
20/20
0/5
20/20
15/20
10/10
20/20
5/5
30/30
0/20
0/5
0/10
3
Minimum value cut
u
40
10
s t
v
40
10
10
Find a minimum value cut
6
6
5
8
s
t
10
7
3
36
2
4
5
8
5
4
8
MaxFlow – MinCut Theorem
• There exists a flow which has the same value of 
the minimum cut
• Proof: Consider a flow where the residual graph 
has no s-t path with positive capacity pp py
• Let S be the set of vertices in G
R
reachable from 
s with paths of positive capacity
s t
Let S be the set of vertices in G
R
reachable 
from s with paths of positive capacity
s t u v
S
T
What can we say about the flows and capacity 
between u and v?
Max Flow - Min Cut Theorem
• Ford-Fulkerson algorithm finds a flow 
where the residual graph is disconnected, 
hence FF finds a maximum flow.
• If we want to find a minimum cut, we begin 
by looking for a maximum flow.
Performance
• The worst case performance of the Ford-
Fulkerson algorithm is horrible
u
s t
v
1000
1000
1 
1000
1000
Page 4


1
CSE 421
Algorithms g
Richard Anderson
Lecture 22
Network Flow
Review
• Network flow definitions
• Flow examples
• Augmenting Paths
• Residual Graph
• Ford Fulkerson Algorithm
•Cuts
• Maxflow-MinCut Theorem
Network Flow Definitions
• Flowgraph:  Directed graph with distinguished 
vertices s (source) and t (sink)
• Capacities on the edges,  c(e) >= 0
• Problem, assign flows f(e) to the edges such Problem,  assign flows f(e) to the edges such 
that:
– 0 <= f(e) <= c(e)
– Flow is conserved at vertices other than s and t
• Flow conservation: flow going into a vertex equals the flow 
going out
– The flow leaving the source is a large as possible
Find a maximum flow
a d g
5/5
20/20 20/20
20/20 20/20
0/5
0/5
0/5
0/5
s b
c f
e h
i
t
15/25
25/30
20/20
5/5
20/20
0/5
20/20
15/20
10/10
20/20
5/5
30/30
0/5
0/5
0/5
0/5
0/20
Residual Graph
• Flow graph showing the remaining capacity
• Flow graph G,  Residual Graph G
R
– G: edge e from u to v with capacity c and flow f
G d’f t ith it f – G
R
: edge e’ from u to v with capacity c – f
–G
R
: edge e’’ from v to u with capacity f
Residual Graph
u
15/20
15/30
0/10
u
510
15
s t
v
20/20
15/30
5/10
s t
v
15 
5 20
15
5
2
Build the residual graph
s
d
e
g
h
t
3/5
2/4
3/3
1/5 1/5
1/1
3/3
2/5
1/1
s
d
e
g
h
t
Residual graph:
Augmenting Path Lemma
• Let P = v
1
, v
2
, …, v
k
be a path from s to t with 
minimum capacity b in the residual graph.  
• b units of flow can be added along the path P in 
the flow graph. gp
u
s t
v
15/20
20/20
15/30
0/10
5/10
u
s t
v
5
15 
10
5 20
15
15
5
Proof
• Add b units of flow along the path P
• What do we need to verify to show we 
have a valid flow after we do this?
–
–
Ford-Fulkerson Algorithm (1956)
while not done
Construct residual graph G
R
Find an s-t path P in G
R
with capacity b > 0
Add b units along in G
If the sum of the capacities of edges leaving S 
is at most C, then the algorithm takes at most 
C iterations
Cuts in a graph
• Cut:  Partition of V into disjoint sets S, T with s in 
S and t in T.
• Cap(S,T): sum of the capacities of edges from   
S to T
Fl (S T) t fl t f S • Flow(S,T): net flow out of S
– Sum of flows out of S minus sum of flows into S
• Flow(S,T) <= Cap(S,T)
What is Cap(S,T) and Flow(S,T)
a d g
5/5
20/20 20/20
20/20 20/20
S={s, a, b, e, h},    T = {c, f, i, d, g, t}
0/5
0/5
0/5
0/5
s b
c f
e h
i
t
15/25
25/30
20/20
5/5
20/20
0/5
20/20
15/20
10/10
20/20
5/5
30/30
0/20
0/5
0/10
3
Minimum value cut
u
40
10
s t
v
40
10
10
Find a minimum value cut
6
6
5
8
s
t
10
7
3
36
2
4
5
8
5
4
8
MaxFlow – MinCut Theorem
• There exists a flow which has the same value of 
the minimum cut
• Proof: Consider a flow where the residual graph 
has no s-t path with positive capacity pp py
• Let S be the set of vertices in G
R
reachable from 
s with paths of positive capacity
s t
Let S be the set of vertices in G
R
reachable 
from s with paths of positive capacity
s t u v
S
T
What can we say about the flows and capacity 
between u and v?
Max Flow - Min Cut Theorem
• Ford-Fulkerson algorithm finds a flow 
where the residual graph is disconnected, 
hence FF finds a maximum flow.
• If we want to find a minimum cut, we begin 
by looking for a maximum flow.
Performance
• The worst case performance of the Ford-
Fulkerson algorithm is horrible
u
s t
v
1000
1000
1 
1000
1000
4
Better methods of finding 
augmenting paths
• Find the maximum capacity augmenting 
path
–O(m
2
log(C)) time algorithm for network flow
Find the shortest augmenting path • Find the shortest augmenting path
–O(m
2
n) time algorithm for network flow
• Find a blocking flow in the residual graph
– O(mnlog n) time algorithm for network flow
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!