0
$\begingroup$

I have a flow network G with a single source s and a single sink t, but out-degree(t) is not 0 and in-degree(s) is not 0.

Does removing all the edges leaving t and/or entering s change the capacity of any cut separating s and t?

$\endgroup$
0
$\begingroup$

The capacity of a cut $A,B$ where $s \in A$ and $t \in B$ is the sum of the capacities of the edges from $A$ to $B$. Edges from $B$ to $A$ aren't counted.

An edge leaving $t$ cannot be an edge from $A$ to $B$, since $t \in B$. Similarly, incoming edges of $s$ can't be counted, so these kinds of edges can be safely removed. They can't chance the capacity of a cut.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.