Question 6 - A-Level Maths

AQA D2 2008 June — Question 6 13 marks

Exam Board	AQA
Module	D2 (Decision Mathematics 2)
Year	2008
Session	June
Marks	13
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Network Flows
Type	Lower and upper capacity networks
Difficulty	Standard +0.3 This is a standard network flows question with lower/upper capacities requiring routine application of max-flow min-cut theorem and flow augmentation algorithm. While it involves multiple parts and careful bookkeeping, the techniques are algorithmic and well-practiced in D2, making it slightly easier than average A-level maths difficulty overall.
Spec	7.04e Route inspection: Chinese postman, pairing odd nodes 7.04f Network problems: choosing appropriate algorithm

6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]
The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{f98d4434-458a-4118-92ed-309510d7975a-06_796_1337_518_338}

1. Find the value of the cut \(C\).
2. Hence state what can be deduced about the maximum flow from \(S\) to \(T\).
Figure 4, printed on the insert, shows a partially completed diagram for a feasible flow of 32 litres per second from \(S\) to \(T\). Indicate, on Figure 4, the flows along the edges \(P Q , U Q\) and \(U T\).
1. Taking your feasible flow from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 5.
2. Use flow augmentation on Figure 5 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
3. Illustrate the maximum flow on Figure 6.

Show mark scheme Show mark scheme source

Question 6:

Part (a)(i)

Answer	Marks	Guidance
Answer	Marks	Guidance
Cut \(C\) passes through edges \(PU\) and \(PQ\) (forward) and any back edges	M1
Value of cut \(C = 17 + 8 = 25\) (or correct sum of capacities of forward edges in cut)	A1

Part (a)(ii)

Answer	Marks	Guidance
Answer	Marks	Guidance
Maximum flow \(\leq 25\) (upper bound given by cut \(C\))	B1

Part (b)

Answer	Marks	Guidance
Answer	Marks	Guidance
Flow along \(PQ\) stated correctly	B1
Flow along \(UQ\) stated correctly	B1
Flow along \(UT\) stated correctly	B1

Part (c)(i)

Answer	Marks	Guidance
Answer	Marks	Guidance
Potential increases shown on edges not at upper capacity	B1
Potential decreases shown on edges carrying positive flow	B1

Part (c)(ii)

Answer	Marks	Guidance
Answer	Marks	Guidance
Valid flow augmenting path identified with correct bottleneck	M1
Further augmenting paths found and applied	M1 A1
Maximum flow value stated with justification	A2

Part (c)(iii)

Answer	Marks	Guidance
Answer	Marks	Guidance
Maximum flow correctly illustrated on Figure 6	B1

I can see these images are from an AQA Mathematics Decision 2 (MD02) June 2008 exam paper — specifically the insert pages containing figures and tables for candidates to use when answering questions. These are not mark scheme pages.

The images contain:

- Figure 1: A precedence network/activity-on-node diagram (for Question 1)

- Figure 2: A blank Gantt/cascade chart grid (for Question 1)

- Figure 3: A dynamic programming table for a cabinet production scheduling problem (for Question 5)

There is no mark scheme content in these images. To extract mark scheme content, you would need the separate AQA MD02 June 2008 Mark Scheme document, which is a different publication.

If you have images of the actual mark scheme, please share those and I would be happy to extract and format the content as requested.

I can see this image contains figures (Figure 4, 5, and 6) that are provided for use in Question 6 of what appears to be an AQA Decision Mathematics paper (P5756/Jun08/MD02). However, these pages only show the figures/diagrams for the question — they do not contain the mark scheme.

The mark scheme would be in a separate document. From the figures shown, I can identify this is a maximum flow / flow augmentation problem with:

- Source: \(S\), Sink: \(T\)

- Nodes: \(P, Q, R, U, V, W\)

- Capacities shown in Figure 4

- Figure 5 is a blank working diagram with a Path/Additional Flow table

- Figure 6 shows the directed network structure for working

No mark scheme content is present on these pages — only the question figures are shown. To extract mark scheme content, you would need to provide the actual mark scheme document pages.

If you have the mark scheme pages, please share those and I can extract and format the content as requested.

# Question 6:

## Part (a)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cut $C$ passes through edges $PU$ and $PQ$ (forward) and any back edges | M1 | |
| Value of cut $C = 17 + 8 = 25$ (or correct sum of capacities of forward edges in cut) | A1 | |

## Part (a)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum flow $\leq 25$ (upper bound given by cut $C$) | B1 | |

## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Flow along $PQ$ stated correctly | B1 | |
| Flow along $UQ$ stated correctly | B1 | |
| Flow along $UT$ stated correctly | B1 | |

## Part (c)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Potential increases shown on edges not at upper capacity | B1 | |
| Potential decreases shown on edges carrying positive flow | B1 | |

## Part (c)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Valid flow augmenting path identified with correct bottleneck | M1 | |
| Further augmenting paths found and applied | M1 A1 | |
| Maximum flow value stated with justification | A2 | |

## Part (c)(iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum flow correctly illustrated on Figure 6 | B1 | |

I can see these images are from an AQA Mathematics Decision 2 (MD02) June 2008 exam paper — specifically the **insert pages** containing figures and tables for candidates to use when answering questions. These are **not mark scheme pages**.

The images contain:
- **Figure 1**: A precedence network/activity-on-node diagram (for Question 1)
- **Figure 2**: A blank Gantt/cascade chart grid (for Question 1)
- **Figure 3**: A dynamic programming table for a cabinet production scheduling problem (for Question 5)

There is **no mark scheme content** in these images. To extract mark scheme content, you would need the separate **AQA MD02 June 2008 Mark Scheme** document, which is a different publication.

If you have images of the actual mark scheme, please share those and I would be happy to extract and format the content as requested.

I can see this image contains figures (Figure 4, 5, and 6) that are provided for use in Question 6 of what appears to be an AQA Decision Mathematics paper (P5756/Jun08/MD02). However, these pages only show the **figures/diagrams** for the question — they do not contain the **mark scheme**.

The mark scheme would be in a separate document. From the figures shown, I can identify this is a **maximum flow / flow augmentation** problem with:

- Source: $S$, Sink: $T$
- Nodes: $P, Q, R, U, V, W$
- Capacities shown in Figure 4
- Figure 5 is a blank working diagram with a Path/Additional Flow table
- Figure 6 shows the directed network structure for working

**No mark scheme content is present on these pages** — only the question figures are shown. To extract mark scheme content, you would need to provide the actual mark scheme document pages.

If you have the mark scheme pages, please share those and I can extract and format the content as requested.

Show LaTeX source

6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]\\
The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second.\\
\includegraphics[max width=\textwidth, alt={}, center]{f98d4434-458a-4118-92ed-309510d7975a-06_796_1337_518_338}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Find the value of the cut $C$.
\item Hence state what can be deduced about the maximum flow from $S$ to $T$.
\end{enumerate}\item Figure 4, printed on the insert, shows a partially completed diagram for a feasible flow of 32 litres per second from $S$ to $T$. Indicate, on Figure 4, the flows along the edges $P Q , U Q$ and $U T$.
\item \begin{enumerate}[label=(\roman*)]
\item Taking your feasible flow from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 5.
\item Use flow augmentation on Figure 5 to find the maximum flow from $S$ to $T$. You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
\item Illustrate the maximum flow on Figure 6.
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{AQA D2 2008 Q6 [13]}}

This paper (6 questions)

View full paper

Q1 12 Q2 13 Q3 13 Q4 11 Q5 13 Q6 13