In the network G below, the demand values are shown on vertices (supply value if negative)....

Transcribed Image Text:

In the network G below, the demand values are shown on vertices (supply value if negative). Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge. Determine if there is a feasible circulation in this graph. You need to show all your steps. (2,6) (2,4) 5 -4 (1, 4) 9 (3,4) (2,3) (2,5) 3 -13 (2,5) (a) Reduce the Feasible Circulation with Lower Bounds problem to a Feasible Circulation problem without lower bounds. (b) Reduce the Feasible Circulation problem obtained in part a to a Maximum Flow problem in a Flow Network. (c) Using the solution to the resulting Max Flow problem explain whether there is a Feasible Circulation in G In the network G below, the demand values are shown on vertices (supply value if negative). Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge. Determine if there is a feasible circulation in this graph. You need to show all your steps. (2,6) (2,4) 5 -4 (1, 4) 9 (3,4) (2,3) (2,5) 3 -13 (2,5) (a) Reduce the Feasible Circulation with Lower Bounds problem to a Feasible Circulation problem without lower bounds. (b) Reduce the Feasible Circulation problem obtained in part a to a Maximum Flow problem in a Flow Network. (c) Using the solution to the resulting Max Flow problem explain whether there is a Feasible Circulation in G