Lesson 2: Cuts and their capacity
The capacity of a cut with an edge pointing back
SkillsCapacity of a cutIdentifying cuts
Worked example
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.
Answer
(a) Source side , sink side . (b) The capacity is TJ/day; points back across the cut, so it is not counted.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
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.