Question 8 - A-Level Maths

AQA Further Paper 3 Discrete 2022 June — Question 8 10 marks

Exam Board	AQA
Module	Further Paper 3 Discrete (Further Paper 3 Discrete)
Year	2022
Session	June
Marks	10
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Network Flows
Type	Lower and upper capacity networks
Difficulty	Standard +0.8 This is a multi-part network flow problem requiring supersink construction, flow augmentation algorithm application, and max-flow min-cut theorem proof. While these are standard Further Maths techniques, the question demands careful execution across multiple steps, understanding of capacity constraints, and critical analysis of a claim about network improvement. The 10-mark allocation and requirement to prove optimality places it moderately above average difficulty.
Spec	7.02p Networks: weighted graphs, modelling connections 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms

Figure 1 shows a network of gas pipes. The numbers on each arc represent the lower and upper capacity for each pipe in \(\text{m}^3 \text{s}^{-1}\) The numbers in the circles represent an initial feasible flow of 73 \(\text{m}^3 \text{s}^{-1}\) through the network. \includegraphics{figure_8}

On Figure 1 above, add a supersink \(T\) to the network. [2 marks]
Using flow augmentation, find the maximum flow through the network. You must indicate any flow augmenting paths clearly in the table below. You may use Figure 2, on the page opposite, in your solution. [4 marks]
Augmenting Path Flow
Maximum flow \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
Prove that the flow found in part (b) is the maximum flow through the network. [2 marks]
A trainee engineer claims that increasing the upper capacity of the pipe \(AG\) will increase the maximum flow through the network, as the flow through this pipe cannot currently be increased. Comment on the validity of the trainee's claim. [2 marks]

Show mark scheme Show mark scheme source

Question 8:

Answer	Marks	Guidance
8(a)	Connects supersink T to nodes
G and H with two directed arcs	1.1a	M1

Includes a correct upper

capacity and a correct lower

capacity on both directed arcs

Answer	Marks	Guidance
GT and GH	1.1b	A1
Total	2
Q	Marking instructions	AO

Answer	Marks
8(b)	Finds at least one correct

augmenting path and the flow

(may be seen on diagram)

Condone T not included in

Answer	Marks	Guidance
augmenting path	3.1a	M1

SAEGT 2

SBDEGT 2

SCFHT 2

Maximum flow = 79 m3 s–1

Finds a second correct

augmenting path and the flow

Condone T not included in

Answer	Marks	Guidance
augmenting path	1.1b	A1

Finds a third correct augmenting

path and the flow, and no

incorrect paths

Condone T not included in

Answer	Marks	Guidance
augmenting path	1.1b	A1

Clearly states the correct

Answer	Marks	Guidance
maximum flow with correct units	3.2a	B1
Total	4
Augmenting Path	Flow
SAEGT	2
SBDEGT	2
SCFHT	2
Q	Marking instructions	AO

Answer	Marks
8(c)	Translates the problem of

proving the flow is maximum

into explicitly identifying the

correct minimum cut of the

network

Condone T not included in sink

Answer	Marks	Guidance
set	3.1a	M1

= 25 + 19 + 10 + 25 = 79

As the flow (79) is equal to the

value of the minimum cut (79), the

maximum flow through the network

is 79 by the maximum flow-

minimum cut theorem.

Completes a reasoned

argument by comparing the

value of the correct minimum cut

and the flow of 79 m3 s–1 and

states this flow is maximum by

naming or explaining the

maximum flow-minimum cut

Answer	Marks	Guidance
theorem	2.1	R1
Total	2
Q	Marking instructions	AO

Answer	Marks
8(d)	States or explains that AG is

currently not limiting the

maximum flow through the

Answer	Marks	Guidance
network	1.1b	M1

AG would not increase the

maximum flow through the network

as flow into node A is already

maximum.

Hence, the trainee engineer’s claim

is incorrect.

Explains why AG is not limiting

