Network Flow

Network flow is about how much can move through a network of pipes, roads or cables. It was worth 6 marks in NESA's sample HSC paper. The questions are short and methodical: if you know how to measure a cut correctly, you can find the maximum flow every time.

• Terminology: flow network, source, sink, capacity, flow, cut, capacity of a cut, maximum flow, minimum cut.
• Draw a weighted, directed network from a table.
• Find the capacity of a cut, and the minimum cut.
• Use the maximum-flow minimum-cut theorem to solve small network flow problems.
• Examine what happens when an edge's capacity is increased or reduced.
• Explain whether a network's capacity is enough to meet demand.

A flow network is a directed, weighted network that carries something from one place to another: water through pipes, cars along roads, data through cables.

• The source (often S) is where everything starts. The sink (often T) is where everything ends.
• Each edge has an arrow showing the direction of flow, and a capacity: the most it can carry, such as 9 kL per hour.
• The flow along an edge is how much it actually carries. It can't exceed the capacity.
• At every vertex other than the source and sink, flow in = flow out. Nothing is stored or lost along the way.
• The flow of the network is the total leaving the source, which equals the total arriving at the sink.

From a table to a diagram

A table lists each edge, its direction and its capacity. Draw one vertex for each place, put S on the left and T on the right, then draw each edge as an arrow labelled with its capacity. The network below is used throughout this page. It is a set of water pipes, with capacities in kilolitres per hour.

A cut is a line through the network that separates the source from the sink, so that nothing could get from S to T without crossing it. Every cut splits the vertices into a source side (containing S) and a sink side (containing T).

The capacity of a cut is the sum of the capacities of the edges it crosses that go from the source side to the sink side. Edges crossing the other way (sink side back to source side) count as zero.

Example: measuring cuts

• A cut through S → A and S → B: capacity $10+8=18$.
• A cut with S and A on the source side, through S → B, A → B and A → C: capacity $8+3+6=17$.
• A cut with S and B on the source side, through S → A, B → C and B → D: capacity $10+4+7=21$. This cut also crosses A → B, but that edge flows from the sink side (A) back to the source side (B), so it adds nothing.
• A cut through C → T and D → T: capacity $9+6=15$.

The minimum cut is the cut with the smallest capacity. Check all the sensible cuts and choose the smallest. In this network it is the cut through C → T and D → T, with capacity 15.

The maximum flow through a network equals the capacity of its minimum cut.

The idea is simple: everything that reaches T has to cross every cut, so the flow can never be more than the smallest cut. And the theorem says you can always reach that limit. The minimum cut is the bottleneck of the network.

Worked example: maximum flow

For the water network above:

(a) Find the maximum flow from S to T.

Step 1: list the main cuts and their capacities (count only edges going from the source side to the sink side). The other possible cuts, such as the one with S and B on the source side (21), are all larger.

Step 2: the minimum cut has capacity 15, so the maximum flow is 15 kL per hour.

Step 3 (a check): show a flow of 15 that fits every capacity and has flow in = flow out at each vertex.

At A: in 9, out $3+6=9$. At B: in $6+3=9$, out $3+6=9$. At C: in $6+3=9$, out 9. At D: in 6, out 6. Total into T: $9+6=15$.

(b) A town needs 16 kL per hour. Can this network meet the demand? No. The maximum flow is 15 kL per hour, so it is 1 kL per hour short, no matter how the water is routed.

(c) The pipe D → T is upgraded from 6 to 9 kL per hour. What is the new maximum flow?

The cut through C → T and D → T now has capacity $9+9=18$. But the cut through C → T and B → D still has capacity $9+7=16$, and that is now the smallest. The new maximum flow is 16 kL per hour, which just meets the town's demand.

Notice that increasing D → T by 3 only increased the maximum flow by 1, because a different cut became the bottleneck.

• Increasing the capacity of an edge in the minimum cut can increase the maximum flow, but only until another cut becomes the minimum.
• Increasing an edge that is not in any minimum cut changes nothing. In the example, widening S → A from 10 to 20 would not help at all.
• Reducing the capacity of an edge in the minimum cut (a burst pipe, a lane closure) reduces the maximum flow by the same amount. Reducing an edge with spare capacity may change nothing until it becomes a bottleneck.
• To decide which single upgrade helps most, look at the minimum cut first, then check the next smallest cut.

• Counting an edge that crosses the cut from the sink side back to the source side. It counts as zero.
• Drawing a "cut" that doesn't separate S from T, so a path gets through without crossing it.
• Adding up all the edges into T, or all the edges out of S, and calling that the maximum flow without checking other cuts.
• Finding the maximum cut instead of the minimum.
• Assuming that increasing any edge increases the flow.
• Forgetting units, such as kL per hour or cars per minute.

• Draw your cuts clearly on the diagram, and write the capacity of each beside it.
• In a "find the maximum flow" question, name the minimum cut (list its edges) and quote the theorem in a few words: maximum flow equals minimum cut capacity.
• Explain whether demand is met: compare the demand with the maximum flow, both with units, and give a conclusion in context.
• For "what happens if this edge is increased", recheck the cuts; another cut may now be smallest.

• Networks, paths and trees (Year 11): vertices, edges, weighted and directed networks.
• Critical path analysis: another kind of directed network, where the weights are times.