| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Add supersource and/or supersink |
| Difficulty | Standard +0.3 This is a standard textbook exercise on network flows requiring routine application of the supersource technique and max-flow algorithm. While it involves multiple parts, each step follows a well-defined procedure taught in D2 with no novel problem-solving required. The labelling procedure and cut verification are algorithmic processes, making this slightly easier than average A-level difficulty. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Minimum capacities: \(S \to F_1 = 12\) (or max out of \(F_1\)), \(S \to F_2 = 9\), \(S \to F_3 = 12\) | B1, B1 | B1 correct arcs, B1 correct minimum capacities |
| Answer | Marks | Guidance |
|---|---|---|
| Max flow along \(SF_3CR = \min(12, 8, 14) ... = \min = 4\) ... actually \(\min(12,8,4)=4\) (via arc of capacity 4) | B1, B1 | B1 each |
| Answer | Marks | Guidance |
|---|---|---|
| Continue to find further augmenting routes | M1, A1, A1, A1 | M1 method, A1 per correct augmenting route |
| Answer | Marks | Guidance |
|---|---|---|
| Identify saturated cut: e.g. cut through \(\{BR, CR, F_2R\}\) with capacity equal to max flow; max flow \(= \) stated value | M1, A1, A1 | M1 identifying cut, A1 capacity, A1 equals flow |
# Question 11:
## Part (a):
Add supersource $S$ with arcs $S \to F_1$, $S \to F_2$, $S \to F_3$
Minimum capacities: $S \to F_1 = 12$ (or max out of $F_1$), $S \to F_2 = 9$, $S \to F_3 = 12$ | B1, B1 | B1 correct arcs, B1 correct minimum capacities |
## Part (b)(i):
Max flow along $SF_1ABR = \min(12, 6, 8, 15) = 6$
Max flow along $SF_3CR = \min(12, 8, 14) ... = \min = 4$ ... actually $\min(12,8,4)=4$ (via arc of capacity 4) | B1, B1 | B1 each |
## Part (c)(i):
Using labelling from initial flow (6 on $SF_1ABR$, 4 on $SF_3CR$):
Augmenting route $S \to F_1 \to B \to R$: flow $= \min(6,6,15-6)=6$... check capacities and residuals
Continue to find further augmenting routes | M1, A1, A1, A1 | M1 method, A1 per correct augmenting route |
## Part (c)(ii):
Identify saturated cut: e.g. cut through $\{BR, CR, F_2R\}$ with capacity equal to max flow; max flow $= $ stated value | M1, A1, A1 | M1 identifying cut, A1 capacity, A1 equals flow |
I can see these are exam answer book pages showing student work spaces and diagrams, but I don't see an actual mark scheme with marking guidance (M1, A1, B1 etc.) on these pages. What's shown appears to be:
- The **question paper** for Question 12 (network flow problem)
- **Answer book pages** with blank/partially labelled diagrams for students to complete
- A separate **D2 2003 question paper** with Questions 1 and 2
To provide the mark scheme content you're requesting, I would need the actual **mark scheme document** which would show:
- Correct answers
- Mark allocations (M1, A1, B1, DM1 etc.)
- Examiner guidance notes
Could you share the mark scheme pages? They are typically separate documents from the question paper and answer book.
---
That said, I can provide **worked solutions** to Question 12 based on the question content shown:11. A company wishes to transport its products from 3 factories $F _ { 1 } , F _ { 2 }$ and $F _ { 3 }$ to a single retail outlet $R$. The capacities of the possible routes, in van loads per day, are shown in Fig. 5.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-011_723_1172_476_337}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item On Diagram 1 in the answer booklet add a supersource $S$ to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
\item \begin{enumerate}[label=(\roman*)]
\item State the maximum flow along $S F _ { 1 } A B R$ and $S F _ { 3 } C R$.
\item Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles.
Taking your answer to part (b)(ii) as the initial flow pattern,
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item use the labelling procedure to find a maximum flow from $S$ to $R$.
Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
\item Prove that your final flow is maximal.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q11}}