2. Consider the directed graph G = (V,E) below with non-negative capacities c : E R20 and an (s, t)-flow f : E R20 that is feasible with respect to c. Each edge is labeled with its flow/capacity. 20 o/15 o/10 o/10 5/15 o/10 5/15 An (s, t)-flow f. Each edge is labeled with its flow/capacity. (a) Draw the residual graph Gf -(V,Ef) for flow f. Be sure to label every edge of Gf (b) Describe an augmenting path s = Vo-w1y, = t in Gf by either drawing the (c) Let F = mini cf(w-wi+1) and let f, : E R20 be the flow obtained from f by pushing with its residual capacity. path in your residual graph or listing the path's vertices in order. F units through your augmenting path. Draw a new copy of G, and label its edges with the flow values for f'. Is your new flow a maximum flow in G? (d) For this last part, let G = (V,E) be an arbitrary directed graph (not necessarily the one given above) with non-negative capacities c : E-R20 on the edges and two special vertices s and t. Suppose we assign a non-negative limit 1 : {s, t} R20 for the amount of flow that can pass through each vertex other than s or t. Formally, a flow f : E R20 is feasible with respect to both c and 1 if for all edges e E E we have f (e) c(e) and for all vertices v e V \ {s, t } we have uf (u-v) 1 (v). Describe and analyze an algorithm to compute a graph G'(VE) with non-negative edge capacities c' : E' R>0 but no vertex limits so that the value of the maximum feasible flow in G' with respect to c' is equal to the value of the maximum feasible flow in G with respect to both c and l