AN10–AN12 - Network flows and cuts | OCR A-Level Further Mathematics B (MEI)

Model transmission through capacity-limited directed arcs. AN10 checks feasible flows and introduces super sources and sinks, AN11 calculates cut capacities, and AN12 certifies a maximum flow by matching it to a cut of the same value.

Separate flow from capacity

One pipe in a transmission system is full. Does that prove the whole system is carrying its maximum possible flow? A full pipe may sit beside unused alternatives. To prove a maximum, we need a bound on the whole system as well as a feasible flow.

You already know

A directed network gives permitted directions and weights with a stated meaning. A model must identify what each vertex and arc represents; reversing an arrow changes a permitted connection.

Think of fluid moving steadily from a source $S$ to a sink $T$ , with no losses or accumulation inside the network. The same mathematics can describe data transmission or traffic rates when the model's assumptions are appropriate.

Capacity and feasible flow

An arc's capacity is its maximum permitted rate. Its flow is the actual assigned rate. A feasible flow satisfies $0\le f_{ij}\le c_{ij}$ on every directed arc and flow in equals flow out at every vertex other than the source and sink. An arc is saturated when its flow equals its capacity.

The value of the flow is the net rate leaving $S$ , equal to the net rate entering $T$ . In the examples below no arcs enter $S$ or leave $T$ , so add the flows leaving $S$ , or add those entering $T$ . Do not add the flows on every arc: the same fluid may pass through several arcs.

All these flow relations are modelling rules, not supplied formula-booklet results. Keep capacity and assigned flow in separate tables or use a clearly stated label such as “flow/capacity”.

Complete a feasible flow using conservation

Use a separate equation at each intermediate vertex. A reverse-direction arc is a separate permitted pipe, so include it on the correct side of the conservation equation.

Conservation and total value

For every intermediate vertex $v$ ,

\sum_{i\to v}f_{iv}=\sum_{v\to j}f_{vj}

Check $0\le f_{ij}\le c_{ij}$ after solving. With no incoming arcs at $S$ or outgoing arcs at $T$ ,

F=\sum_{S\to j}f_{Sj}=\sum_{i\to T}f_{iT}

Not in the formula booklet: learn it.

The following directed system has capacities in litres per minute.

Arc	$SA$	$SB$	$AB$	$BA$	$AT$	$BT$
Capacity	$8$	$6$	$3$	$2$	$5$	$9$

[DIAGRAM: asset_name: Capacity and a feasible assigned flow; asset_slug: flows_capacity_and_assignment; caption: Arc limits and actual assigned rates are different data, and both internal vertices must conserve flow; description: A directed network has S at left, A upper middle, B lower middle and T at right. Arc capacities are SA 8, SB 6, AB 3, BA 2, AT 5 and BT 9. A second panel labels the feasible assigned flows SA 7, SB 5, AB 3, BA 1, AT 5 and BT 7, all in litres per minute. The opposite AB and BA arcs are drawn separately with distinct arrowheads and labels.]
Arc limits and actual assigned rates are different data, and both internal vertices must conserve flow

Worked example 1: solve two missing rates

Question. In this system the assigned flows are $SA=7,SB=5,BA=1,AT=5$ . Determine $AB$ , $BT$ and the total flow value, checking feasibility.

Plan. Balance vertex $A$ , then vertex $B$ , and check the assigned rates against the capacities.

\begin{aligned} 7+1&=AB+5 &&\text{conservation at }A\\ AB&=3 &&\text{solve}\\ 5+3&=BT+1 &&\text{conservation at }B\\ BT&=7 &&\text{solve}\\ F&=7+5=12 &&\text{source output}\\ 5+7&=12 &&\text{sink input check} \end{aligned}

Why this step? Flow $BA$ enters $A$ but leaves $B$ , so it appears on opposite sides of the two equations.

Answer. $AB=3$ , $BT=7$ , total value $12\,\mathrm{L\,min^{-1}}$ . Every flow is non-negative and no capacity is exceeded.

Check. $AB$ and $AT$ are saturated, but other pipes have spare capacity; saturation alone does not establish a maximum.

Change only the assigned flow $SA$ from $7$ to $6$ . Keep $SB=5,BA=1,AT=5$ .

Worked example 2: a different feasible assignment

Question. Complete this revised flow and determine its value.

Plan. Reapply the same conservation equations with the changed source contribution.

