Question: Given the following directed graph with 6 nodes and 10 directed arcs (i,j) with capacities u(i,j), find the maximum flow from source node 1 to
Given the following directed graph with 6 nodes and 10 directed arcs (i,j) with capacities u(i,j), find the maximum flow from source node 1 to sink node 6 and the minimum cut using the Ford-Fulkerson labeling algorithm:
u(1,2) = 3, u(1,3) = 2, u(1,4) = 1, u(2,5) = 4, u(3,4) = 1,
u(3,6) = 2, u(4,2) = 1, u(4,6) = 2, u(5,4) = 1, u(5,6) = 1.
Note: If you draw the directed graph with nodes 1 to 4 to 6 on a straight-line path and nodes 2 followed by 5 above that line and node 3 below that line, no directed arcs will overlap each other and the structure of the network will be clear.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
