| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Year | 2023 |
| Session | June |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Standard +0.3 This is a straightforward network flows question testing standard concepts: (a) requires describing adding a supersink (basic network modification), (b) is routine cut capacity calculation using upper bounds, and (c) tests understanding that a cut value gives an upper bound on max flow. All parts are direct application of textbook definitions with no problem-solving insight required, making it slightly easier than average even for Further Maths. |
| Spec | 7.02p Networks: weighted graphs, modelling connections |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| The new facility should be connected to nodes \(H\), \(I\) and \(J\) as these are the sinks of the network | E1 | Explains that the new facility should be connected to nodes \(H\), \(I\) and \(J\) |
| States that the new facility is a supersink | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(94\) gallons per second | B1 | Condone missing units |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Tim's cut has a value greater than \(94\) gallons per minute, so Tim's cut is not the minimum cut of the network | B1 | Compares their cut value from part (b) with Tim's cut, OR correctly identifies and finds the value of a different cut which has a value lower than \(106\) and compares this cut with Tim's cut |
| Therefore Tim's claim is incorrect as the maximum flow through the network is equal to the minimum cut of the network, which is less than or equal to \(94\) gallons per minute | B1F | Concludes that Tim's claim is not correct based on a comparison of \(106\) with their cut value |
## Question 4:
### Part 4(a):
| Answer | Mark | Guidance |
|--------|------|----------|
| The new facility should be connected to nodes $H$, $I$ and $J$ as these are the sinks of the network | E1 | Explains that the new facility should be connected to nodes $H$, $I$ and $J$ |
| States that the new facility is a supersink | B1 | |
**Subtotal: 2 marks**
### Part 4(b):
| Answer | Mark | Guidance |
|--------|------|----------|
| $94$ gallons per second | B1 | Condone missing units |
**Subtotal: 1 mark**
### Part 4(c):
| Answer | Mark | Guidance |
|--------|------|----------|
| Tim's cut has a value greater than $94$ gallons per minute, so Tim's cut is not the minimum cut of the network | B1 | Compares their cut value from part (b) with Tim's cut, OR correctly identifies and finds the value of a different cut which has a value lower than $106$ and compares this cut with Tim's cut |
| Therefore Tim's claim is incorrect as the maximum flow through the network is equal to the minimum cut of the network, which is less than or equal to $94$ gallons per minute | B1F | Concludes that Tim's claim is not correct based on a comparison of $106$ with their cut value |
**Subtotal: 2 marks**
**Question 4 Total: 5 marks**
---4 The network below represents a system of water pipes in a geothermal power station.
The numbers on each arc represent the lower and upper capacity for each pipe in gallons per second.\\
\includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-04_837_1413_493_312}
The water is taken from a nearby river at node $A$\\
The water is then pumped through the system of pipes and passes through one of three treatment facilities at nodes $H , I$ and $J$ before returning to the river.
4
\begin{enumerate}[label=(\alph*)]
\item The senior management at the power station want all of the water to undergo a final quality control check at a new facility before it returns to the river.
Using the language of networks, explain how the network above could be modified to include the new facility.
4
\item Find the value of the cut $\{ A , B , C , D , E \} \{ F , G , H , I , J \}$
4
\item Tim, a trainee engineer at the power station, correctly calculates the value of the cut $\{ A , B , C , D , E , F \} \{ G , H , I , J \}$ to be 106 gallons per second.
Tim then claims that the maximum flow through the network of pipes is 106 gallons per second.
Comment on the validity of Tim's claim.
\end{enumerate}
\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2023 Q4 [5]}}