Answer Happy

Q1) (25p) Consider the following maximum flow problem. The numbers next to each arc represent the capacity of the arc, and our goal is to find the maximum amount of flow that can be sent from the source node (so) to the sink node (şi). 8 3 8 8 si SO 6 12 2 8 A student has started implementing the Ford-Fulkerson algorithm to find the optimal solution. Currently, she has the following solution as a feasible solution. The number next to an arc represents the amount of flow sent through that arc. 5 3 8 5 3 SO 3 2 a) (15 points) Is this solution optimal? Is yes, explain why. If not, identify an augmenting path (clearly draw the augmenting path), determine the maximum amount of flow you can send through this path and specify the amount of flow on each arc in the new solution on the following graph. b) (10 points) Find a minimum cut for this network (clearly show the minimum cut on a graph and write down its capacity). What can you say about the optimality of the solution identified in part (a)? CO 3 si