AQA D1 2016 June — Question 7 17 marks

Exam BoardAQA
ModuleD1 (Decision Mathematics 1)
Year2016
SessionJune
Marks17
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicMinimum Spanning Trees
TypeApply Prim's algorithm from vertex
DifficultyModerate -0.5 This is a standard application of Prim's algorithm from a given starting vertex with a small 6-vertex graph. Part (a) requires mechanical execution of a well-defined algorithm with no problem-solving insight. Parts (b)(i)-(iii) involve standard TSP techniques (lower bound by deletion, nearest neighbour heuristic) that are routine D1 content. The question is slightly easier than average A-level because it's purely algorithmic with no conceptual challenges or novel reasoning required.
Spec7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree
7 A company operates a steam railway between six stations. The minimum cost (in euros) of travelling between pairs of stations is shown in the table below.
  1. On Figure 1 below, use Prim's algorithm, starting from \(P\), to find a minimum spanning tree for the graph connecting \(P , Q , R , S , T\) and \(U\). State clearly the order in which you select the vertices and draw your minimum spanning tree. \section*{Question 7 continues on page 20} \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1}
    \(\boldsymbol { P }\)\(\boldsymbol { Q }\)\(\boldsymbol { R }\)\(\boldsymbol { S }\)\(\boldsymbol { T }\)\(\boldsymbol { U }\)
    \(\boldsymbol { P }\)-14711612
    \(\boldsymbol { Q }\)14-810910
    \(\boldsymbol { R }\)78-121315
    \(\boldsymbol { S }\)111012-511
    \(\boldsymbol { T }\)69135-10
    \(\boldsymbol { U }\)1210151110-
    \end{table}
  2. Another station, \(V\), is opened. The minimum costs (in euros) of travelling to and from \(V\) to each of the other stations are added to the table in part (a), as shown in Figure 2(i) below. Further copies of this table are shown in Figure 2(ii). Arjen is on holiday and he plans to visit each station. He intends to board a train at \(V\) and visit all the other stations, once only, before returning to \(V\).
    1. By first removing \(V\), obtain a lower bound for the minimum travelling cost of Arjen's tour. (You may use Figure 2(i) for your working.)
    2. Use the nearest neighbour algorithm twice, starting each time from \(V\), to find two different upper bounds for the minimum cost of Arjen's tour. State, with a reason, which of your two answers gives the better upper bound. (You may use Figure 2(ii) for your working.)
    3. Hence find an optimal tour of the seven stations. Explain how you know that it is optimal. Answer space for question 7(b) \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2(ii)}
      \(\boldsymbol { P }\)\(Q\)\(\boldsymbol { R }\)\(\boldsymbol { S }\)\(T\)\(\boldsymbol { U }\)\(V\)
      \(\boldsymbol { P }\)-1471161215
      \(Q\)14-81091018
      \(\boldsymbol { R }\)78-12131514
      \(\boldsymbol { S }\)111012-51114
      \(T\)69135-1017
      \(\boldsymbol { U }\)1210151110-12
      \(V\)151814141712-
      \end{table}
