Explanations 
Textbooks 
Flashcards 
91影视 AI 
Notes 
Study Plans 
Study Sets 
Find a degree 
Magazine Chapter 7: Q10E (page 240)
For the following network, with edge capacities as shown, find the maximum flow from S to T, along with a matching cut.
Short Answer
The maximum flow is obtained with the residual capacity 13 and the matching cut is{S,C,F} and {A,B,D,E,G,T}
Step by step solution
Step 1:
Choose the augmenting path as S -> A -> D -> G -> T and the edge, which has the lowest capacity along the path, is A -> D andit has the capacity 4.
The following diagram represents it:
In the above diagram,
Left side is the current path and right side is the residual path.
The residual capacity is 4.
Subtract 4 from the capacity of the forward edge. Therefore, its capacity 6 now becomes 2 and the capacity of the reverse edge becomes 4.
Subtract 4 from the capacity of the forward edge. Therefore, its capacity 4 now becomes 0 and the capacity of the reverse edge becomes 4.
Subtract 4 from the capacity of the forward edge. Therefore, its capacity 5 now becomes 1 and the capacity of the reverse edge becomes 4.
Subtract 4 from the capacity of the forward edge. Therefore, its capacity 12 now becomes 8 and the capacity of the reverse edge becomes 4.
Step 2:
Choose the augmenting path as S -> A -> B -> E -> G -> T and the edge, which has the lowest capacity along the path, and it has the capacity 2.
The following diagram represents it:
In the above diagram,
Left side is the current path and right side is the residual path.
The residual capacity is 2.
Subtract 2 from the capacity of the forward edge. Therefore, its capacity 2 now becomes 0 and the capacity of the reverse edge becomes 6 from 4.
Subtract 2 from the capacity of the forward edge. Therefore, its capacity 2 i now becomes 0 and the capacity of the reverse edge becomes 2.
Subtract 2 from the capacity of the forward edge. Therefore, its capacity 20 now becomes 18 and the capacity of the reverse edge becomes 2.
Subtract 2 from the capacity of the forward edge. Therefore, its capacity 10 now becomes 8 and the capacity of the reverse edge becomes 2.
Step 3:
Subtract 2 from the capacity of the forward edge. Therefore, its capacity 8 now becomes 6 and the capacity of the reverse edge becomes 6 from 4.
Choose the augmenting path as S -> B -> E -> G -> T and the edge, which has the lowest capacity along the path, and it has the capacity 1.
The following diagram represents it:
In the above diagram,
Left side is the current path and right side is the residual path.
The residual capacity is 1.
Subtract 1 from the capacity of the forward edge. Therefore, its capacity 1 now becomes 0 and the capacity of the reverse edge becomes 1.
Subtract 1 from the capacity of the forward edge. Therefore, its capacity 18 now becomes 17 and the capacity of the reverse edge becomes 3 from 2.
Subtract 1 from the capacity of the forward edge. Therefore, its capacity 8 now becomes 7 and the capacity of the reverse edge becomes 3 from 2.
Subtract 1 from the capacity of the forward edge. Therefore, its capacity 6 now becomes 5 and the capacity of the reverse edge becomes 7 from 6.
Step 4:
Choose the augmenting path as S-> C -> F -> T and the edge, which has the lowest capacity along the path, and it has the capacity 4.
The following diagram represents it:
In the above diagram,
Left side is the current path and right side is the residual path.
The residual capacity is 4.
Subtract 4 from the capacity of the forward edge. Therefore, its capacity 10 now becomes 6 and the capacity of the reverse edge becomes 4.
Subtract 4 from the capacity of the forward edge. Therefore, its capacity 5 now becomes 1 and the capacity of the reverse edge becomes 4.
Subtract 4 from the capacity of the forward edge. Therefore, its capacity 4 now becomes 0 and the capacity of the reverse edge becomes 4.
Step 5:
Choose the augmenting path as S -> C -> B -> E -> G -> T and the edge, which has the lowest capacity along the path, and it has the capacity 2.
The following diagram represents it:
In the above diagram,
Left side is the current path and right side is the residual path.
The residual capacity is 2.
Subtract 2 from the capacity of the forward edge. Therefore, its capacity 6 now becomes 4 and the capacity of the reverse edge becomes 6 from 4.
Subtract 2 from the capacity of the forward edge. Therefore, its capacity 2 now becomes 0 and the capacity of the reverse edge becomes 2.
Subtract 2 from the capacity of the forward edge. Therefore, its capacity 17 now becomes 15 and the capacity of the reverse edge becomes 5 from 3.
Step 6:
Subtract 2 from the capacity of the forward edge. Therefore, its capacity 7 now becomes 5 and the capacity of the reverse edge becomes 5 from 3.
Subtract 2 from the capacity of the forward edge. Therefore, its capacity 5 now becomes 3 and the capacity of the reverse edge becomes 9 from 7.
The maximum flow is obtained with the residual capacity 4+2+1+4+2=13
Then cut the partition into two, let it be 鈥淢鈥� and 鈥淣鈥�. Both should be a disjoint group where 鈥淪鈥� should be in 鈥淢鈥� and 鈥淭鈥� should be in 鈥淣鈥�.
LetM={S,C,F}andN={A,B,D,E,G,T}
Cut 鈥淢鈥� is shown below:
Cut 鈥淣鈥� is shown below:
Therefore, the maximum flow is obtained with the residual capacity 13 and the matching cut is {S,C,F} and {A,B,D,E,G,T}
Over 30 million students worldwide already upgrade their learning with 91影视!
