| Exam Board | AQA |
|---|---|
| Module | Further AS Paper 2 Discrete (Further AS Paper 2 Discrete) |
| Session | Specimen |
| Marks | 4 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Moderate -0.5 This is a standard network flows question requiring systematic calculation of cut capacities from a given diagram and application of the max-flow min-cut theorem. Part (a) involves routine addition of arc capacities crossing each cut (computational but straightforward), part (b) requires stating the minimum cut value (direct recall of theorem), and part (c) asks for a feasible flow pattern. While it requires careful bookkeeping and understanding of the topic, it's a textbook application with no novel problem-solving or proof required. Slightly easier than average due to its procedural nature. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Cut | Value | |
| \{ S \} | \(\{ P , Q , R , T \}\) | 31 |
| \(\{ S , P \}\) | \(\{ Q , R , T \}\) | 32 |
| \(\{ S , Q \}\) | \(\{ P , R , T \}\) | |
| \(\{ S , R \}\) | \(\{ P , Q , T \}\) | |
| \(\{ S , P , Q \}\) | \(\{ R , T \}\) | 30 |
| \(\{ S , P , R \}\) | \(\{ Q , T \}\) | 37 |
| \(\{ S , Q , R \}\) | \(\{ P , T \}\) | 35 |
| \(\{ S , P , Q , R \}\) | \(\{ T \}\) | 30 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| 35 and 36 | B1 | Determines correctly the value of both cuts |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Max flow \(= 30\) as max flow \(=\) min cut and value of minimum cut is 30 | E1 | Deduces maximum flow using max-flow min-cut theorem with reasoning |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(SR = 7,\ QR = 5,\ RT = 12,\ QT = 8,\ PT = 10\) | B1 | Determines correctly flow along saturated arcs |
| \(SP = 15\) and \(SQ = 8\) and \(PQ = 5\), or \(SP = 14\) and \(SQ = 9\) and \(PQ = 4\) | B1 | Determines correctly possible flow for each of \(SP\), \(SQ\) and \(PQ\) |
# Question 7:
## Part 7(a):
| Answer | Mark | Guidance |
|--------|------|----------|
| 35 and 36 | B1 | Determines correctly the value of both cuts |
## Part 7(b):
| Answer | Mark | Guidance |
|--------|------|----------|
| Max flow $= 30$ as max flow $=$ min cut and value of minimum cut is 30 | E1 | Deduces maximum flow using max-flow min-cut theorem with reasoning |
## Part 7(c):
| Answer | Mark | Guidance |
|--------|------|----------|
| $SR = 7,\ QR = 5,\ RT = 12,\ QT = 8,\ PT = 10$ | B1 | Determines correctly flow along saturated arcs |
| $SP = 15$ and $SQ = 8$ and $PQ = 5$, or $SP = 14$ and $SQ = 9$ and $PQ = 4$ | B1 | Determines correctly possible flow for each of $SP$, $SQ$ and $PQ$ |7 The network shows a system of pipes, where $S$ is the source and $T$ is the sink.\\
The capacity, in litres per second, of each pipe is shown on each arc.\\
The cut shown in the diagram can be represented as $\{ S , P , R \} , \{ Q , T \}$.\\
\includegraphics[max width=\textwidth, alt={}, center]{ba9e9840-ce27-4ca7-ab05-50461d135445-10_629_1168_616_557}
7
\begin{enumerate}[label=(\alph*)]
\item Complete the table below to give the value of each of the 8 possible cuts.
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
\multicolumn{2}{|c|}{Cut} & Value \\
\hline
\{ S \} & $\{ P , Q , R , T \}$ & 31 \\
\hline
$\{ S , P \}$ & $\{ Q , R , T \}$ & 32 \\
\hline
$\{ S , Q \}$ & $\{ P , R , T \}$ & \\
\hline
$\{ S , R \}$ & $\{ P , Q , T \}$ & \\
\hline
$\{ S , P , Q \}$ & $\{ R , T \}$ & 30 \\
\hline
$\{ S , P , R \}$ & $\{ Q , T \}$ & 37 \\
\hline
$\{ S , Q , R \}$ & $\{ P , T \}$ & 35 \\
\hline
$\{ S , P , Q , R \}$ & $\{ T \}$ & 30 \\
\hline
\end{tabular}
\end{center}
7
\item State the value of the maximum flow through the network.
Give a reason for your answer.\\[0pt]
[1 mark]
7
\item Indicate on Figure 1 a possible flow along each arc, corresponding to the maximum flow through the network.\\[0pt]
[2 marks]
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{ba9e9840-ce27-4ca7-ab05-50461d135445-11_618_1150_1260_557}
\end{center}
\end{figure}
\end{enumerate}
\hfill \mbox{\textit{AQA Further AS Paper 2 Discrete Q7 [4]}}