Calculate Specific Tour Length

A question is this type if and only if it asks the student to calculate the total length or time of a specified tour given as a sequence of vertices.

5 questions · Moderate -0.6

7.04d Travelling salesman lower bound: using minimum spanning tree
Sort by: Default | Easiest first | Hardest first
AQA D1 2005 January Q7
16 marks Moderate -0.8
7 Rob delivers bread to six shops \(A , B , C , D , E\) and \(F\). Each day, Rob starts at shop \(A\), travels to each of the other shops before returning to shop \(A\). The table shows the distances, in miles, between the shops.
\(\boldsymbol { A }\)\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { D }\)\(\boldsymbol { E }\)\(\boldsymbol { F }\)
\(\boldsymbol { A }\)-869127
\(\boldsymbol { B }\)8-1014138
\(\boldsymbol { C }\)610-71610
\(\boldsymbol { D }\)9147-155
\(\boldsymbol { E }\)12131615-11
\(\boldsymbol { F }\)7810511-
    1. Find the length of the tour \(A B C D E F A\).
    2. Find the length of the tour obtained by using the nearest neighbour algorithm starting from \(A\).
  1. By deleting \(A\), find a lower bound for the length of a minimum tour.
  2. By deleting \(F\), another lower bound of 45 miles is obtained for the length of a minimum tour. The length of a minimum tour is \(T\) miles. Write down the smallest interval for \(T\) which can be obtained from your answers to parts (a) and (b), and the information given in this part.
    (3 marks)
OCR FD1 AS 2017 December Q4
8 marks Moderate -0.3
4 Tom is planning a day out walking. He wants to start from his sister's house ( S ), then visit three places \(\mathrm { A } , \mathrm { B }\) and C (once each, in any order) and then finish at his own house (T).
  1. Complete the graph in the Printed Answer Booklet showing all possible arcs that could be used to plan Tom's walk. Tom needs to keep the total distance that he walks to a minimum, so he weights his graph.
  2. (a) Why would finding the shortest path from S to T , on Tom's network, not necessarily solve Tom's problem?
    (b) Why would finding a minimum spanning tree, on Tom's network, not necessarily solve Tom's problem? The distance matrix below shows the direct distances, in km , between places.
    SABCT
    n S03254
    nA3022.52
    nB2203.22.5
    n52.53.202
    \cline { 2 - 6 } T422.520
    \cline { 2 - 6 }
    \cline { 2 - 6 }
  3. - Use an appropriate algorithm to find a minimum spanning tree for Tom's network.
AQA D1 2005 June Q6
13 marks Moderate -0.5
6 Mia is on holiday in Venice. There are five places she wishes to visit: Rialto \(( R )\), St Mark's \(( S )\), Murano ( \(M\) ), Burano ( \(B\) ) and Lido ( \(L\) ). Boat services connect the five places. The table shows the times, in minutes, to travel between the places. Mia wishes to keep her travelling time to a minimum.
Rialto ( \(R\) )St Mark's ( \(S\) )Murano ( \(M\) )Burano (B)Lido (L)
Rialto ( \(R\) )-15557525
St Mark's ( \(S\) )15-906020
Murano ( \(M\) )5590-2580
Burano (B)756025-50
Lido ( \(L\) )25208050-
    1. Find the length of the tour \(S R M B L S\).
    2. Find the length of the tour using the nearest neighbour algorithm starting from \(S\).
  1. By deleting Burano ( \(B\) ), find a lower bound for the length of the minimum tour.
  2. Sketch a network showing the edges that give the lower bound found in part (b) and comment on its significance.
AQA D1 2011 January Q7
10 marks Moderate -0.8
Fred delivers bread to five shops, \(A\), \(B\), \(C\), \(D\) and \(E\). Fred starts his deliveries at shop \(B\), and travels to each of the other shops once before returning to shop \(B\). Fred wishes to keep his travelling time to a minimum. The table shows the travelling times, in minutes, between the shops. $$\begin{array}{c|ccccc} & A & B & C & D & E \\ \hline A & - & 3 & 11 & 15 & 5 \\ B & 3 & - & 18 & 12 & 4 \\ C & 11 & 18 & - & 5 & 16 \\ D & 15 & 12 & 5 & - & 10 \\ E & 5 & 4 & 16 & 10 & - \end{array}$$
  1. Find the travelling time for the tour \(BACDEB\). [1]
  2. Use the nearest neighbour algorithm, starting at \(B\), to find another upper bound for the travelling time for Fred's tour. [3]
  3. By deleting \(C\), find a lower bound for the travelling time for Fred's tour. [4]
  4. Sketch a network showing the edges that give you the lower bound in part (c) and comment on its significance. [2]
Edexcel D1 2022 January Q7
Moderate -0.8
7. \section*{Question 7 continued} \section*{Question 7 continued} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{765ea64e-d4b8-4f0f-9a43-2619f9db0c18-19_2109_1335_299_372} \captionsetup{labelformat=empty} \caption{Diagram 1}
\end{figure} \section*{Question 7 continued} \section*{Pearson Edexcel International Advanced Level} Time 1 hour 30 minutes \section*{Paper reference WDM11/01} \section*{Mathematics} \section*{You must have:} Decision Mathematics Answer Book (enclosed), calculator Candidates may use any calculator permitted by Pearson regulations. Calculators must not have the facility for symbolic algebra manipulation, differentiation and integration, or have retrievable mathematical formulae stored in them. \section*{Instructions}
  • Use black ink or ball-point pen.
  • If pencil is used for diagrams/sketches/graphs it must be dark (HB or B).
  • Write your answers for this paper in the Decision Mathematics answer book provided.
  • Fill in the boxes at the top of the answer book with your name, centre number and candidate number.
  • Do not return the question paper with the answer book.
  • Answer all questions and ensure that your answers to parts of questions are clearly labelled.
  • Answer the questions in the spaces provided
  • there may be more space than you need.
  • You should show sufficient working to make your methods clear. Answers without working may not gain full credit.
  • Inexact answers should be given to three significant figures unless otherwise stated.
\section*{Information}
  • There are 7 questions in this question paper. The total mark for this paper is 75.
  • The marks for each question are shown in brackets
  • use this as a guide as to how much time to spend on each question.
\section*{Advice}
  • Read each question carefully before you start to answer it.
  • Try to answer every question.
  • Check your answers if you have time at the end.
  • If you change your mind about an answer, cross it out and put your new answer and any working underneath.
\section*{Write your answers in the D1 answer book for this paper.}