2. Consider the directed graph G = (V, E) below with non-negative capacities c : E R0 and an (s, t)-flow f : E R0 that is feasible with respect to c. Each edge is labeled with its flow/capacity.

y. s a b c d t 5/20 0/10 0/10 5/5 5/5 5/15 0/15 0/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 with its residual capacity.

(b) Describe an augmenting path s = v0v1. . .vr = t in Gf by either drawing the path in your residual graph or listing the paths vertices in order.

(c) Let F = mini cf (vivi+1 ) and let f 0 : E R0 be the flow obtained from f by pushing F units through your augmenting path. Draw a new copy of G, and label its edges with the flow values for f 0 . 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 R0 on the edges and two special vertices s and t. Suppose we assign a non-negative limit ` : V \ {s, t} R0 for the amount of flow that can pass through each vertex other than s or t. Formally, a flow f : E R0 is feasible with respect to both c and ` if for all edges e E we have f (e) c(e) and for all vertices v V \ {s, t} we have P u f (uv) `(v). Describe and analyze an algorithm to compute a graph G 0 = (V 0 , E 0 ) with non-negative edge capacities c 0 : E 0 R0 but no vertex limits so that the value of the maximum feasible flow in G 0 with respect to c 0 is equal to the value of the maximum feasible flow in G with respect to both c and `.