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.
- Value a cut in a network whose arcs carry lower capacities as well as upper ones.
- Say when a flow is feasible under lower capacities, and why one may not exist.
COMMON MISCONCEPTION
The capacity of a cut is the total capacity of every arc it crosses.
Only the arcs directed from the source side to the sink side are counted. An arc crossing back carries flow away from the sink and contributes nothing, so including it inflates the cut and weakens the bound it gives. Where arcs carry lower capacities as well, an arc crossing back has to carry its floor, and that floor is taken off the upper capacities crossing forward.
The capacity of a cut
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.
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. A cut of small capacity therefore establishes an upper bound on the flow without examining any 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.
Arcs with a floor as well as a ceiling
Some arcs carry a lower capacity as well as an upper one: a contract to deliver at least so much, a pipe that silts up below a certain rate, a machine that idles badly when run slowly. Write the pair on the arc with the floor first, so an arc marked 2 to 6 has to carry at least 2 and at most 6. A flow is feasible when it respects both numbers on each arc and still balances at each intermediate vertex, and producing one such flow becomes the first piece of work rather than a formality.
Floors also change what a cut is worth. The flow across a cut is the flow forward less the flow back, so the forward arcs contribute at most their upper capacities as before, while a backward arc now removes at least its lower capacity instead of nothing. The value of the cut is therefore the total of the upper capacities crossing towards the sink minus the total of the lower capacities crossing back, and it bounds the flow just as the simpler count did.
WORKED EXAMPLE
A cut with a floor across it
A network has vertices S, A, B, T and arcs SA 0 to 10, SB 0 to 8, AB 2 to 6, AT 0 to 7 and BT 0 to 9, the first number of each pair being the lower capacity. Find the value of the cut separating {S, B} from {A, T}.
Crossing towards the sink are SA, of upper capacity 10, and BT, of upper capacity 9.
Crossing back is AB, which runs from A on the sink side to B on the source side, and it has to carry its floor of 2.
The value is 10 + 9 − 2 = 17.
Without the floor that arc would have contributed nothing and the cut would have been worth 19, so the floor has tightened the bound rather than loosened it.
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 arrive, 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.
- Where the arcs carry floors, subtract the lower capacity of each arc crossing back instead of ignoring it.
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.
An arc with a lower capacity has to carry its floor, so a cut is valued at the upper capacities forward less the floors crossing back.
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.
- Value a cut in a network whose arcs carry lower capacities as well as upper ones.
- Say when a flow is feasible under lower capacities, and why one may not exist.
Open the full revision checklist to see every objective in the course in one place.