the maximum flow through the

network and then concludes that

the trainee engineer’s claim is

Answer	Marks	Guidance
incorrect	2.3	R1
Total	2
Question total	10
Q	Marking instructions	AO

Question 8:
--- 8(a) ---
8(a) | Connects supersink T to nodes
G and H with two directed arcs | 1.1a | M1
Includes a correct upper
capacity and a correct lower
capacity on both directed arcs
GT and GH | 1.1b | A1
Total | 2
Q | Marking instructions | AO | Marks | Typical solution
--- 8(b) ---
8(b) | Finds at least one correct
augmenting path and the flow
(may be seen on diagram)
Condone T not included in
augmenting path | 3.1a | M1 | Augmenting Path Flow
SAEGT 2
SBDEGT 2
SCFHT 2
Maximum flow = 79 m3 s–1
Finds a second correct
augmenting path and the flow
Condone T not included in
augmenting path | 1.1b | A1
Finds a third correct augmenting
path and the flow, and no
incorrect paths
Condone T not included in
augmenting path | 1.1b | A1
Clearly states the correct
maximum flow with correct units | 3.2a | B1
Total | 4
Augmenting Path | Flow
SAEGT | 2
SBDEGT | 2
SCFHT | 2
Q | Marking instructions | AO | Marks | Typical solution
--- 8(c) ---
8(c) | Translates the problem of
proving the flow is maximum
into explicitly identifying the
correct minimum cut of the
network
Condone T not included in sink
set | 3.1a | M1 | {S, B, C} {A, D, E, F, G, H, T}
= 25 + 19 + 10 + 25 = 79
As the flow (79) is equal to the
value of the minimum cut (79), the
maximum flow through the network
is 79 by the maximum flow-
minimum cut theorem.
Completes a reasoned
argument by comparing the
value of the correct minimum cut
and the flow of 79 m3 s–1 and
states this flow is maximum by
naming or explaining the
maximum flow-minimum cut
theorem | 2.1 | R1
Total | 2
Q | Marking instructions | AO | Marks | Typical solution
--- 8(d) ---
8(d) | States or explains that AG is
currently not limiting the
maximum flow through the
network | 1.1b | M1 | Increasing the upper capacity of
AG would not increase the
maximum flow through the network
as flow into node A is already
maximum.
Hence, the trainee engineer’s claim
is incorrect.
Explains why AG is not limiting
the maximum flow through the
network and then concludes that
the trainee engineer’s claim is
incorrect | 2.3 | R1
Total | 2
Question total | 10
Q | Marking instructions | AO | Marks | Typical solution

Show LaTeX source

Figure 1 shows a network of gas pipes.

The numbers on each arc represent the lower and upper capacity for each pipe in $\text{m}^3 \text{s}^{-1}$

The numbers in the circles represent an initial feasible flow of 73 $\text{m}^3 \text{s}^{-1}$ through the network.

\includegraphics{figure_8}

\begin{enumerate}[label=(\alph*)]
\item On Figure 1 above, add a supersink $T$ to the network.
[2 marks]

\item Using flow augmentation, find the maximum flow through the network.

You must indicate any flow augmenting paths clearly in the table below.

You may use Figure 2, on the page opposite, in your solution.
[4 marks]

\begin{tabular}{|l|l|}
\hline
Augmenting Path & Flow \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
\end{tabular}

Maximum flow \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

\item Prove that the flow found in part (b) is the maximum flow through the network.
[2 marks]

\item A trainee engineer claims that increasing the upper capacity of the pipe $AG$ will increase the maximum flow through the network, as the flow through this pipe cannot currently be increased.

Comment on the validity of the trainee's claim.
[2 marks]
\end{enumerate}

\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2022 Q8 [10]}}

This paper (10 questions)

View full paper

Q1 1 Q2 1 Q3 1 Q4 6 Q5 6 Q6 6 Q7 8 Q8 10 Q9 6 Q10 5