Flow network: Source with in degree and sink with out degree

783 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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.