Maths › Decision Mathematics 2 › Flows in networks: cuts and capacity
Flows in networks: cuts and capacity
Every way of separating the source from the sink puts a ceiling on the flow. Finding the tightest of those ceilings is half of proving a flow cannot be beaten.
Builds on Shortest paths: Dijkstra and Floyd and Minimum spanning trees.
IN THIS TOPIC
- Define a cut, calculate its capacity correctly, and explain why it bounds the flow.
- Handle multiple sources, multiple sinks and restricted vertices.
COMMON MISCONCEPTION
The capacity of a cut is the total capacity of every arc it crosses.
What a cut counts
A cut divides the vertices into two sets, one containing the source and the other the sink. Its capacity is the total capacity of the arcs directed from the source side to the sink side. Arcs crossing the other way contribute nothing at all. They carry flow back away from the sink, so they can only reduce what gets through.
Forgetting that direction rule is the commonest error in the topic. Every unit of flow has to cross every cut at least once in the forward direction, so no flow can exceed any cut's capacity. Find a small cut and you have proved an upper bound without examining a single route.
WORKED EXAMPLE
Two cuts on one network
A network has SA 10, SB 8, AC 6, AD 5, BD 7, CT 9, DT 10. Find the capacity of the cut round the source and of the cut separating {S, A, B, D} from {C, T}.
Round the source, the arcs leaving are SA and SB: capacity 10 + 8 = 18.
For the second cut, the arcs from the first set to the second are AC and DT: capacity 6 + 10 = 16.
So the flow cannot exceed 16, and the obvious cut round the source was not the binding one.
Sources, sinks and pinched vertices
With several sources, add a supersource joined to each of them by an arc whose capacity is that source's output. Do the same with a supersink for several sinks. The network then has the standard shape and every method applies unchanged.
A vertex with restricted capacity is split into two. An in-vertex collects all the arcs that arrived, an out-vertex issues all the arcs that leave, and a single arc joins them with the restriction as its capacity. Every route through the vertex is then forced along that one arc, which is exactly what the restriction means.
GUIDED PRACTICE
A restricted vertex
In the same network, vertex D can handle at most 8 units. Explain how to model this and what it does to the cut of capacity 16.
Show the working
Split D into D-in and D-out, with AD and BD arriving at D-in and DT leaving D-out.
Join D-in to D-out with an arc of capacity 8.
That new arc is now crossed by the cut in place of DT, so the cut capacity becomes 6 + 8 = 14.
The restriction has tightened the bound, since AD and BD together could have delivered 12 to D and DT could have carried 10.
ASSESSMENT FOCUS
- Count only the arcs crossing towards the sink. Arcs crossing back contribute zero.
- Draw the cut on the diagram so it is clear which vertices sit on which side.
- Split a restricted vertex into two with a single arc between them, and say what its capacity is.
CHECK YOURSELF
A cut crosses arcs of capacity 7 and 5 towards the sink and one of capacity 4 back towards the source. Find its capacity.
Show a hint
One of those arcs does not count.
Show the answer
7 + 5 = 12. The arc crossing back towards the source contributes nothing to the cut's capacity.
A cut's capacity is the total of the arcs crossing from the source side to the sink side only.
Every flow is bounded by every cut, so a small cut is a proof of an upper bound; restricted vertices are split into two joined by one arc.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the flows in networks: cuts and capacity questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Define a cut, calculate its capacity correctly, and explain why it bounds the flow.
- Handle multiple sources, multiple sinks and restricted vertices.
Open the full revision checklist to see every objective in the course in one place.