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$

1 Answer 1

1
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .