Node Capacities, K&T Ch.7 Ex.13. In a standard st Maximum-Flow Problem, we assume edges have capacities, and there is no limit on how much flow is allowed to pass through a node. In this problem, we consider a variant of the Maximum-Flow and Min-Cut problems with node capacities Let G-(V E) be a directed graph, with source s V, sink t ? V, and nonnegative node capacities c 0 for each u ? V. Given a flow f in this graph, the flow through a node u is defined as fn (v). We say that a flow is feasible if it satisfies the usual flow-conservation constraints and the node-capacity constraints: fin (v) S c for all nodes. Give a polynomial-time algorithm to find an s -t maximum flow in such a node-capacitated network. Define an s-t cut for node-capacitated networks, and show that the analogue of the Max-Flow Min-Cut Theorem holds true