Find a Maximum Flow Value of Flow - PowerPoint Presentation, engineering Notes | EduRev

: Find a Maximum Flow Value of Flow - PowerPoint Presentation, engineering Notes | EduRev

 Page 1


1
Find a maximum flow
Value of flow:           
a
s
d
b e
g
h t
5
20 20
20
30
5 5
5
20
5
20
20
5
20
30
c f i
25 20 5
10
20
5
20
10
5
Construct a maximum flow and indicate the flow value
Find two augmenting paths
2/5
s t
0/1
3/4
3/3
2/4
1/3
3/3
2/2
3/4
1/3
3/3
2/2
3/3
1/3
3/3
1/3
1/3
2/2
1/3
Page 2


1
Find a maximum flow
Value of flow:           
a
s
d
b e
g
h t
5
20 20
20
30
5 5
5
20
5
20
20
5
20
30
c f i
25 20 5
10
20
5
20
10
5
Construct a maximum flow and indicate the flow value
Find two augmenting paths
2/5
s t
0/1
3/4
3/3
2/4
1/3
3/3
2/2
3/4
1/3
3/3
2/2
3/3
1/3
3/3
1/3
1/3
2/2
1/3
2
Build the residual graph
d g
3/5
2/4 3/3
s
e h
t
3/3
1/5 1/5
1/1
1/1
2/5
Residual graph:
s
d
e
g
h
t
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?
–
–
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!