Multiple sources and sinks, restricted capacities and optimal flow

Multiple sources and sinks, restricted capacities and optimal flow

Spec 3.4–5 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Several sources or sinks: add a super source SS and super sink TT with arcs of capacity equal to the supplies and demands.
  • A vertex with limited throughput is split into CinC_{\text{in}} and CoutC_{\text{out}} joined by an arc of that capacity.
  • An arc with lower and upper capacities [lower,upper][\text{lower},\text{upper}] has forward label upper −- flow and backward label flow −- lower.
  • Capacity of a cut =∑=\sum upper capacities (XX to YY) −∑-\sum lower capacities (YY to XX).
  • 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 SS with an arc to each source, and a super sink TT 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 SS and demands on arcs into TT.

supply 9supply 6demanddemandSPQXYT
Depots P and Q become sources; shops X and Y become sinks.

Shop X needs at most 8 units. Which arc gets capacity 8?

Restricted vertices

Split the vertex into CinC_{\text{in}} and CoutC_{\text{out}} joined by an arc whose capacity is the restriction.

If a vertex CC can handle only a limited total flow, say 7, split it into CinC_{\text{in}} and CoutC_{\text{out}} joined by an arc CinCoutC_{\text{in}}C_{\text{out}} of capacity 7.

Every arc that ended at CC now ends at CinC_{\text{in}}, and every arc that started at CC now starts at CoutC_{\text{out}}.

All flow through CC must use the new arc, so the throughput is at most 7. The new arc counts in cuts: the cut {S,A,B,Cin}\{S,A,B,C_{\text{in}}\} includes it.

capacity 7ABC inC outDE
Vertex C is split; all flow through C uses the arc of capacity 7.

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 [lower,upper][\text{lower},\text{upper}].

A flow is feasible if on every arc lower≤flow≤upper\text{lower}\le\text{flow}\le\text{upper} 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

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 XX to YY, then subtract the lower capacities of arcs from YY to XX.

For a cut with sets XX (containing SS) and YY (containing TT), arcs from YY to XX 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∑\sum upper (X→YX\to Y) −∑-\sum lower (Y→XY\to X)

Worked example

Arcs SASA [1,11] and BTBT [2,8] go out of X={S,B}X=\{S,B\}, and ABAB [3,9] comes into XX from YY. Find the capacity of the cut.

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 TT 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 XX to YY in the minimum cut, or lowering the lower capacity of an arc from YY to XX, increases the cut capacity. Changes to arcs elsewhere do nothing.

The gain stops when another cut becomes the smallest.

  1. 1

    Feasible flow

    start with any flow meeting all lower capacities

  2. 2

    Label and augment

    repeat until T cannot be labelled

  3. 3

    Find the cut

    its capacity must equal the flow value

Finding the optimal flow

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 SASA [1, 9] and BTBT [2, 7] go from X={S,B}X=\{S,B\} to Y={A,T}Y=\{A,T\}. Arc ABAB [3, 6] goes from YY to XX. (a) Find the capacity of this cut. (b) State what the cut tells you about the value of any feasible flow.

[4 marks]

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

Revision notes