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?
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?
Copyright © 2021 JogjaFile Inc.
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.