\begin{aligned} 6+1&=AB+5 &&\text{at }A\\ AB&=2 &&\text{new internal flow}\\ 5+2&=BT+1 &&\text{at }B\\ BT&=6 &&\text{new sink contribution}\\ F&=6+5=11 &&\text{source value} \end{aligned}

Why this step? A changed incoming rate must propagate through the conservation equations; it cannot simply disappear at an intermediate vertex.

Answer. $AB=2$ , $BT=6$ , total $11\,\mathrm{L\,min^{-1}}$ , within all capacities.

Check. The sink receives $5+6=11$ , agreeing with the source output.

If the equations force an arc above capacity, the given partial assignment has no feasible completion. Conservation is necessary, but does not replace the capacity check.

Watch out

Wrong: conservation at $A$ is $6=AB+5+1$ in the revised assignment. Flow $BA=1$ enters $A$ ; it does not leave it. Correct: $6+1=AB+5$ , giving $AB=2$ , followed by a separate balance at $B$ .

Classify each directed flow as incoming or outgoing before writing the next balance.

Specify a cut and count its forward capacity

A cut splits the vertices into two sets: one contains $S$ , the other $T$ . To transmit flow from source to sink, the net flow must cross from the source side to the sink side somewhere.

Cut capacity

For a partition $(U,V)$ with $S\in U$ and $T\in V$ , the cut capacity is the sum of the capacities of arcs directed from $U$ to $V$ . Do not include arcs pointing from $V$ back to $U$ , and do not subtract their capacities.

Specify both vertex sets or clearly list the crossing arcs. Use the original capacity diagram, not the numbers in a particular assigned-flow diagram.

A cut gives an upper bound

For every feasible source-to-sink flow and every source–sink cut,

F\le C(U,V)=\sum_{i\in U,\,j\in V}c_{ij}

The net flow equals forward crossing flow minus reverse crossing flow. Forward flow is at most its forward capacities, while reverse flow is non-negative.

Not in the formula booklet: learn it.

Use the original capacity table $SA=8,SB=6,AB=3,BA=2,AT=5,BT=9$ .

Worked example 3: a cut with a backward arc

Question. Calculate the capacity of $U=\{S,B\}$ , $V=\{A,T\}$ .

Plan. Classify each crossing direction before summing capacities.

\begin{aligned} \text{forward cut arcs}&=SA,BA,BT &&\text{source side to sink side}\\ AB&\text{ points backwards across the cut} &&\text{exclude its capacity}\\ C(U,V)&=8+2+9=19 &&\text{sum forward capacities} \end{aligned}

Why this step? $BA$ counts here because $B$ is on the source side; its letter order alone says nothing about the cut direction.

Answer. Cut capacity $19\,\mathrm{L\,min^{-1}}$ , giving upper bound $F\le19$ .

Check. $SB$ stays within $U$ , and $AT$ within $V$ , so neither crosses the cut.

Change only the partition to $U=\{S,A\}$ , $V=\{B,T\}$ . The network itself is unchanged.

Worked example 4: a stronger cut bound

Question. Calculate this cut's capacity and compare the resulting upper bound.

Plan. Reclassify forward and backward crossings for the new sets.

\begin{aligned} \text{forward cut arcs}&=SB,AB,AT &&\text{from }\{S,A\}\text{ to }\{B,T\}\\ BA&\text{ points backwards} &&\text{do not add or subtract its capacity}\\ C(U,V)&=6+3+5=14 &&\text{new upper bound} \end{aligned}

Why this step? A cut's capacity depends on the partition. A smaller capacity gives a stronger upper bound, but is not automatically known to be the minimum cut.

Answer. Capacity $14\,\mathrm{L\,min^{-1}}$ , so $F\le14$ , stronger than $F\le19$ .

Check. For the earlier feasible value $12$ , the net crossing flow is $5+3+5-1=12$ ; the backward flow is subtracted in this check, unlike backward capacity in the capacity sum.

One identified cut bounds every feasible flow. You do not have to exhaustively list all cuts to produce a useful bound or a maximum-flow certificate.

Watch out

Wrong: the second cut has capacity $6+3+5-2$ . Backward crossing capacity is neither added nor subtracted in a cut capacity. Correct: $C=6+3+5=14$ ; subtract backward flow only when checking the net assigned flow.

List only forward cut arcs before summing the next capacities.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

AN10–AN12 - Network flows and cuts

Separate flow from capacity

Complete a feasible flow using conservation

Specify a cut and count its forward capacity

Continue this lesson.

Learn faster with Nova