Multiple sources and sinks, restricted capacities and optimal flow
Studying this course? Keep your progress in one place.
Key facts
- Several sources or sinks: add a super source and super sink with arcs of capacity equal to the supplies and demands.
- A vertex with limited throughput is split into and joined by an arc of that capacity.
- An arc with lower and upper capacities has forward label upper flow and backward label flow lower.
- Capacity of a cut upper capacities ( to ) lower capacities ( to ).
- To improve a flow, change an arc in the minimum cut; the gain stops at the next-smallest cut.
Several sources and sinks
Add a super source with an arc to each source and a super sink with an arc from each sink, then solve as normal.
A network may have several sources (depots) and several sinks (shops). Add a super source with an arc to each source, and a super sink with an arc from each sink. Then solve as a single-source, single-sink problem.
The capacity of each new arc is the supply of that source or the demand of that sink. If a source can supply any amount, give its arc infinite capacity (or a number larger than any possible flow).
Supplies go on arcs from and demands on arcs into .
Shop X needs at most 8 units. Which arc gets capacity 8?
Restricted vertices
Split the vertex into and joined by an arc whose capacity is the restriction.
If a vertex can handle only a limited total flow, say 7, split it into and joined by an arc of capacity 7.
Every arc that ended at now ends at , and every arc that started at now starts at .
All flow through must use the new arc, so the throughput is at most 7. The new arc counts in cuts: the cut includes it.
Vertex D can pass at most 12 units in total. What do you add?
Lower and upper capacities
Write the arc as [lower, upper]. The forward label is upper minus flow; the backward label is flow minus lower.
Some arcs must carry at least a minimum flow as well as at most a maximum. Write each arc as .
A flow is feasible if on every arc and flow in equals flow out at each intermediate vertex.
When labelling:
- the arrow in the direction of the arc shows upper flow (how much it can increase)
- the arrow in the opposite direction shows flow lower (how much it can decrease).
Start from a feasible flow and augment as before.
| [2, 8], flow 5 | [3, 9], flow 3 | |
|---|---|---|
| Forward label | 8 − 5 = 3 | 9 − 3 = 6 |
| Backward label | 5 − 2 = 3 | 3 − 3 = 0 |
[2, 8], flow 5
- Forward label:
- 8 − 5 = 3
- Backward label:
- 5 − 2 = 3
[3, 9], flow 3
- Forward label:
- 9 − 3 = 6
- Backward label:
- 3 − 3 = 0
An arc [4, 10] carries a flow of 7. What are the forward and backward labels?
Cuts with lower capacities
Add the upper capacities of arcs from to , then subtract the lower capacities of arcs from to .
For a cut with sets (containing ) and (containing ), arcs from to now matter: their minimum flows must return across the cut, which uses up some of the flow that can cross forwards.
With all lower capacities zero, this is the earlier rule.
- Capacity of cut upper () lower ()
Worked example
Arcs [1,11] and [2,8] go out of , and [3,9] comes into from . Find the capacity of the cut.
- 1
Forward arcs ( to ): and , so add the upper capacities: .
- 2
Backward arc ( to ): , so subtract its lower capacity: 3.
- 3
Capacity .
A cut has forward arcs with upper capacities 6 and 9, and one backward arc [2, 5]. What is its capacity?
Optimal flow and improving a network
Augment from a feasible flow until T cannot be labelled, then find a cut equal to the flow. To improve it, change an arc in the minimum cut.
To find the optimal (maximum) flow with lower capacities, start from any feasible flow, augment with the labelling procedure until cannot be labelled, then confirm with a cut whose capacity equals the flow value.
To improve the flow, change an arc in the minimum cut. Raising the upper capacity of an arc from to in the minimum cut, or lowering the lower capacity of an arc from to , increases the cut capacity. Changes to arcs elsewhere do nothing.
The gain stops when another cut becomes the smallest.
- 1
Feasible flow
start with any flow meeting all lower capacities
- 2
Label and augment
repeat until T cannot be labelled
- 3
Find the cut
its capacity must equal the flow value
The minimum cut has capacity 20 and the next smallest is 23. You raise an arc in the minimum cut by 5. What is the new maximum flow?
Try an exam question
Arcs [1, 9] and [2, 7] go from to . Arc [3, 6] goes from to . (a) Find the capacity of this cut. (b) State what the cut tells you about the value of any feasible flow.
[4 marks]
- [1]Arcs from to are and : upper capacities .
- [1]Arc goes from to , so subtract its lower capacity 3.
- [1]Capacity of the cut is .
- [1]Any feasible flow has value at most 13.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which arcs and capacities should join the super source S to the depots?
1 mark, marked against the mark scheme
Which arcs and capacities should join the super source S to the depots?
1 mark, marked against the mark scheme