| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Apply labelling procedure for max flow |
| Difficulty | Moderate -0.3 This is a standard D1 network flows question requiring routine application of the labelling procedure algorithm. While multi-part with several marks, it involves straightforward algorithmic steps (drawing digraph, calculating cuts, applying max-flow procedure) that are well-practiced textbook exercises with no novel problem-solving required. Slightly easier than average due to being purely procedural. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| To From | \(S\) | \(A\) | \(B\) | \(C\) | D | \(T\) |
| S | - | 35 | 30 | 55 | - | - |
| A | - | - | - | - | - | 50 |
| B | - | 12 | - | 8 | - | 20 |
| C | - | - | - | - | 15 | 30 |
| D | - | - | - | - | - | 14 |
| T | - | - | - | - | - | - |
| Answer | Marks | Guidance |
|---|---|---|
| (a) [Network diagram with weighted edges and flow indicators] | M2 A1 | |
| (b) \(50 + 20 + 30 + 15 = 115\) | A1 | |
| (c) Minimum cut = \(\{S, C, D\} | \{A, B, T\} = 109\) | M1 A1 |
| (d) e.g. start with \(SAT = 35\), \(SBT = 20\), \(SCT = 30\). Augment \(SBAT\) by 10 and \(SCDT\) by 14 giving maximum flow below [Flow diagram with values and circles] | M4 A4 | |
| (e) This is maximum flow as it is equal to the minimum cut | B1 | |
| (f) e.g. maximum traffic flow between 2 points on a one-way system | B1 | (16) |
**(a)** [Network diagram with weighted edges and flow indicators] | M2 A1 |
**(b)** $50 + 20 + 30 + 15 = 115$ | A1 |
**(c)** Minimum cut = $\{S, C, D\} | \{A, B, T\} = 109$ | M1 A1 |
**(d)** e.g. start with $SAT = 35$, $SBT = 20$, $SCT = 30$. Augment $SBAT$ by 10 and $SCDT$ by 14 giving maximum flow below [Flow diagram with values and circles] | M4 A4 |
**(e)** This is maximum flow as it is equal to the minimum cut | B1 |
**(f)** e.g. maximum traffic flow between 2 points on a one-way system | B1 | (16) |
---6. The table below shows the maximum flows possible within a system.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
To From & $S$ & $A$ & $B$ & $C$ & D & $T$ \\
\hline
S & - & 35 & 30 & 55 & - & - \\
\hline
A & - & - & - & - & - & 50 \\
\hline
B & - & 12 & - & 8 & - & 20 \\
\hline
C & - & - & - & - & 15 & 30 \\
\hline
D & - & - & - & - & - & 14 \\
\hline
T & - & - & - & - & - & - \\
\hline
\end{tabular}
\end{center}
For example, the maximum flow from $B$ to $A$ is 12 units.
\begin{enumerate}[label=(\alph*)]
\item Draw a digraph to represent this information.
\item Give the capacity of the cut $\{ S , A , B , C \} \mid \{ D , T \}$.
\item Find the minimum cut, stating its capacity, and expressing it in the form $\{ \quad \} \mid \{ \quad \}$.
\item Use the labelling procedure to find the maximum flow from $S$ to $T$. You should list each flow-augmenting route you find together with its flow.
\item Explain how you know that you have found the maximum possible flow.
\item Give an example of a practical situation that could be modelled by the original table.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q6 [16]}}