The Minimum Flow Problem. Assume that each arc (,) E A has a lower bound lij 20 and well as an upper bound tij on the amount of flow that must be routed along it. In the minimum flow problem we wish to send a flow of minimum value from the source to the sink such that f satisfies the lower and upper bounds on every arc. (a) Show how to solve the minimum flow problem using two applications of the max-flow algorithm on modified graphs with no lower bounds, i.e. all y = 0. (b) Prove the following minflow-maxcut theorem: let the floor of an 8-t cut 8(S) bel(S) = (13)+(s) li- lues-(s) Wij. Show that the minimum value of all feasible s-t flows equals the maximum floor of all s-t cuts. The Minimum Flow Problem. Assume that each arc (,) E A has a lower bound lij 20 and well as an upper bound tij on the amount of flow that must be routed along it. In the minimum flow problem we wish to send a flow of minimum value from the source to the sink such that f satisfies the lower and upper bounds on every arc. (a) Show how to solve the minimum flow problem using two applications of the max-flow algorithm on modified graphs with no lower bounds, i.e. all y = 0. (b) Prove the following minflow-maxcut theorem: let the floor of an 8-t cut 8(S) bel(S) = (13)+(s) li- lues-(s) Wij. Show that the minimum value of all feasible s-t flows equals the maximum floor of all s-t cuts