AnswerMarks Guidance
(a) \(\begin{array}{ccccccc} & P & Q & R & S & T & U \\ \hline P & - & 14 & 7 & 11 & 6 & 12 \\ Q & 14 & - & 8 & 10 & 9 & 10 \\ R & 7 & 8 & - & 12 & 13 & 15 \\ S & 11 & 10 & 12 & - & 5 & 11 \\ T & 6 & 9 & 13 & 5 & - & 10 \\ U & 12 & 10 & 15 & 11 & 10 & - \end{array}\) M1
PT (6) and TS (5) circledA1
PR (7) and RQ (8) circledA1
Order of vertices: P, T, S, R, Q, UB1 Order of adding vertices – either listed (condone PTSRQU) or indicated at the top/side of the matrix (numbers could be 1,…,5 starting at T or 0, … , 5 starting at P). Do NOT allow a list of edges
All correct, including order, with correct values circled and all 'lines' crossed out, either as shown or as 'mirror image'. (Condone omission of 'line' at U)A1
Correct MST with vertices labelled. Either QU or TU but not both (unless if QU and TU both drawn then the need for a choice must be indicated with the diagram)B1 6 marks total
(b)(i) \(36 + \text{or} + \text{(26)}\) with spanning tree connecting P,Q,R,S,T,U or using their answer from (a) or 36 AND 2 labelled edges from V (edges, but not lengths, can be listed or shown in a diagram NOT simply circling values in the table)M1
Correct edges from V with a spanning tree (not necessarily a MST)A1
\(= 62\)B1 3 marks total
(ii) \(V \quad U \quad Q \quad R \quad P \quad T \quad S \quad V (12 \quad 10 \quad 8 \quad 7 \quad 6 \quad 5 \quad 14) (= 62)\)M1 Tour, from V, visiting all other vertices, once only
Correct tour, must be in this orderA1
\(V \quad U \quad T \quad S \quad Q \quad R \quad P \quad V (12 \quad 10 \quad 5 \quad 10 \quad 8 \quad 7 \quad 15) (= 67)\)M1 Second tour, from V, visiting all other vertices, once only
Correct tour, must be in this orderA1
62 and 67B1
62, because 62 < 67E1F 6 marks total
(iii) \(V U Q R P T S V\) or reverseB1 oe This tour starting from any vertex e.g. \(U Q R P T S V U\), \(S T P R Q V S\)
Tour/upper bound has the same length (62) as the lower bound (therefore optimal) or As lower bound gives a tour, therefore optimalE1 2 marks total
Total: 17 marks
**(a)** $\begin{array}{c|cccccc} & P & Q & R & S & T & U \\ \hline P & - & 14 & 7 & 11 & 6 & 12 \\ Q & 14 & - & 8 & 10 & 9 & 10 \\ R & 7 & 8 & - & 12 & 13 & 15 \\ S & 11 & 10 & 12 & - & 5 & 11 \\ T & 6 & 9 & 13 & 5 & - & 10 \\ U & 12 & 10 & 15 & 11 & 10 & - \end{array}$ | M1 | SCA; Use of matrix form, 4+ numbers circled and 4+ parallel 'lines' deleted
PT (6) and TS (5) circled | A1 |
PR (7) and RQ (8) circled | A1 |
Order of vertices: P, T, S, R, Q, U | B1 | Order of adding vertices – either listed (condone PTSRQU) or indicated at the top/side of the matrix (numbers could be 1,…,5 starting at T or 0, … , 5 starting at P). Do NOT allow a list of edges
All correct, including order, with correct values circled and all 'lines' crossed out, either as shown or as 'mirror image'. (Condone omission of 'line' at U) | A1 |
Correct MST with vertices labelled. Either QU or TU but not both (unless if QU and TU both drawn then the need for a choice must be indicated with the diagram) | B1 | 6 marks total

**(b)(i)** $36 + \text{or} + \text{(26)}$ with spanning tree connecting P,Q,R,S,T,U or using their answer from (a) or 36 AND 2 labelled edges from V (edges, but not lengths, can be listed or shown in a diagram NOT simply circling values in the table) | M1 |
Correct edges from V with a spanning tree (not necessarily a MST) | A1 |
$= 62$ | B1 | 3 marks total

**(ii)** $V \quad U \quad Q \quad R \quad P \quad T \quad S \quad V (12 \quad 10 \quad 8 \quad 7 \quad 6 \quad 5 \quad 14) (= 62)$ | M1 | Tour, from V, visiting all other vertices, once only
Correct tour, must be in this order | A1 |
$V \quad U \quad T \quad S \quad Q \quad R \quad P \quad V (12 \quad 10 \quad 5 \quad 10 \quad 8 \quad 7 \quad 15) (= 67)$ | M1 | Second tour, from V, visiting all other vertices, once only
Correct tour, must be in this order | A1 |
62 and 67 | B1 |
62, because 62 < 67 | E1F | 6 marks total | oe; If both UB values the same then E0

