AS June 2025 Q2

EdexcelCurrent spec11 marksFlows in Networks

Figure 1: capacitated directed network from S to T with capacities and a feasible flow (in circles): SA 70 (63), SB 48 (44), AC 31 (31), AD 45 (32), CD 8 (0), CG 39 (31), BD 20 (20), DG 20 (20), DF 36 (32), BE 24 (24), EF 6 (6), FG 21 (21), FT 14 (14), FH 6 (3), EH 30 (18), GT 80 (72), HT 25 (21); cuts C1 and C2 shown as dashed curves — Figure 1

Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent a feasible flow from S to T.

(a) State the two conditions satisfied by a feasible flow. (2)

(b) List the seven saturated arcs in Figure 1. (1)

(i) cut \(C_1\)

(ii) cut \(C_2\) (2)

(d) Write down a flow-augmenting route that increases the flow by four units. (1)

(e) Use the answer to part (d) to draw the resulting flow pattern on Diagram 1 in the answer book. (2)

Diagram 1: the directed network of Figure 1 with no capacities or flows — Diagram 1

(f) Prove that the answer to part (e) is a maximum flow. (3)

Mark scheme (a)

Scheme	Marks	AO
On every arc actual flow cannot exceed capacity. Total flow into a vertex equals total flow out of the vertex for all vertices apart from the source and the sink.	B1 B1	1.2 1.2
	(2)

Notes

a1B1: Either condition.

a2B1: Both conditions (condone no mention of source and sink).

Scheme	Marks	AO
AC, BD, BE, DG, EF, FG, FT	B1	1.1b
	(1)

Scheme	Marks	AO
(i) \(C_1 = (31 + 45 + 20 + 6 + 25 =)\ 127\)	B1	1.1b
(ii) \(C_2 = (80 + 8 + 45 + 48 =)\ 181\)	B1	1.1b
	(2)

Scheme	Marks	AO
SADFEHT	B1	1.1b
	(1)

resulting flow: SA 67, SB 44, AC 31, AD 36, CD 0, CG 31, BD 20, DG 20, DF 36, BE 24, EF 2, FG 21, FT 14, FH 3, EH 22, GT 72, HT 25 — Mark scheme (e)

Scheme	Marks	AO
	M1 A1	1.1b 1.1b
	(2)

Mark scheme (f)

Scheme	Marks	AO
Use of max-flow min-cut theorem Identifies cut through, AC, DC, DG, DF, BE or AC, CD, DG, FG, FT, HT capacity = 111 Value of flow =111 Therefore flow is maximal.	M1 A1 A1	2.1 3.1a 2.2a
	(3)
	(11 marks)

Notes

f1M1: Construct argument based on max-flow min-cut theorem so attempt to find a cut through saturated arcs (either stated or drawn).

f1A1: Use appropriate process for finding minimum cut, with cut and value correct.

f2A1: Correct deduction that flow is maximal. Must state value of the flow and see all 4 words max flow min cut and conclusion