(6) The Minimum Flow Problem. Assume that each arc (i,j) E A has a lower bound lij > 0 and well as an upper bound wij on the amount of flow that must be routed along it. In the minimum flow problem we wish to send a flow f 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 lij = 0. (b) Prove the following minflow-maxcut theorem: let the floor of an s-t cut 8+(S) bel(S) = lijles+(s) lij-les-(5) Uij. Show that the minimum value of all feasible s- t flows equals the maximum floor of all s-t cuts. (6) The Minimum Flow Problem. Assume that each arc (i,j) E A has a lower bound lij > 0 and well as an upper bound wij on the amount of flow that must be routed along it. In the minimum flow problem we wish to send a flow f 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 lij = 0. (b) Prove the following minflow-maxcut theorem: let the floor of an s-t cut 8+(S) bel(S) = lijles+(s) lij-les-(5) Uij. Show that the minimum value of all feasible s- t flows equals the maximum floor of all s-t cuts