What does the 'maximum flow' in a network graph mean?

Question

The maximum flow in a capacity-constrained network can be found by methods like Folk-Fulkerson. For example, in the graph below:

Here, the maximum flow from S to T has been calculated to be 19. I understand how the algorithm works, but am unclear what this '19' actually represents?

In concrete situations, for example if this is a railway network between cities S and T, what does the number '19' mean? Is is the amount of railcars that we can send out from S to T in one day unit, or what?

Thank you.

Answer 1

Indeed that would be the maximum amount of railcars we can send from S to T in a day, provided that the capacity of each arc is the amount of railcars that that arc can support in a day.

Observe that any railcar going from $S$ to $T$ must leave the set of nodes $\{S,C\}$ at least one, using one of the two arcs $S \to A$ or $C \to D$. These two arcs have capacities 10 and 9 respectively, each railcar consumes one from their capacities, hence we cannot have more that 19 railcars per day going from $S$ to $T$.

This means that you cannot send 20 railcars from S to T in a single day. If you try to send more railcars, they will get stuck at some point (at $C$ in your example).

This set $\{S,C\}$ defines a cut between $S$ and $T$ that bounds the number of railcars. Actually, any cut between $S$ and $T$ gives you an upper bound on the number of railcars, but that particular cut gives you the smallest such bound (19), and that bound is equal to the value of the maximum flow. The max-flow min-cut theorem states that there always exists such a cut, whose value equals the maximum flow value.

Answer 2

Max flow = min cut by Ford-Fulkerson.

Max flow concerns the bottleneck of the network from source to sink. In your network, the arrows $S\rightarrow A$ and $S\rightarrow C$ provide the bottleneck and correspond to the max flow of $10+9=19$.