1
$\begingroup$

Problem: Let $f$ be a flow in a network $N = (V,X,Y,c)$ with vertice-set $V$, source-set $X$ and sink-set $Y$, and capacity function $c$ . Show that the resultant flow out of the sources is equal to the resultant flow into the sources.

Thoughts: I know the resultant flow out of a sub-set of a network is equal to $f^{out}(X) - f^{in}(X)$ , (the negative of which is the resultant flow into a subset) and so the problem amounts to showing that

$f^{out}(X) - f^{in}(X) = f^{in}(Y) - f^{out}(X)$.

I am stuck and need a hint to progress as I am not sure where to begin.

$\endgroup$
1
$\begingroup$

Observe that we have $$ \sum_{v \in V} f^{out}(v) = \sum_{v \in V} f^{in}(v) \tag{$1$} $$ since the flow on each edge contributes the same amount to both the LHS and the RHS of $(1)$. In addition, by definition of a flow, we have $$ f^{out}(v) = f^{in}(v) \quad\text{for } \forall v \not \in X \cup Y \tag{$2$} $$ By $(1)$ and $(2)$, we then have $$ \sum_{v \in X \cup Y} f^{out}(v) = \sum_{v \in X \cup Y} f^{in}(v) $$ Since $X \cap Y = \emptyset$, the conclusion is immediate then.

$\endgroup$
  • $\begingroup$ I don't see how the conclusion is immediate, can you elaborate on the final step? $\endgroup$ – IntegrateThis Apr 5 '17 at 15:24
  • 1
    $\begingroup$ @TheMathNoob We have $$\sum_{v \in X}f^{out}(v) + \sum_{v \in Y}f^{out}(v) = \sum_{v \in X}f^{in}(v) + \sum_{v \in Y}f^{in}(v)$$ which implies $$\sum_{v \in X}f^{out}(v) - \sum_{v \in X}f^{in}(v) = \sum_{v \in Y}f^{in}(v) - \sum_{v \in Y}f^{out}(v)$$Note that $$\sum_{v \in X}f^{out}(v) - \sum_{v \in X}f^{in}(v) = f^{out}(X) - f^{in}(X)$$ Similarly for $Y$. $\endgroup$ – PSPACEhard Apr 5 '17 at 15:41

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.