(5; 4) 2 4 (5; 5) (7; 5) 1 (1; 1) (2;0) 6 (1; 1) (10; 8) (8; 8) 3 5 (9:8) a) Consider the maximum flow problem from node 1 to node 6 on the network given above. On each arc we have two numbers in the form (x; y). The first number x shows the capacity of the arc and y shows the current flow on the arc. i) (2 pts) What is the value of the current flow? ii) (8 pts) What is the value of the maximum flow? What is the value of flow on arcs (2,3) and (4,6) for the optimal flow? (4 pts) Provide a minimum cut. Which arcs are in the cut? b) (4 pts) Suppose you have a network that consists of 100 nodes. You would like to find the shortest path from node 1 to node 100 that does not go through node 49. How would you solve this problem? c) (4 pts) Suppose you have a network with 100 nodes. You would like to find the shortest path from node 1 to node 100 that goes through arc (5,8). How would you solve this problem? d) (4 pts) Suppose you have a network with 100 nodes. You would like to find a flow such that the flow from the source to the sink is at least 50 and the flow on arc (8,12) is maximized. How would you solve this problem? (5; 4) 2 4 (5; 5) (7; 5) 1 (1; 1) (2;0) 6 (1; 1) (10; 8) (8; 8) 3 5 (9:8) a) Consider the maximum flow problem from node 1 to node 6 on the network given above. On each arc we have two numbers in the form (x; y). The first number x shows the capacity of the arc and y shows the current flow on the arc. i) (2 pts) What is the value of the current flow? ii) (8 pts) What is the value of the maximum flow? What is the value of flow on arcs (2,3) and (4,6) for the optimal flow? (4 pts) Provide a minimum cut. Which arcs are in the cut? b) (4 pts) Suppose you have a network that consists of 100 nodes. You would like to find the shortest path from node 1 to node 100 that does not go through node 49. How would you solve this problem? c) (4 pts) Suppose you have a network with 100 nodes. You would like to find the shortest path from node 1 to node 100 that goes through arc (5,8). How would you solve this problem? d) (4 pts) Suppose you have a network with 100 nodes. You would like to find a flow such that the flow from the source to the sink is at least 50 and the flow on arc (8,12) is maximized. How would you solve this