| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2016 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | List saturated arcs |
| Difficulty | Easy -1.2 This is a straightforward network flows question requiring basic identification of saturated arcs (where flow equals capacity) and routine application of standard algorithms. Part (a) is pure observation, parts (b-c) are reading values, part (d) requires finding an augmenting path by inspection (only 3 units), and part (e) applies the max-flow min-cut theorem. All techniques are standard D2 content with no novel problem-solving required. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Saturated arcs: \(S \to C\) (22), \(S \to B\) (20), \(C \to F\) (30), \(B \to C\) (8) | B1 B1 | One mark per two correct arcs |
| Answer | Marks |
|---|---|
| Initial flow = 75 | B1 |
| Answer | Marks |
|---|---|
| \(C_1\): arcs \(S\to A\), \(S\to B\), \(S\to C\); capacity = \(25+20+22 = 67\) | B1 |
| \(C_2\): arcs \(D\to T\), \(E\to F\), \(C\to F\)... capacity = \(16+21+30 = ...\); \(C_2 = 78\) | B1 |
| Answer | Marks |
|---|---|
| Route: \(S \to A \to E \to F \to T\) (increase by 3) | B1 |
| Answer | Marks |
|---|---|
| Max flow = min cut; identify cut with capacity = new flow value (78) | M1 |
| State cut and its capacity equals the flow, therefore maximal | A1 |
## Question 2:
**(a)**
Saturated arcs: $S \to C$ (22), $S \to B$ (20), $C \to F$ (30), $B \to C$ (8) | B1 B1 | One mark per two correct arcs
**(b)**
Initial flow = **75** | B1 |
**(c)**
$C_1$: arcs $S\to A$, $S\to B$, $S\to C$; capacity = $25+20+22 = 67$ | B1 |
$C_2$: arcs $D\to T$, $E\to F$, $C\to F$... capacity = $16+21+30 = ...$; $C_2 = 78$ | B1 |
**(d)**
Route: $S \to A \to E \to F \to T$ (increase by 3) | B1 |
**(e)**
Max flow = min cut; identify cut with capacity = new flow value (78) | M1 |
State cut and its capacity equals the flow, therefore maximal | A1 |
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{a12f9520-85c0-43f6-a104-2502011d5657-3_780_1155_246_461}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent an initial flow.
\begin{enumerate}[label=(\alph*)]
\item List the saturated arcs.
\item State the value of the initial flow.
\item State the capacities of the cuts $C _ { 1 }$ and $C _ { 2 }$
\item By inspection, find a flow-augmenting route to increase the flow by three units. You must state your route.
\item Prove that the new flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2016 Q2 [8]}}