What is a flow through the cut in the Ford-Fulkerson algorithm?
-
05-11-2019 - |
Question
In page 12 of the slide, it states flow across a cut $(S, T)$ is $f(S, T) = \sum_{u\in S} \sum_{v\in T} f(u,v) - \sum_{u\in S} \sum_{v\in T} f(v,u)$.
I think the first part $\sum_{u\in S} \sum_{v\in T} f(u,v)$ is the amount of flow entering the network at the source node. The second part $\sum_{u\in S} \sum_{v\in T} f(v,u)$ is the amount of flow leaving the network at the sink node. Shouldn't these two be the same? Why the flow across a cut is the difference of these two?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange