Question 1 - A-Level Maths

Edexcel FD2 2024 June — Question 1 10 marks

Exam Board	Edexcel
Module	FD2 (Further Decision 2)
Year	2024
Session	June
Marks	10
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Network Flows
Type	Vertex restrictions in networks
Difficulty	Standard +0.3 This is a standard network flows question testing basic concepts: conservation of flow at vertices, identifying cut capacity, finding flow-augmenting paths by inspection, and applying max-flow min-cut theorem. The vertex restriction in part (f) is a textbook application. While it requires understanding multiple concepts, each step follows routine procedures with no novel problem-solving required, making it slightly easier than average.
Spec	7.02p Networks: weighted graphs, modelling connections 7.04c Travelling salesman upper bound: nearest neighbour method

1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{931ccf1d-4b02-448c-b492-846b0f42c057-02_696_1347_214_367} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Figure 1 shows a capacitated, directed network of pipes. The numbers in circles represent an initial flow from S to T . The other number on each arc represents the capacity, in litres per second, of the corresponding pipe.

1. State the value of \(x\)
2. State the value of \(y\)
State the value of the initial flow.
State the capacity of cut \(C _ { 1 }\)
Find, by inspection, a flow-augmenting route to increase the flow by four units. You must state your route. The flow-augmenting route from (d) is used to increase the flow from S to T .
Prove that the flow is now maximal. A vertex restriction is now applied so that no more than 12 litres per second can flow through E.
1. Complete Diagram 1 in the answer book to show this restriction.
2. State the value of the maximum flow through the network with this restriction.

Show mark scheme Show mark scheme source

Question 1:

Part (a)

Answer	Marks	Guidance
Answer	Marks	Guidance
(i) \(x = 10\)	B1	AO 1.1b
(ii) \(y = 7\)	B1	AO 1.1b
Total: (2)

Part (b)

Answer	Marks	Guidance
Answer	Marks	Guidance
\(32\)	B1	AO 1.1b
Total: (1)

Part (c)

Answer	Marks	Guidance
Answer	Marks	Guidance
Cut \(C_1 (= 13 + 12 + 12 + 11) = 48\)	B1	AO 1.1b
Total: (1)

Part (d)

Answer	Marks	Guidance
Answer	Marks	Guidance
SCDFET	B1	AO 1.1b
Total: (1)

Part (e)

Answer	Marks	Guidance
Answer	Marks	Guidance
Use of max-flow min-cut theorem	M1	AO 2.1
Identification of cut through AE, DE, DT, EF and FT	A1	AO 3.1a
Value of flow \(= 36\); it follows that flow is maximal	A1	AO 2.2a
Total: (3)

Part (f)

Answer	Marks	Guidance
Answer	Marks	Guidance
Correct diagram showing supersource \(A\) with flow \(2\) to \(E_{IN}\), flow \(12\) from \(E_{IN}\) to \(E_{OUT}\), flow \(13\) to \(D\), flow \(17\) from \(E_{OUT}\) to \(T\), flow \(4\) from \(E_{OUT}\) towards \(F\)	B1	AO 3.3
(ii) Maximum flow \(= 33\)	B1ft	AO 2.2a
Total: (2)

(10 marks total)

Question 1:

Part (a)

Answer	Marks	Guidance
Answer	Mark	Guidance
CAO for \(x\)	B1
CAO for \(y\)	B1

Part (b)

Answer	Marks	Guidance
Answer	Mark	Guidance
CAO	B1

Part (c)

Answer	Marks	Guidance
Answer	Mark	Guidance
CAO	B1

Part (d)

Answer	Marks	Guidance
Answer	Mark	Guidance
CAO	B1

Part (e)

Answer	Marks	Guidance
Answer	Mark	Guidance
Construct argument based on max-flow min-cut theorem (e.g. attempt to find a cut through saturated arcs)	M1	Cut may be drawn or stated in terms of arcs but not as nodes. Note the only saturated arc not in the cut is SB
Use appropriate process of finding a minimum cut: cut + value correct	A1
Must have stated the value of the flow and correct deduction that the flow is maximal	dA1	Must use max flow = min cut all 4 words. Dependent on previous A mark so M1 A0 A1 is not possible

