0
$\begingroup$

The strength of the flow in a transportation network is defined as the sum of the flow of each edge leaving the source.

My textbook remarked without proof that this is the same as the sum of the flow of each edge entering the sink, but I'm not sure how to prove this formally.

Terminology:

A transportation network is a finite directed graph with 2 distinguished vertices the source and the sink.

The flow is a nonnegative real valued function on the edges of the graph satisfying the following conservation criterion:

for each vertex x that is not the source nor the sink, the sum of flow on edges entering x is equal to the sum of flow on edges leaving x.

$\endgroup$

1 Answer 1

1
$\begingroup$

To deduce this equality, just add up the flow balance constraints for $i \in N \setminus \{s,t\}$: $$\sum_{(i,j)\in A} x_{i,j} - \sum_{(j,i)\in A} x_{j,i} = 0$$

Almost everything cancels out in pairs, leaving: $$\sum_{(s,j)\in A} x_{s,j} - \sum_{(j,t)\in A} x_{j,t} = 0$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .