n a maximum$-$flow problem, we assume edges have capacities, and there

is no limit on how much flow is allowed to pass through a vertex. Now we consider the maximum$-$

flow problem with node capacities.

Let G $=($V$,$ E$)$ be a directed graph, with source s in V $,$ sink t in V $,$ and nonnegative node capacities

$\{$cv $>=0\}$ for each v in V $.$ Given a flow in this graph, the flow though a node v is defined as f in$($v$).$

We say that a flow is feasible if it satisfies f in$($v$)<=$ cv for all nodes.

Your tasks are:

$(1)$ Give a polynomial$-$time algorithm to find an s $$ t maximum flow in a flow network with node

capacities. Prove its correctness and perform time complexity analysis.

$(2)$ Define an s$-$t cut for flow networks with node capacities, and show that the analogue of the

Max$-$Flow Min$-$Cut Theorem holds true in the node$-$capacitied networks