The strength of a flow equals the total flow entering the sink

graph theoryNetworknetwork-flow

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.

Best Answer

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$$

Related Question