1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

Consider a graph of two node $s$ and $t$ and one edge $(s,t)$ with a flow $f$, $f(s,t)=1$.

Let $S=\{s\}$ and $T=\{t\}$. Then the flow across the cut $(S, T)$ is, apparently 1. Or, $$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)= f(u,v)=1.$$

$\sum_{u\in S} \sum_{v\in T} f(u,v)$ is the flow from $S$ to $T$. $\sum_{u\in S} \sum_{v\in T}f(v,u)$ is the flow from $T$ to $S$. Their difference is the flow across $(S,T)$.

Note that all ideas above does not depend on which is source node nor which is sink node. The flow across a cut $(S,T)$ just means how much (water, current, resource, etc) is flowing from $S$ to $T$.


It happens that it is required the source node is in $S$ and the sink node is in $T$ in that part of the proof. That requirement does NOT affect the explanation above. It is just a convenience measure since in a flow network we are only interested in that kind of cut. However, it does make the situation somewhat confusing.

Now let $s$ be the source node and $t$ be sink node. So that the cut $(S,T)$ above is indeed a cut as required in the proof.

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?

The first part $\sum_{u\in S} \sum_{v\in T} f(u,v)=f(u,v)$ is not necessarily the amount of flow entering the network at the source node, although it happens to be in the current example.

The second part $\sum_{u\in S} \sum_{v\in T} f(v,u)=0$ is not necessarily the amount of flow leaving the network at the sink node. In fact, it is not in the current example! The amount of flow leaving the network at the sink node is
$\sum_{u\in V}f(u,t)=1$. Now, can you read the following again?

The second part $\sum_{u\in S} \sum_{v\in T} f(v,u)$ is the flow from $T$ to $S$ while $\sum_{u\in V}f(u,\text{the sink node})$ is the flow from all nodes to the sink node. Even if $T$ consists of the sink node only, these two sums are different. The former is for flow from the sink node and the latter is for flow to the sink node. They are not only different. They are very different! They are too different.


Here are a few easy exercises about a general flow network $G=(V,E)$ with source node $s$ and sink node $t$ and a flow $f$.

Exercise 1. The amount of flow entering the network at the source node is the flow across the cut $(\{s\}, V\setminus\{s\})$.

Exercise 2. The amount of flow leaving the network at the sink node is the flow across the cut $(V\setminus\{t\}, \{t\})$.

Exercise 3. The amount of flow across any cut is the same.

$\endgroup$
  • $\begingroup$ If there is no source node or sink node, then what is $S$ and $T$? Must the difference between the flow from $S$ to $T$ and the flow from $T$ to $S$ be positive? $\endgroup$ – user8314628 Feb 20 at 5:28
  • $\begingroup$ I was emphasizing the fact that the concept of flow across a cut depending only on the cut $(S, T)$. In that proof, it happens to require the source node is in $S$ and the sink node is in $T$. We can, of course, let $s$ be the source node and $t$ be the sink node in my example. Does it make sense? $\endgroup$ – Apass.Jack Feb 20 at 5:44
  • $\begingroup$ @user8314628 $S$ and $T$ are two sets of nodes partitioned by the cut, they are not necessarily source and sink nodes. $\endgroup$ – Jinhong Chen Feb 20 at 6:29

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.