Suppose that D = (V, A: c) is a flow network and f is a maximum...

Transcribed Image Text:

Suppose that D = (V, A: c) is a flow network and f is a maximum s-t flow in D. Let U be a subset of V with sEUCV\{t}. Prove that sout (U) is a minimum s-t cut in D if and only if residual graph Df has no edge from U to V\U. Suppose that D = (V, A: c) is a flow network and f is a maximum s-t flow in D. Let U be a subset of V with sEUCV\{t}. Prove that sout (U) is a minimum s-t cut in D if and only if residual graph Df has no edge from U to V\U.

Answer rating: 100% (QA)

Solution Suppose that D V A c is a flow network and f is maximum sit flow in ... View the full answer