Question

QUESTION Use the Augmenting Paths method to find the maximum flow from the source node s to sink node tin the flow network represented by the graph below. In your solution show the algorithm iterations, and for each iteration show the augmenting path and that path's flow. Attach File Browse My Computer

Answer 1

SHOW AUGMENTING PATH AND PATH FLOW USING ALGORITHM

Iteration 1

• We find a path s → 4 → 3 → t that can carry a positive flow.

• The maximum flow we can send along this path is f1 = min{2, 1, 1}.

• We send f1 = 1 unit of flow along this path.

• We obtain a residual network with updated link capacities resulting from pushing the flow along the path.

2 011_ 011 01 || 111

Iteration 2

· We find a path s → 1 → 2 → t that can carry a positive flow.

· The maximum flow we can send along this path is f2 = min{4, 4, 3}.

· We send f2 = 3 units of flow along this path.

0/1 0/1

· We obtain a residual network with updated link capacities resulting from pushing the flow along this path.

113 013 1/3/ 2 011 011 1/1

Iteration 3

· We find a path s → 4 → t that can carry a positive flow.

· The maximum flow we can send along this path is f3 = min{1, 3}.

· We send f3 = 1 unit of flow along this path.

113 _ 013 113/ 2 0/1 011 1/1

· We obtain a residual network with updated link capacities resulting from pushing the flow along this path.

113 013 1/3/ 2 | 011 0/1| 211) 10/2 \

Iteration 4

· We find a path s → 1 → 3 → 4 → t that can carry a positive flow.

· The maximum flow we can send along this path is f4 = min{1, 2, 1, 2}.

We send f4 = 1 unit of flow along this path.

013 1/3 2 0/1 012

· We obtain a residual network with updated link capacities resulting from pushing the flow along this path.

113 013 014/ 1 1 011 170 org 10 | 12/ 012

· At this point we are done.

· The node 2 is disconnected from the rest of the nodes (forward capacity 0 on all outgoing links). There are no more augmenting paths.

FLOW VALUE: The maximum flow is the total flow sent: f1 + f2 + f3 + f4 = 1 + 3 + 1 + 1 = 6.