| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Moderate -0.3 This is a standard textbook application of the labelling procedure (max flow-min cut algorithm) with straightforward initialization. Part (a) requires simple addition of flows, (b) is routine labelling of excess capacities, (c-d) follow the standard algorithm mechanically, and (e) requires stating a minimum cut. While multi-part with 11 marks total, each step is algorithmic with no novel problem-solving required, making it slightly easier than average A-level difficulty. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| (a) Initial flow = 46 | B1 | 1 |
| (b) Flow augmenting paths with capacities marked | M1 A1 | 2 |
| Example: SBDET – flow 3, SBCFT – flow 2 | ||
| (c) E.g. SBDET – flow 3, SBCFT – flow 2 | 1M1 1A1 2M1 2A1 | 4 |
| (d) Maximum flow diagram with flow values | M1 A1 | 2 |
| Cut with value 51 (through DT, DE, BE, BF, CB and SC) | ||
| (e) (The value of the flow is 51). The cut through DT, DE, BE, BF, CB and SC has value 51. By max flow-min cut theorem flow is maximal | M1 A1cso | 2 |
| Total 11 |
| Answer/Working | Marks | Guidance |
|---|---|---|
| **(a)** Initial flow = 46 | B1 | **1** |
| **(b)** Flow augmenting paths with capacities marked | M1 A1 | **2** |
| Example: SBDET – flow 3, SBCFT – flow 2 | | |
| **(c)** E.g. SBDET – flow 3, SBCFT – flow 2 | 1M1 1A1 2M1 2A1 | **4** |
| **(d)** Maximum flow diagram with flow values | M1 A1 | **2** |
| Cut with value 51 (through DT, DE, BE, BF, CB and SC) | | |
| **(e)** (The value of the flow is 51). The cut through DT, DE, BE, BF, CB and SC has value 51. By max flow-min cut theorem flow is maximal | M1 A1cso | **2** |
| | | **Total 11** |
**Notes for question 6:**
- a1B1: CAO
- b1M1: Two numbers on each arc
- b1A1: CAO do give bod since they might well cross these number out.
- c1M1: One valid flow augmenting route found and a valid value stated.
- c1A1: Flow increased by at least 2
- c2M1: A second correct flow route and value correct.
- c2A1: CSO Flow increased by 5 and no more.
- d1M1: Consistent flow pattern ≥48. One number only per arc. No unnumbered arcs.
- e1M1: CAO must follow from their routes.
- e1A1CSO: For (d) and (e) Cut and (d) correct, Cut may be drawn. Must refer to max flow-min cut theorem flow is maximal. Must refer to max flow-min cut theorem. (Three words out of four.)
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{d0bede44-05dc-4edd-8436-cf5eea710d1a-7_1120_1691_260_187}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.
\begin{enumerate}[label=(\alph*)]
\item State the value of the initial flow.\\
(1)
\item Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along $\mathrm { SB } , \mathrm { BD } , \mathrm { CF }$ and FT .\\
(2)
\item Hence use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.\\
(4)
\item Draw a maximal flow pattern on Diagram 2 in your answer book.\\
(2)
\item Prove that your flow is maximal.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2012 Q6 [11]}}