Lesson 1 of 7 · 14 min

Flow networks: sources, sinks and capacities

Read a flow network — its source, sink and edge capacities — find the most that can flow along a single path, and use the rule that flow in equals flow out at every junction.

What you will be able to do

  • Identify the source, the sink and the capacity of each edge of a flow network.
  • Find the largest flow that can travel along one path (its smallest capacity).
  • Use conservation of flow: at every vertex other than the source and sink, flow in = flow out.
  • Build up a flow through a network path by path without exceeding any capacity.

A farm on the Darling Downs pumps water from a dam to its storage tank through a system of pipes. Each pipe can carry only so much: a wide main might take 9 kilolitres per hour, a narrow branch only 3. The farmer wants to know the most water that can reach the tank each hour.

Adding up the pipes leaving the dam won't do — some of that water could be held up further along. To answer the question properly you need a flow network.

Definition

Flow networks

A flow network is a directed, weighted graph in which each weight is a capacity: the most that can travel along that edge per unit of time.

  • The source is the vertex where the flow starts. Edges only leave it.
  • The sink is the vertex where the flow ends. Edges only arrive at it.
  • The flow along an edge is how much actually travels along it: anything from 0 up to its capacity, in the direction of the arrow.

The farm's pipes. Capacities are in kilolitres per hour (kL/h). SS is the dam (the source) and TT is the tank (the sink).

Follow one route, SS–AA–TT. The pipe SASA could deliver 9 kL/h to AA, but ATAT can only take 6 kL/h onwards. Water can't pile up at a junction, so this route carries at most 6 kL/h.

The weakest link sets the limit. The edge of smallest capacity on a path is its bottleneck.

Key idea

Flow along one path

The largest flow that can travel along a single path is the smallest capacity on that path — not the sum of the capacities.

What is the largest flow, in kL/h, that can travel along the path SS–BB–TT on its own?

in kL/h

Key idea

Conservation of flow

Two rules hold for every flow through a network:

  1. The flow along each edge is between 0 and its capacity.
  2. At every vertex other than the source and the sink, total flow in = total flow out. Nothing is stored or lost at a junction.

So the total flow leaving the source equals the total flow arriving at the sink. That amount is the value of the flow.

Worked example

Building a flow path by path

  • Simple familiar

The farm network in the figure carries water from the dam SS to the tank TT. Capacities are in kilolitres per hour (kL/h).

(a) What is the largest flow that the path SS–AA–TT can carry?

(b) Send as much as possible along SS–AA–TT, then along SS–BB–TT, then along SS–AA–BB–TT. What total flow do you reach?

(c) Check that flow in equals flow out at AA and at BB.

6 steps

Try it yourself first, then check the working one step at a time.

Method

  1. The most a path can carry is its smallest (spare) capacity.

  2. Send that much, reduce the spare capacities, and look for another path with spare capacity.

  3. Check flow in = flow out at every middle vertex.

Watch out for

  • Adding the capacities along a path (9+6=159 + 6 = 15) instead of taking the smaller.

  • Forgetting that flow already sent uses up capacity: after step 2, SASA has only 3 left, not 9.

A flow of 13 kL/h, written flow / capacity on each edge. Check AA: in 8, out 6+2=86 + 2 = 8. Check BB: in 5+2=75 + 2 = 7, out 7.

In a different network, 11 units per minute flow into junction PP along two edges, and PP has two edges leaving it. One of them carries 4 units per minute. How much flows along the other?

Common mistake

Adding along a path

Capacities along a path are not added. Every unit that travels SS–AA–TT passes through both pipes, so the path can carry only as much as its narrowest pipe.

Building a flow path by path, as in the example, always gives a valid flow. But is 13 kL/h really the most this farm can get? The pipes leaving the dam could carry 9+5=149 + 5 = 14. Is the 14th kilolitre just hard to find, or impossible? The next lesson gives a way to be certain: cuts.

Summary

  • A flow network is a digraph whose weights are capacities. Flow starts at the source and ends at the sink.

  • The flow along an edge can be anything from 0 up to its capacity.

  • The most a single path can carry is its smallest capacity, the bottleneck.

  • At every other vertex, flow in = flow out; so flow out of the source = flow into the sink.

  • You can build a flow path by path, reducing the spare capacity each time — but that alone does not prove the flow is the largest possible.

Finished the lesson?

Try the 2 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 1 of 70% read

Save your progress with a free account