**(iii)** $V U Q R P T S V$ or reverse | B1 | oe This tour starting from any vertex e.g. $U Q R P T S V U$, $S T P R Q V S$
Tour/upper bound has the same length (62) as the lower bound (therefore optimal) or As lower bound gives a tour, therefore optimal | E1 | 2 marks total | Must come from correct 62 from bii and LB of 62 in bi. Their (bi) must be correct

**Total: 17 marks**

---
7 A company operates a steam railway between six stations. The minimum cost (in euros) of travelling between pairs of stations is shown in the table below.
\begin{enumerate}[label=(\alph*)]
\item On Figure 1 below, use Prim's algorithm, starting from $P$, to find a minimum spanning tree for the graph connecting $P , Q , R , S , T$ and $U$. State clearly the order in which you select the vertices and draw your minimum spanning tree.

\section*{Question 7 continues on page 20}
\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
 & $\boldsymbol { P }$ & $\boldsymbol { Q }$ & $\boldsymbol { R }$ & $\boldsymbol { S }$ & $\boldsymbol { T }$ & $\boldsymbol { U }$ \\
\hline
$\boldsymbol { P }$ & - & 14 & 7 & 11 & 6 & 12 \\
\hline
$\boldsymbol { Q }$ & 14 & - & 8 & 10 & 9 & 10 \\
\hline
$\boldsymbol { R }$ & 7 & 8 & - & 12 & 13 & 15 \\
\hline
$\boldsymbol { S }$ & 11 & 10 & 12 & - & 5 & 11 \\
\hline
$\boldsymbol { T }$ & 6 & 9 & 13 & 5 & - & 10 \\
\hline
$\boldsymbol { U }$ & 12 & 10 & 15 & 11 & 10 & - \\
\hline
\end{tabular}
\end{center}
\end{table}
\item Another station, $V$, is opened. The minimum costs (in euros) of travelling to and from $V$ to each of the other stations are added to the table in part (a), as shown in Figure 2(i) below. Further copies of this table are shown in Figure 2(ii).

Arjen is on holiday and he plans to visit each station. He intends to board a train at $V$ and visit all the other stations, once only, before returning to $V$.
\begin{enumerate}[label=(\roman*)]
\item By first removing $V$, obtain a lower bound for the minimum travelling cost of Arjen's tour. (You may use Figure 2(i) for your working.)
\item Use the nearest neighbour algorithm twice, starting each time from $V$, to find two different upper bounds for the minimum cost of Arjen's tour. State, with a reason, which of your two answers gives the better upper bound. (You may use Figure 2(ii) for your working.)
\item Hence find an optimal tour of the seven stations. Explain how you know that it is optimal.

Answer space for question 7(b)

\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 2(ii)}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
 & $\boldsymbol { P }$ & $Q$ & $\boldsymbol { R }$ & $\boldsymbol { S }$ & $T$ & $\boldsymbol { U }$ & $V$ \\
\hline
$\boldsymbol { P }$ & - & 14 & 7 & 11 & 6 & 12 & 15 \\
\hline
$Q$ & 14 & - & 8 & 10 & 9 & 10 & 18 \\
\hline
$\boldsymbol { R }$ & 7 & 8 & - & 12 & 13 & 15 & 14 \\
\hline
$\boldsymbol { S }$ & 11 & 10 & 12 & - & 5 & 11 & 14 \\
\hline
$T$ & 6 & 9 & 13 & 5 & - & 10 & 17 \\
\hline
$\boldsymbol { U }$ & 12 & 10 & 15 & 11 & 10 & - & 12 \\
\hline
$V$ & 15 & 18 & 14 & 14 & 17 & 12 & - \\
\hline
\end{tabular}
\end{center}
\end{table}
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{AQA D1 2016 Q7 [17]}}
This paper (8 questions)
View full paper
Q1 5 Q2 7 Q3 7 Q4 11 Q5 8 Q6 7 Q7 17 Q8 13