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 and calculate its capacity correctly.
- Explain why every cut bounds the flow above.
- Handle multiple sources, multiple sinks and restricted vertices.
WHAT YOU PROBABLY THINK
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: they carry flow away from the sink, so they can only reduce what gets through, never increase it.
That is the point the opening claim misses, and it is the commonest error in the topic. Every unit of flow must cross every cut at least once in the forward direction, so no flow can exceed any cut's capacity. Finding a small cut therefore proves 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 of capacity equal to 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 collecting all the arcs that arrived, an out-vertex issuing all the arcs that leave, and a single arc between them whose capacity is the restriction. Every route through the vertex is then forced through that arc, which is exactly what the restriction means. Lower capacities on arcs are handled the same way, by insisting a minimum flow passes.
YOUR TURN
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.
THE EXAM BIT
- 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 are on which side.
- Try several cuts: the smallest one you find is the strongest bound you have.
- 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
=
1
2
.
T
h
e
a
r
c
c
r
o
s
s
i
n
g
b
a
c
k
t
o
w
a
r
d
s
t
h
e
s
o
u
r
c
e
c
o
n
t
r
i
b
u
t
e
s
n
o
t
h
i
n
g
t
o
t
h
e
c
u
t
'
s
c
a
p
a
c
i
t
y
.
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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Define a cut and calculate its capacity correctly.
- Explain why every cut bounds the flow above.
- Handle multiple sources, multiple sinks and restricted vertices.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.