| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2015 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Explain capacity/flow constraints |
| Difficulty | Standard +0.3 This is a straightforward network flows question requiring basic understanding of cuts, max-flow min-cut theorem, and flow conservation. Parts (a)-(c) involve simple arithmetic and recall of definitions, while (d) requires basic logical reasoning about flow conservation at a node. Part (e) involves constructing a flow pattern with given constraints but explicitly states no labelling procedure is needed, making it mechanical rather than requiring algorithmic problem-solving. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(C_1 = 45\) | B1 | CAO for \(C_1(45)\) |
| \(C_2 = 73\) | B1 | CAO for \(C_2(73)\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(45\) | B1ft | 45 or the value of their smallest cut from (a) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(20\) | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| The maximum capacity of arcs flowing into G is 21, so both GF and GT cannot be full to capacity as the capacity of arcs flowing out of G is 26 | B1 | CAO – argument must be numerical in nature (minimum accept \(26 > 21\)) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Consistent flow pattern shown in diagram (arc EC must be 4, AD \(= 10\), DF \(= 3\); all other arcs may have over-capacitated values) | M1, A1 | Consistent flow pattern – check each node, must have exactly 1 number per arc |
# Question 4:
## Part (a)
| Answer/Working | Marks | Guidance |
|---|---|---|
| $C_1 = 45$ | B1 | CAO for $C_1(45)$ |
| $C_2 = 73$ | B1 | CAO for $C_2(73)$ |
## Part (b)
| Answer/Working | Marks | Guidance |
|---|---|---|
| $45$ | B1ft | 45 or the value of their smallest cut from (a) |
## Part (c)
| Answer/Working | Marks | Guidance |
|---|---|---|
| $20$ | B1 | CAO |
## Part (d)
| Answer/Working | Marks | Guidance |
|---|---|---|
| The maximum capacity of arcs flowing into G is 21, so both GF and GT cannot be full to capacity as the capacity of arcs flowing out of G is 26 | B1 | CAO – argument must be numerical in nature (minimum accept $26 > 21$) |
## Part (e)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Consistent flow pattern shown in diagram (arc EC must be 4, AD $= 10$, DF $= 3$; all other arcs may have over-capacitated values) | M1, A1 | Consistent flow pattern – check each node, must have exactly 1 number per arc |4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{57c75bde-811a-421c-899a-3689bdba6724-5_837_1217_233_424}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. Two cuts $\mathrm { C } _ { 1 }$ and $\mathrm { C } _ { 2 }$ are shown.
\begin{enumerate}[label=(\alph*)]
\item Find the capacity of each of the two cuts.
Given that one of these two cuts is a minimum cut,
\item write down the maximum possible flow through the network.
Given that the network now has a maximal flow from S to T ,
\item determine the flow along arc SB.
\item Explain why arcs GF and GT cannot both be saturated.
Given that arcs EC, AD and DF are saturated and that there is no flow along arc GF,
\item determine a maximum flow pattern for this network and draw it on Diagram 1 in the answer book. You do not need to use the labelling procedure to determine the maximum flow.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2015 Q4 [7]}}