(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.