| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Complete labelling procedure initialization |
| Difficulty | Moderate -0.8 Part (b) asks only to complete a partially-worked labelling procedure by filling in four specific values, which is routine execution of a standard algorithm with no problem-solving required. This is easier than average A-level maths questions that typically require multi-step reasoning or conceptual understanding. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A cut divides the vertices into two sets, one set containing the source(s) and the other the sink(s) | B2,1,0 | Close, bod, probably 2 out of three points; good complete answer, 2 'sets'; source and sink separated; vertices |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Diagram with two numbers on each arc | M1, A1 | cao; two numbers on each arc |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. \(SBACEGT - 9\) | M1, A1 | 1 correct route and a flow value stated; any flow \(>9\) gets M0 |
| \(SBADGEHT - 1\) | A1 | 1 valid route with valid flow |
| \(SBFEHT - 3\) | A1 | 2 distinct valid routes with valid flows found to \(>3\); all routes and flows found to 13 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Consistent flow pattern diagram shown | M1, A1 | Consistent flow pattern \(>55\); cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Flow value \(67\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Max flow–min cut theorem; cut through \(AD, AC, BC, EF, FH\) | M1, A1 | Depends flow of 67, 3 out of 4 words in theorem, cut attempted; valid cut |
# Question 6:
## Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| A cut divides the vertices into two sets, one set containing the source(s) and the other the sink(s) | B2,1,0 | Close, bod, probably 2 out of three points; good complete answer, 2 'sets'; source and sink separated; vertices |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Diagram with two numbers on each arc | M1, A1 | cao; two numbers on each arc |
## Part (c):
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. $SBACEGT - 9$ | M1, A1 | 1 correct route and a flow value stated; any flow $>9$ gets M0 |
| $SBADGEHT - 1$ | A1 | 1 valid route with valid flow |
| $SBFEHT - 3$ | A1 | 2 distinct valid routes with valid flows found to $>3$; all routes and flows found to 13 |
## Part (d):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Consistent flow pattern diagram shown | M1, A1 | Consistent flow pattern $>55$; cao |
## Part (e):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Flow value $67$ | B1 | cao |
## Part (f):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Max flow–min cut theorem; cut through $AD, AC, BC, EF, FH$ | M1, A1 | Depends flow of 67, 3 out of 4 words in theorem, cut attempted; valid cut |6. (a) Define the term 'cut' as it applies to a directed network.\\
(2)
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-7_659_1367_376_349}
\captionsetup{labelformat=empty}
\caption{Figure 6}
\end{center}
\end{figure}
Figure 6 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.\\
(b) Complete the labelling procedure on Diagram 2 in your answer book by entering values along CE, EG, HT and GT.\\
(c) Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.\\
(d) Show a maximal flow pattern on Diagram 3 in your answer book.\\
(e) State the value of the maximum flow through the network.\\
(f) Prove that your flow is maximal.\\
\hfill \mbox{\textit{Edexcel D1 2008 Q6 [13]}}