Question 1 - A-Level Maths

Edexcel FD1 2023 June — Question 1 7 marks

Exam Board	Edexcel
Module	FD1 (Further Decision 1)
Year	2023
Session	June
Marks	7
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Graph Theory Fundamentals
Type	Multiple choice identification
Difficulty	Moderate -0.8 This is a straightforward multi-part question testing standard recall and application of basic graph theory definitions (Eulerian/Hamiltonian/planar) and Floyd's algorithm. All parts require direct application of learned procedures with no novel problem-solving or insight. Easier than average A-level maths due to being mostly definitional checks and algorithmic execution.
Spec	7.02g Eulerian graphs: vertex degrees and traversability 7.02h Hamiltonian paths: and cycles 7.02l Planar graphs: planarity, subdivision, contraction 7.04a Shortest path: Dijkstra's algorithm

1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-02_476_727_210_683} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Figure 1 shows the graph G.

State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer.
Write down an example of a Hamiltonian cycle on G.
State whether or not G is planar, justifying your answer.
State the number of arcs that would need to be added to G to make the graph \(\mathrm { K } _ { 5 }\) \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-03_467_716_178_671} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} Direct roads between five villages, A, B, C, D and E, are represented in Figure 2. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the five villages.
For the network represented in Figure 2, complete the initial time matrix in the answer book. The time matrix after four iterations of Floyd's algorithm is shown in Table 1. \begin{table}[h]
A B C D E
A - 10 13 15 5
B 10 - 3 5 4
C 13 3 - 2 7
D 15 5 2 - 7
E 5 4 7 7 -
\captionsetup{labelformat=empty} \caption{Table 1}
\end{table}
Perform the final iteration of Floyd's algorithm that follows from Table 1, showing the time matrix for this iteration.

Show mark scheme Show mark scheme source

Question 1:

Part (a)

Answer	Marks	Guidance
Graph G is neither as there are more than two vertices of odd degree	B1	AO2.4

(1 mark)

Part (b)

Answer	Marks	Guidance
e.g. \(A - B - C - D - E - A\)	B1	AO1.1b

(1 mark)

Part (c)

Answer	Marks	Guidance
G is planar as it can be drawn with no arcs intersecting/crossing each other (with valid planar drawing shown)	B1	AO2.4

(1 mark)

Part (d)

Answer	Marks	Guidance
\(2\)	B1	AO1.1b

(1 mark)

Part (e)

Answer	Marks	Guidance
Distance matrix with entries: \(AB=10,\ AC=15,\ BD=\infty,\ BC=3,\ BE=4,\ CD=2,\ CE=\infty,\ DE=7\)	B1	AO1.1b

(1 mark)

Part (f)

Answer	Marks	Guidance
Updated matrix with boxed values: \(AB=[9],\ AC=[12],\ AD=[12],\ AE=5,\ BC=[9],\ BD=5,\ BE=4,\ CD=2,\ CE=7,\ DE=7\)	M1	AO1.1b
Correct completed matrix with all boxed permanent labels shown	A1	AO1.1b

(2 marks)

Total: 7 marks

Question 1:

Part (a)

Answer	Marks	Guidance
Answer	Mark	Guidance
'Neither' with correct reason	B1	Valid reasons include: G contains more than 2 odd nodes; G contains 4 odd nodes (or stating A, C, D and E are odd); G contains (only) 1 even node; The number of odd degree nodes in G is not 0 or 2. B0 for: G contains odd nodes; G contains at least 2 odd nodes; G contains 4 nodes of degree 3 (not linking to 'odd')

Part (b)

Answer	Marks	Guidance
Answer	Mark	Guidance
CAO - Hamiltonian cycle beginning and ending at same node, including every other node exactly once e.g. AC, CB, BD, DE, EA	B1	Accept if given in terms of arcs

Part (c)

Answer	Marks	Guidance
Answer	Mark	Guidance
Planar + justification	B1	Valid: AC can be moved outside or EB, DB can be moved outside; AC(O), BE(I), BD(I) or vice-versa, accept just AC(O) or BE(O) and BD(O); correct planar drawing. Invalid: Move arc BE (or BD) outside only; vague statement about moving arcs; comments about moving nodes

Part (d)

Answer	Marks	Guidance
Answer	Mark	Guidance
2	B1	CAO (2 only)

Part (e)

