Value of max flow and min cut in a graph with no directed paths

142 Views Asked by At

Let $N(x, y)$ be a network which contains no directed $(x, y)$-path.

How do I show that the value of a maximum flow and the capacity of a minimum cut in $N$ are both zero?

1

There are 1 best solutions below

3
On

Apply weak duality: maximum flow is at most minimum cut, so if you exhibit a flow and cut that have the same value, they are both optimal.