3. (10 pts) (a) Consider the flow graph and the flow (of value 50) shown below. Execute one iteration of the Ford- Fulkerson max-flow algorithm. Show the residual graph used to determine an augmenting path, the augmenting path, and show the resulting new flow 10/20 10/20 20/20 10/15 10/10 15/30 20/20 30/30 20/20 5/5 10 5 10/1 15/2 10/25 10/20 10/10 (b) Let G be a flow graph with a source s and a sink t and positive integer capacities on the edges Assume a maximum flow has been determined and the corresponding flow function f is given to you on every edge of G. The capacity of edge (u, v) in G increases by 5, resulting in a new flow network G'. Describe and analyze an efficient method for generating the new maximum flow in G' from flow f. Your solution needs to be significantly faster than recomputing the flow. 3. (10 pts) (a) Consider the flow graph and the flow (of value 50) shown below. Execute one iteration of the Ford- Fulkerson max-flow algorithm. Show the residual graph used to determine an augmenting path, the augmenting path, and show the resulting new flow 10/20 10/20 20/20 10/15 10/10 15/30 20/20 30/30 20/20 5/5 10 5 10/1 15/2 10/25 10/20 10/10 (b) Let G be a flow graph with a source s and a sink t and positive integer capacities on the edges Assume a maximum flow has been determined and the corresponding flow function f is given to you on every edge of G. The capacity of edge (u, v) in G increases by 5, resulting in a new flow network G'. Describe and analyze an efficient method for generating the new maximum flow in G' from flow f. Your solution needs to be significantly faster than recomputing the flow