Edexcel FD2 2022 June — Question 4 9 marks

Exam BoardEdexcel
ModuleFD2 (Further Decision 2)
Year2022
SessionJune
Marks9
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicNetwork Flows
TypeList saturated arcs
DifficultyModerate -0.8 This is a straightforward network flows question testing basic definitions and procedures. Parts (a)-(d) require simple identification from the diagram (saturated arcs, flow value, cut capacities), part (e) asks for a flow-augmenting path by inspection, and part (f) requires applying max-flow min-cut theorem. All are standard textbook exercises with no novel problem-solving required, though the multi-part structure and Further Maths context place it slightly below average difficulty overall.
Spec7.02p Networks: weighted graphs, modelling connections7.04f Network problems: choosing appropriate algorithm
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{cea07472-f93b-4a7b-b362-89fb8c0af4a9-04_931_1312_219_379} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 shows a capacitated, directed network of pipes. The uncircled number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent an initial flow.
  1. List the saturated arcs.
  2. State the value of the initial flow.
  3. Explain why arc FT cannot be full to capacity.
  4. State the capacity of cut \(C _ { 1 }\) and the capacity of cut \(C _ { 2 }\)
  5. By inspection find one flow-augmenting route to increase the flow by three units. You must state your route.
  6. Prove that, once the flow-augmenting route found in part (e) has been applied, the flow is maximal.
Question 4:
Part (a):
AnswerMarks Guidance
Answer/WorkingMark Guidance
AE, BE, BF, BG, DB, DT, SBB1 CAO
Part (b):
AnswerMarks Guidance
Answer/WorkingMark Guidance
\(95\)B1 CAO
Part (c):
AnswerMarks Guidance
Answer/WorkingMark Guidance
Maximum feasible flow into F is 22 (from BF and DF) but maximum feasible flow out of F is 24, therefore FT cannot be full to capacityB1 Correct reasoning; argument must be numerical (minimum comparison of 22 with 24)
Part (d):
AnswerMarks Guidance
Answer/WorkingMark Guidance
\(C_1 (= 33+41+30) = 104\)B1 CAO for \(C_1\)
\(C_2 (= 53+30+14+0+17) = 114\)B1 CAO for \(C_2\)
Part (e):
AnswerMarks Guidance
Answer/WorkingMark Guidance
SABDFTB1 CAO
Part (f):
AnswerMarks Guidance
Answer/WorkingMark Guidance
Use of max-flow min-cut theorem; identification of cut through AE, BE, BG, BF, DF and DTM1 Attempt to find a cut through saturated arcs with source on one side and sink on other; allow cut drawn on diagram
Value of cut \(= 98\), value of flow \(= 98\)A1 Use appropriate process; AE, BE, BG, BF, DF and DT plus value 98 stated correctly
Therefore flow is maximalA1 Must use all four words 'maximum', 'flow', 'minimum', 'cut'; dependent on previous A1 
# Question 4:

## Part (a):

| Answer/Working | Mark | Guidance |
|---|---|---|
| AE, BE, BF, BG, DB, DT, SB | B1 | CAO |

## Part (b):

| Answer/Working | Mark | Guidance |
|---|---|---|
| $95$ | B1 | CAO |

## Part (c):

| Answer/Working | Mark | Guidance |
|---|---|---|
| Maximum feasible flow into F is 22 (from BF and DF) but maximum feasible flow out of F is 24, therefore FT cannot be full to capacity | B1 | Correct reasoning; argument must be numerical (minimum comparison of 22 with 24) |

## Part (d):

| Answer/Working | Mark | Guidance |
|---|---|---|
| $C_1 (= 33+41+30) = 104$ | B1 | CAO for $C_1$ |
| $C_2 (= 53+30+14+0+17) = 114$ | B1 | CAO for $C_2$ |

## Part (e):

| Answer/Working | Mark | Guidance |
|---|---|---|
| SABDFT | B1 | CAO |

## Part (f):

| Answer/Working | Mark | Guidance |
|---|---|---|
| Use of max-flow min-cut theorem; identification of cut through AE, BE, BG, BF, DF and DT | M1 | Attempt to find a cut through saturated arcs with source on one side and sink on other; allow cut drawn on diagram |
| Value of cut $= 98$, value of flow $= 98$ | A1 | Use appropriate process; AE, BE, BG, BF, DF and DT plus value 98 stated correctly |
| Therefore flow is maximal | A1 | Must use all four words 'maximum', 'flow', 'minimum', 'cut'; dependent on previous A1 |

---
4.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{cea07472-f93b-4a7b-b362-89fb8c0af4a9-04_931_1312_219_379}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}

Figure 1 shows a capacitated, directed network of pipes. The uncircled number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent an initial flow.
\begin{enumerate}[label=(\alph*)]
\item List the saturated arcs.
\item State the value of the initial flow.
\item Explain why arc FT cannot be full to capacity.
\item State the capacity of cut $C _ { 1 }$ and the capacity of cut $C _ { 2 }$
\item By inspection find one flow-augmenting route to increase the flow by three units. You must state your route.
\item Prove that, once the flow-augmenting route found in part (e) has been applied, the flow is maximal.
\end{enumerate}

\hfill \mbox{\textit{Edexcel FD2 2022 Q4 [9]}}
This paper (8 questions)
View full paper
Q1 6 Q2 4 Q3 7 Q4 9 Q5 9 Q6 14 Q7 17 Q8 9