Augmenting flows and refinements

Augmenting flows and refinements

Spec DC4–DC7 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A flow-augmenting route increases flow by its smallest spare capacity, using forward spare capacity and backward flow.
  • Stop when no augmenting route exists; the nodes reachable from SS define a minimum cut.
  • With limits [l,u][l,u] on an arc with flow ff: forward spare is u−fu-f and backward amount is f−lf-l.
  • A node with limited capacity is split into two nodes joined by an arc of that capacity.
  • Raising an arc's capacity helps only if the arc is in every minimum cut.

Augmenting a flow

Find a route from SS to TT with spare capacity, and increase the flow by the smallest spare amount on it.

A flow-augmenting route goes from SS to TT. On an arc used in its own direction the spare capacity is capacity −- flow. An arc may also be used backwards: if arc ABAB carries flow ff, travelling from BB to AA can cancel up to ff units.

Increase the flow by the smallest spare capacity (or backward flow) along the route, the bottleneck. Then update every arc: add the amount on forward arcs, subtract it on backward arcs.

Example: arc SASA with capacity 6 and flow 4 has forward spare capacity 2.

  • Forward spare capacitycapacity −- flow
  • Backward amountcurrent flow on the arc
  • Increase along a routesmallest of these

An arc has capacity 9 and flow 5. What is the forward spare capacity, and how much can be cancelled by a backward move?

The augmenting algorithm

Keep augmenting until no route exists; the flow then equals the capacity of a cut, so it is a maximum.

Start with any feasible flow (for example zero). Repeatedly find a flow-augmenting route and increase the flow by its bottleneck. Stop when no augmenting route exists.

Then the nodes reachable from SS (by forward arcs with spare capacity and backward arcs with positive flow) form the set XX. Every arc leaving XX is saturated and every arc entering it carries no flow, so the flow equals the capacity of the cut X∣YX|Y. By the max-flow min-cut theorem it is maximal.

4/60/34/50/34/4SABT
Flow/capacity on each arc, with flow 4 along S, A, B, T.

Worked example

Starting from the flow shown (value 4), find the maximum flow.

Why can you stop when no augmenting route exists?

Upper and lower capacities

With limits [l,u][l,u] the flow on an arc must stay between them, so backward moves can only cancel flow down to ll.

Some arcs have a lower capacity as well as an upper capacity, written [l,u][l,u]: the flow must satisfy l≤f≤ul\le f\le u.

A feasible flow meets every arc's limits and conserves flow at every intermediate node. Find one first (by trial if needed), then augment it.

Lower capacities also set a minimum flow: if AT≥4AT\ge4 and BT≥3BT\ge3 into the sink, every feasible flow has value at least 7.

  • Forward spare capacityu−fu-f
  • Backward amountf−lf-l
  • Capacity of a cut X∣YX|Y∑uX→Y−∑lY→X\sum u_{X\to Y}-\sum l_{Y\to X}

Worked example

An arc has limits [2,6][2,6] and carries flow 5. Find the forward spare capacity and the most that a backward move can cancel.

An arc has limits [3,8][3,8] and flow 6. What is the most flow you can cancel using it backwards?

Nodes of restricted capacity

Split the node into two joined by an arc whose capacity is the restriction.

Sometimes a node, not an arc, limits the flow, for example a depot that can handle at most 6 units per hour. This is a restricted node.

Use node splitting: replace node BB by B1B_1 and B2B_2 joined by an arc B1→B2B_1\to B_2 whose capacity is the restriction. Every arc that entered BB now enters B1B_1, and every arc that left BB now leaves B2B_2. The new arc is then treated like any other, and may appear in a minimum cut.

  1. 1

    Original node B

    arcs enter and leave B; total limited to 6

  2. 2

    Split into B1 and B2

    arcs into B go to B1; arcs out of B leave B2

  3. 3

    Join B1 to B2

    give this new arc the restriction, capacity 6

Splitting a restricted node

Worked example

Arcs SASA 8, SBSB 7, ABAB 4, ACAC 5, BCBC 6, BTBT 5, CTCT 9. Find the maximum flow when the flow through BB is limited to 6.

A node CC can handle at most 10 units. Where do you put the restriction?

Refining and evaluating a model

Raising an arc's capacity helps only if it lies in every minimum cut, and only until another cut becomes the minimum.

Once the maximum flow is known, the minimum cuts show where the bottleneck is.

Raising an arc's capacity increases the maximum flow only if that arc is in every minimum cut, and then the flow rises by the increase or until another cut becomes the minimum, whichever is smaller.

Example: raising a capacity by 2 may raise the maximum flow by only 1 if another cut has capacity one more than the current minimum.

Always check the next smallest cut before you give the new maximum, and state conclusions in context with units.

Arc in every minimum cut

  • Raising capacity can raise the maximum flow
  • Rise stops when another cut becomes the minimum

Arc not in every minimum cut

  • Raising capacity leaves the maximum flow unchanged

The minimum cut has capacity 11 and the next smallest, which does not contain the arc, has capacity 12. An arc in the only minimum cut has its capacity raised by 3. What is the new maximum flow?

Try an exam question

Arc SASA has capacity 1010 and flow 66. Arc ATAT has capacity 88 and flow 66. Find the amount by which the route S→A→TS\to A\to T can increase the flow, and the new flow on each of the two arcs.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

By how much can the flow be increased along the route S→A→TS\to A\to T?

1 mark, marked against the mark scheme

Revision notes