Part (f)

Answer	Marks	Guidance
Answer	Mark	Guidance
Flows into E go to \(E_{IN}\) and flows out of E go from \(E_{OUT}\) and arc of capacity 12 from \(E_{IN}\) to \(E_{OUT}\). All arcs must have the correct arrow and capacity shown. Split node must be labelled as \(E_{IN}\) and \(E_{OUT}\) or \(E_1\) and \(E_2\)	B1
Value of their maximum flow \(- 3\)	B1ft

# Question 1:

## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| (i) $x = 10$ | B1 | AO 1.1b |
| (ii) $y = 7$ | B1 | AO 1.1b |
| **Total: (2)** | | |

## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $32$ | B1 | AO 1.1b |
| **Total: (1)** | | |

## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cut $C_1 (= 13 + 12 + 12 + 11) = 48$ | B1 | AO 1.1b |
| **Total: (1)** | | |

## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| SCDFET | B1 | AO 1.1b |
| **Total: (1)** | | |

## Part (e)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Use of max-flow min-cut theorem | M1 | AO 2.1 |
| Identification of cut through AE, DE, DT, EF and FT | A1 | AO 3.1a |
| Value of flow $= 36$; it follows that flow is maximal | A1 | AO 2.2a |
| **Total: (3)** | | |

## Part (f)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct diagram showing supersource $A$ with flow $2$ to $E_{IN}$, flow $12$ from $E_{IN}$ to $E_{OUT}$, flow $13$ to $D$, flow $17$ from $E_{OUT}$ to $T$, flow $4$ from $E_{OUT}$ towards $F$ | B1 | AO 3.3 |
| (ii) Maximum flow $= 33$ | B1ft | AO 2.2a |
| **Total: (2)** | | |

**(10 marks total)**

# Question 1:

## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| CAO for $x$ | B1 | |
| CAO for $y$ | B1 | |

## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| CAO | B1 | |

## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| CAO | B1 | |

## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| CAO | B1 | |

## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| Construct argument based on max-flow min-cut theorem (e.g. attempt to find a cut through saturated arcs) | M1 | Cut may be drawn or stated in terms of arcs but not as nodes. Note the only saturated arc not in the cut is SB |
| Use appropriate process of finding a minimum cut: cut + value correct | A1 | |
| Must have stated the value of the flow and correct deduction that the flow is maximal | dA1 | Must use max flow = min cut all 4 words. Dependent on previous A mark so M1 A0 A1 is not possible |

## Part (f)
| Answer | Mark | Guidance |
|--------|------|----------|
| Flows into E go to $E_{IN}$ and flows out of E go from $E_{OUT}$ and arc of capacity 12 from $E_{IN}$ to $E_{OUT}$. All arcs must have the correct arrow and capacity shown. Split node must be labelled as $E_{IN}$ and $E_{OUT}$ or $E_1$ and $E_2$ | B1 | |
| Value of their maximum flow $- 3$ | B1ft | |

---

Show LaTeX source

1.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{931ccf1d-4b02-448c-b492-846b0f42c057-02_696_1347_214_367}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}

Figure 1 shows a capacitated, directed network of pipes. The numbers in circles represent an initial flow from S to T . The other number on each arc represents the capacity, in litres per second, of the corresponding pipe.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item State the value of $x$
\item State the value of $y$
\end{enumerate}\item State the value of the initial flow.
\item State the capacity of cut $C _ { 1 }$
\item Find, by inspection, a flow-augmenting route to increase the flow by four units. You must state your route.

The flow-augmenting route from (d) is used to increase the flow from S to T .
\item Prove that the flow is now maximal.

A vertex restriction is now applied so that no more than 12 litres per second can flow through E.
\item \begin{enumerate}[label=(\roman*)]
\item Complete Diagram 1 in the answer book to show this restriction.
\item State the value of the maximum flow through the network with this restriction.
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{Edexcel FD2 2024 Q1 [10]}}

This paper (8 questions)

View full paper

Q1 10 Q2 3 Q3 12 Q4 9 Q5 10 Q6 10 Q7 13 Q8 8