Lesson 2 of 7 · 15 min
Cuts and their capacity
Recognise a cut in a flow network, name its source and sink sides, and find its capacity by adding only the edges that cross from the source side to the sink side.
What you will be able to do
- Explain what a cut is, and decide whether a line drawn on a flow network is a cut.
- Name the source side and the sink side of a cut.
- Find the capacity of a cut, counting only edges that cross from the source side to the sink side.
Imagine taking a pair of shears to the farm's pipes from the last lesson and snipping through some of them, so that no water at all can get from the dam to the tank. Whatever set of pipes you snip, every drop that reaches the tank had to pass through one of them.
That idea — a set of edges that every unit of flow must cross — is a cut. Cuts are how you prove what a network can and can't carry.
Definition
Cut
A cut is a line through a flow network that splits its vertices into two groups:
- the source side, which contains the source, and
- the sink side, which contains the sink,
so that every path from the source to the sink crosses the line. If you removed the edges it crosses, nothing could get from source to sink.
Three cuts of the same network. Capacities are in litres per second.
Each of , and is a cut: try to trace any route from to and you'll cross each line at least once.
The capacity of a cut is the most it could let through. Add the capacities of the edges it crosses — but only the ones that point from the source side to the sink side.
Key idea
Capacity of a cut
An edge that crosses from the sink side back to the source side is not counted. Flow along it heads away from the sink, so it adds nothing to what gets through.
| Cut | Source side | Sink side | Edges counted (source side → sink side) | Capacity |
|---|---|---|---|---|
| 21 | ||||
| (not : it goes from to , sink side to source side) | 23 | |||
| 18 |
A fourth cut has source side and sink side . What is its capacity, in litres per second?
Common mistake
Counting an edge that points back
For , is wrong. crosses , but its arrow points from (sink side) to (source side). Some texts call it a "backward" edge. It contributes 0 — don't add it and don't subtract it.
Another cut has source side and sink side . What is its capacity?
Worked example
The capacity of a cut with an edge pointing back
The figure shows a cut through a network of gas pipes. Capacities are in terajoules per day (TJ/day).
(a) List the vertices on each side of the cut.
(b) Find the capacity of the cut.
Step 1: Name the two sides
The cut puts and on one side. Source side: . Sink side: .
Step 2: Find the edges that cross
Edges with one end on each side: , and the edge between and .
Step 3: Check each direction
goes from (source side) to (sink side) — counted. goes from to — counted. The edge between and points from (sink side) to (source side) — not counted.
Flow along BA heads back towards the source side, so it adds nothing to what reaches the sink.
Step 4: Add the forward edges
TJ/day.
Try it yourself first, then check the working one step at a time.
Answer
(a) Source side , sink side . (b) The capacity is TJ/day; points back across the cut, so it is not counted.
Method
Name the source side and the sink side.
Find every edge with one end on each side.
Add the capacities of those pointing from the source side to the sink side only.
Watch out for
Adding : is wrong.
Subtracting : is also wrong. A backward edge counts as 0.
Not every line is a cut. A line that fences off just one middle vertex — say a loop drawn around — leaves the route –– untouched, so flow can still get through. To check a line, make sure the source and sink end up on different sides, so that every path from one to the other crosses it.
In the network in the figure, which set of edges is not a cut?
Finding the capacity of a cut
Name the two sides
List the vertices on the source side (with ) and on the sink side (with ).
Find the edges that cross
An edge crosses the cut when its two ends are on different sides.
Keep only the forward edges
Keep an edge only if its arrow points from the source side to the sink side. Cross out any that point back.
Add their capacities
Write the sum with each edge named, then state the capacity with units.
Exam tip
When a cut is drawn for you, write the edges it crosses and their capacities, and say why you left any edge out (" points from the sink side to the source side, so it is not counted"). That sentence is often worth a mark.
Summary
A cut splits the vertices into a source side (with the source) and a sink side (with the sink), so every path from source to sink crosses it.
Its capacity is the sum of the capacities of the edges crossing from the source side to the sink side.
An edge crossing from the sink side back to the source side counts as 0.
A line that leaves some path from source to sink uncrossed is not a cut.
Naming the source side is the clearest way to describe a cut, for example .
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.