Answer	Marks	Guidance
Answer	Mark	Guidance
Completed distance matrix	B1	No blank entries (apart from lead diagonal); must include \(\infty\) in cells AD, CE, DA, EC

Part (f)

Answer	Marks	Guidance
Answer	Mark	Guidance
No change in fifth row and fifth column, at least two values reduced correctly	M1	No blank entries apart from lead diagonal
CAO for final iteration	A1

# Question 1:

## Part (a)
| Graph G is neither as there are more than two vertices of odd degree | B1 | AO2.4 |

**(1 mark)**

## Part (b)
| e.g. $A - B - C - D - E - A$ | B1 | AO1.1b |

**(1 mark)**

## Part (c)
| G is planar as it can be drawn with no arcs intersecting/crossing each other (with valid planar drawing shown) | B1 | AO2.4 |

**(1 mark)**

## Part (d)
| $2$ | B1 | AO1.1b |

**(1 mark)**

## Part (e)
| Distance matrix with entries: $AB=10,\ AC=15,\ BD=\infty,\ BC=3,\ BE=4,\ CD=2,\ CE=\infty,\ DE=7$ | B1 | AO1.1b |

**(1 mark)**

## Part (f)
| Updated matrix with boxed values: $AB=[9],\ AC=[12],\ AD=[12],\ AE=5,\ BC=[9],\ BD=5,\ BE=4,\ CD=2,\ CE=7,\ DE=7$ | M1 | AO1.1b |
| Correct completed matrix with all boxed permanent labels shown | A1 | AO1.1b |

**(2 marks)**

**Total: 7 marks**

# Question 1:

## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| 'Neither' with correct reason | B1 | Valid reasons include: G contains more than 2 odd nodes; G contains 4 odd nodes (or stating A, C, D and E are odd); G contains (only) 1 even node; The number of odd degree nodes in G is not 0 or 2. **B0** for: G contains odd nodes; G contains at least 2 odd nodes; G contains 4 nodes of degree 3 (not linking to 'odd') |

## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| CAO - Hamiltonian cycle beginning and ending at same node, including every other node exactly once e.g. AC, CB, BD, DE, EA | B1 | Accept if given in terms of arcs |

## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Planar + justification | B1 | Valid: AC can be moved outside **or** EB, DB can be moved outside; AC(O), BE(I), BD(I) or vice-versa, accept just AC(O) **or** BE(O) and BD(O); correct planar drawing. Invalid: Move arc BE (or BD) outside only; vague statement about moving arcs; comments about moving nodes |

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

## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| Completed distance matrix | B1 | No blank entries (apart from lead diagonal); must include $\infty$ in cells AD, CE, DA, EC |

## Part (f)
| Answer | Mark | Guidance |
|--------|------|----------|
| No change in fifth row and fifth column, at least two values reduced correctly | M1 | No blank entries apart from lead diagonal |
| CAO for final iteration | A1 | |

---

Show LaTeX source

1.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-02_476_727_210_683}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}

Figure 1 shows the graph G.
\begin{enumerate}[label=(\alph*)]
\item State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer.
\item Write down an example of a Hamiltonian cycle on G.
\item State whether or not G is planar, justifying your answer.
\item State the number of arcs that would need to be added to G to make the graph $\mathrm { K } _ { 5 }$

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-03_467_716_178_671}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}

Direct roads between five villages, A, B, C, D and E, are represented in Figure 2. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the five villages.
\item For the network represented in Figure 2, complete the initial time matrix in the answer book.

The time matrix after four iterations of Floyd's algorithm is shown in Table 1.

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
 & A & B & C & D & E \\
\hline
A & - & 10 & 13 & 15 & 5 \\
\hline
B & 10 & - & 3 & 5 & 4 \\
\hline
C & 13 & 3 & - & 2 & 7 \\
\hline
D & 15 & 5 & 2 & - & 7 \\
\hline
E & 5 & 4 & 7 & 7 & - \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{center}
\end{table}
\item Perform the final iteration of Floyd's algorithm that follows from Table 1, showing the time matrix for this iteration.
\end{enumerate}

\hfill \mbox{\textit{Edexcel FD1 2023 Q1 [7]}}

This paper (7 questions)

View full paper

Q1 7 Q2 7 Q3 8 Q4 12 Q5 13 Q6 9 Q7 19