Question 7 - A-Level Maths

AQA Further Paper 3 Discrete 2019 June — Question 7 10 marks

Exam Board	AQA
Module	Further Paper 3 Discrete (Further Paper 3 Discrete)
Year	2019
Session	June
Marks	10
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Network Flows
Type	Complete labelling procedure initialization
Difficulty	Standard +0.3 This is a standard network flows question requiring routine application of the labelling procedure (flow augmentation algorithm). While it involves multiple steps, each component is a textbook exercise: calculating cut values, labelling for potential increases/decreases, finding augmenting paths, and identifying bottleneck arcs. The question provides clear structure and guidance, making it easier than average despite being Further Maths content.
Spec	7.04a Shortest path: Dijkstra's algorithm

7 Figure 1 shows a system of water pipes in a manufacturing complex. The number on each arc represents the upper capacity for each pipe in litres per second. The numbers in the circles represent an initial feasible flow of 38 litres of water per second. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{22f11ce2-8d07-4f51-9326-b578d1e454f9-10_874_1360_609_338}

\end{figure} 7

1. Calculate the value of the cut \(\{ S , A , B , C \} \{ D , E , F , G , H , T \}\). 7
  1. (ii) Explain, in the context of the question, what can be deduced from your answer to part (a)(i). 7
2. 1. Using the initial feasible flow shown in Figure 1, indicate on Figure 2 potential increases and decreases in the flow along each arc. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{22f11ce2-8d07-4f51-9326-b578d1e454f9-11_997_1554_475_242}
    \end{figure} 7
3. (ii) Use flow augmentation on Figure 2 to find the maximum flow through the manufacturing complex. You must indicate any flow augmenting paths clearly in the table and modify the potential increases and decreases of the flow on Figure 2.
  Augmenting Path Flow
  Maximum Flow \(=\) \(\_\_\_\_\) 7
4. The management of the manufacturing complex want to increase the maximum amount of water which can flow through the system of pipes. To do this they decide to upgrade one of the water pipes by replacing it with a larger capacity pipe. Explain which pipe should be upgraded.
  Deduce what effect this upgrade will have on the maximum amount of water which can flow through the system of pipes. \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-13_2488_1716_219_153}

Show mark scheme Show mark scheme source

Question 7:

Part (a)(i):

Answer	Marks	Guidance
Answer	Mark	Guidance
44 litres per second	B1	Condone no units

Part (a)(ii):

Answer	Marks	Guidance
Answer	Mark	Guidance
The maximum flow of water through the system of water pipes is less than or equal to 44 litres per second	B1F	Must explain meaning of cut value in context, including units and pipes

Part (b)(i):

Answer	Marks	Guidance
Answer	Mark	Guidance
Finds correct potential increase and decrease for arcs \(SA\), \(SB\), \(SC\), \(GT\) and \(HT\)	M1	Condone numbers reversed
Determines correctly the potential increase and decrease for each arc	A1	—

Part (b)(ii):

Answer	Marks	Guidance
Answer	Mark	Guidance
Finds correctly one augmenting path and flow	M1	—
Finds correctly two augmenting paths and flows: \(SCHT\) flow 1, \(SBADFGT\) flow 3	A1	—
Finds at least three augmenting paths; \(SBFGT\) flow 1, \(SCBFGT\) flow 1; sum of augmenting flows must be 6	A1	—
Maximum flow \(= 38 + 6 = 44\) litres per second	B1	Condone no units

Part (c):

Answer	Marks	Guidance
Answer	Mark	Guidance
Pipe \(BF\) should be upgraded	E1	This will result in an increase of 2 litres per second through the system
New maximum flow is 2 more than previous maximum = 46 litres per second	B1F	Condone no units

## Question 7:

### Part (a)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| 44 litres per second | B1 | Condone no units |

### Part (a)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| The maximum flow of water through the system of water pipes is less than or equal to 44 litres per second | B1F | Must explain meaning of cut value in context, including units and pipes |

### Part (b)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| Finds correct potential increase and decrease for arcs $SA$, $SB$, $SC$, $GT$ and $HT$ | M1 | Condone numbers reversed |
| Determines correctly the potential increase and decrease for each arc | A1 | — |

### Part (b)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| Finds correctly one augmenting path and flow | M1 | — |
| Finds correctly two augmenting paths and flows: $SCHT$ flow 1, $SBADFGT$ flow 3 | A1 | — |
| Finds at least three augmenting paths; $SBFGT$ flow 1, $SCBFGT$ flow 1; sum of augmenting flows must be 6 | A1 | — |
| Maximum flow $= 38 + 6 = 44$ litres per second | B1 | Condone no units |

### Part (c):
| Answer | Mark | Guidance |
|--------|------|----------|
| Pipe $BF$ should be upgraded | E1 | This will result in an increase of 2 litres per second through the system |
| New maximum flow is 2 more than previous maximum = 46 litres per second | B1F | Condone no units |

---

Show LaTeX source

7 Figure 1 shows a system of water pipes in a manufacturing complex.

The number on each arc represents the upper capacity for each pipe in litres per second. The numbers in the circles represent an initial feasible flow of 38 litres of water per second.

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 1}
  \includegraphics[alt={},max width=\textwidth]{22f11ce2-8d07-4f51-9326-b578d1e454f9-10_874_1360_609_338}
\end{center}
\end{figure}

7
\begin{enumerate}[label=(\alph*)]
\item (i) Calculate the value of the cut $\{ S , A , B , C \} \{ D , E , F , G , H , T \}$.

7 (a) (ii) Explain, in the context of the question, what can be deduced from your answer to part (a)(i).

7
\item (i) Using the initial feasible flow shown in Figure 1, indicate on Figure 2 potential increases and decreases in the flow along each arc.

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 2}
  \includegraphics[alt={},max width=\textwidth]{22f11ce2-8d07-4f51-9326-b578d1e454f9-11_997_1554_475_242}
\end{center}
\end{figure}

7 (b) (ii) Use flow augmentation on Figure 2 to find the maximum flow through the manufacturing complex.

You must indicate any flow augmenting paths clearly in the table and modify the potential increases and decreases of the flow on Figure 2.

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

Maximum Flow $=$ $\_\_\_\_$

7
\item The management of the manufacturing complex want to increase the maximum amount of water which can flow through the system of pipes. To do this they decide to upgrade one of the water pipes by replacing it with a larger capacity pipe.

Explain which pipe should be upgraded.\\
Deduce what effect this upgrade will have on the maximum amount of water which can flow through the system of pipes.\\
\includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-13_2488_1716_219_153}
\end{enumerate}

\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2019 Q7 [10]}}

This paper (8 questions)

View full paper

Q1 1 Q2 1 Q3 4 Q4 6 Q5 12 Q6 6 Q7 10 Q8 10