Edexcel D1 2001 June — Question 6 16 marks

Exam BoardEdexcel
ModuleD1 (Decision Mathematics 1)
Year2001
SessionJune
Marks16
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicNetwork Flows
TypeState maximum flow along specific routes
DifficultyModerate -0.3 This is a standard D1 network flows question requiring application of the max-flow min-cut algorithm with clear scaffolding through parts (a)-(f). While it involves multiple steps, each part guides students through the standard procedure (identifying capacity constraints, finding augmenting paths, proving maximality via cut), making it slightly easier than average A-level difficulty. The labelling procedure is a taught algorithm requiring careful execution rather than novel insight.
Spec7.02a Graphs: vertices (nodes) and arcs (edges)7.02p Networks: weighted graphs, modelling connections7.04f Network problems: choosing appropriate algorithm
6. This question is to be answered on the sheet provided in the answer booklet. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{6d306129-6e1f-424a-b21c-1bf6434ee082-7_602_1255_494_423}
\end{figure} Figure 4 shows a capacitated network. The numbers on each arc indicate the capacity of that arc in appropriate units.
  1. Explain why it is not possible to achieve a flow of 30 through the network from \(S\) to \(T\).
  2. State the maximum flow along
    1. \(S A B T\)
    2. SCET.
  3. Show these flows on Diagram 1 of the answer sheet.
  4. Taking your answer to part (c) as the initial flow pattern, use the labelling procedure to find the maximum flow from \(S\) to \(T\). Show your working on Diagram 2. List each flow-augmenting path you use together with its flow.
  5. Indicate a maximum flow on Diagram 3.
  6. Prove that your flow is maximal.
Question 6:
Part (a):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Finds a cut less than 30, e.g. \(AB, AD, CO, CE = 25\), or \(AB, BD, ET = 24\), giving its valueM1 A1 A1
or a consideration of flow input/output through e.g. \(A\) and \(C\) (3)
Part (b):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
(i) \(SABT = 6\)B1
(ii) \(SCET = 10\)B1 (2)
Part (c):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Correct diagram with flows shownB1 (1)
Part (d):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Correct flow augmentation diagramM1 A1
Further augmentation shown correctlyM1 A1
e.g. \(SADBT = 4\), \(SCDBT = 2\), \(SCDЕТ = 2\), max flow \(= 24\)A1 B1 (6)
Part (e):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Correct final flow diagram shownM1 A1 (2)
Part (f):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Refers to max flow–min cut theorem and the cut through \(AB, BD, ET\) of value \(24\)M1 A1 (2) 
## Question 6:

### Part (a):

| Answer/Working | Marks | Guidance |
|---|---|---|
| Finds a cut less than 30, e.g. $AB, AD, CO, CE = 25$, or $AB, BD, ET = 24$, giving its value | M1 A1 A1 | |
| or a consideration of flow input/output through e.g. $A$ and $C$ | | **(3)** |

### Part (b):

| Answer/Working | Marks | Guidance |
|---|---|---|
| (i) $SABT = 6$ | B1 | |
| (ii) $SCET = 10$ | B1 | **(2)** |

### Part (c):

| Answer/Working | Marks | Guidance |
|---|---|---|
| Correct diagram with flows shown | B1 | **(1)** |

### Part (d):

| Answer/Working | Marks | Guidance |
|---|---|---|
| Correct flow augmentation diagram | M1 A1 | |
| Further augmentation shown correctly | M1 A1 | |
| e.g. $SADBT = 4$, $SCDBT = 2$, $SCDЕТ = 2$, max flow $= 24$ | A1 B1 | **(6)** |

### Part (e):

| Answer/Working | Marks | Guidance |
|---|---|---|
| Correct final flow diagram shown | M1 A1 | **(2)** |

### Part (f):

| Answer/Working | Marks | Guidance |
|---|---|---|
| Refers to max flow–min cut theorem and the cut through $AB, BD, ET$ of value $24$ | M1 A1 | **(2)** |

---
6. This question is to be answered on the sheet provided in the answer booklet.

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 4}
  \includegraphics[alt={},max width=\textwidth]{6d306129-6e1f-424a-b21c-1bf6434ee082-7_602_1255_494_423}
\end{center}
\end{figure}

Figure 4 shows a capacitated network. The numbers on each arc indicate the capacity of that arc in appropriate units.
\begin{enumerate}[label=(\alph*)]
\item Explain why it is not possible to achieve a flow of 30 through the network from $S$ to $T$.
\item State the maximum flow along
\begin{enumerate}[label=(\roman*)]
\item $S A B T$
\item SCET.
\end{enumerate}\item Show these flows on Diagram 1 of the answer sheet.
\item Taking your answer to part (c) as the initial flow pattern, use the labelling procedure to find the maximum flow from $S$ to $T$. Show your working on Diagram 2. List each flow-augmenting path you use together with its flow.
\item Indicate a maximum flow on Diagram 3.
\item Prove that your flow is maximal.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2001 Q6 [16]}}
This paper (7 questions)
View full paper
Q1 5 Q2 7 Q3 7 Q4 11 Q5 12 Q6 16 Q7 17