(Duality and the Max-Flow/Min-Cut Theorem) Consider a feasible max-flow problem and let Q = [S, N −S] be a minimum capacity cut separating s and t. Consider also the minimum cost flow problem...

(Duality and the Max-Flow/Min-Cut Theorem) Consider a feasible max-flow problem and let Q = [S, N −S] be a minimum capacity cut separating s and t. Consider also the minimum cost flow problem formulation for the max-flow problem Show that the price vector

is an optimal solution of the dual problem. Furthermore, show that the max- flow/min-cut theorem expresses the equality of the primal and dual optimal costs.