MST Method for Upper Bound

A question is this type if and only if it asks the student to find a minimum spanning tree and use it (with or without shortcuts) to determine an upper bound for the travelling salesman problem.

5 questions · Moderate -0.2

7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04d Travelling salesman lower bound: using minimum spanning tree
Sort by: Default | Easiest first | Hardest first
Edexcel D2 Q4
11 marks Moderate -0.3
4. This question should be answered on the sheet provided. A travelling salesman problem relates to the network represented by the following table of distances in kilometres. You may assume that the network satisfies the triangle inequality.
AB\(C\)D\(E\)\(F\)G\(H\)
A-85593147527441
B85-1047351684355
C59104-5462886145
D317354-40596578
E47516240-567168
\(F\)5268885956-5349
G744361657153-63
H41554578684963-
Showing your method clearly, use
  1. the nearest neighbour algorithm, beginning with \(A\),
  2. Prim's algorithm with \(H\) deleted,
    to show that the minimum distance travelled, \(d \mathrm {~km}\), satisfies the inequality \(357 \leq d \leq 371\).
    (11 marks)
Edexcel D2 Q6
14 marks Standard +0.3
6. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4e50371b-0c1c-4b4e-b21d-60858ae160df-5_664_1029_335_440} \captionsetup{labelformat=empty} \caption{Fig. 3}
\end{figure} The network in Figure 3 shows the distances, in miles, between a newspaper distributor based at area \(A\), and five areas, \(B , C , D , E\), and \(F\), to which the distributor must deliver newspapers. Each morning a delivery van has to set out from \(A\) and visit each of these areas before again returning to \(A\), and the driver wishes to keep the total mileage to a minimum.
  1. Draw a complete network showing the shortest distances between the six areas.
    (3 marks)
  2. Obtain a minimum spanning tree for the complete network and hence find an upper bound for the length of the driver's route.
    (5 marks)
  3. Improve this upper bound to find an upper bound of less than 55 miles.
  4. By deleting \(A\), find a lower bound for the total length of the route.
Edexcel D2 Q6
17 marks Standard +0.8
6. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{073926c5-03cc-41d4-82bf-315740ead663-6_672_984_322_431} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} A band is going on tour to play gigs in six towns, including their home town, \(A\). The network in Figure 1 shows the distances, in miles, between the various towns. The band must begin and end their tour at \(A\) and visit each of the other towns once, and they wish to keep the total distance travelled as small as possible.
  1. By inspection, draw a complete network showing the shortest distances between the towns.
  2. Use your complete network and the nearest neighbour algorithm, starting at \(A\), to find an upper bound for the total distance travelled.
    1. Use your complete network to obtain and draw a minimum spanning tree and hence obtain another upper bound for the total distance travelled.
    2. Improve this upper bound using two shortcuts to find an upper bound below 225 miles.
  4. By deleting \(A\), find a lower bound for the total distance travelled.
  5. State an interval of as small a width as possible within which \(d\), the minimum distance travelled, in miles, must lie. \section*{Please hand this sheet in for marking}
    StagePrevious tournamentCurrent tournament
    \multirow[t]{3}{*}{1}G
    J
    K
    L
    \(H\)
    J
    K
    L
    I
    J
    K
    L
    \multirow[t]{3}{*}{2}D
    G
    H
    I
    \(E\)
    G
    H
    I
    \(F\)
    G
    H
    I
    \multirow[t]{3}{*}{3}A
    D
    E
    F
    \(B\)
    D
    E
    F
    C
    D
    E
    F
    4None
    A
    B
    C
    \section*{Please hand this sheet in for marking}
    1. \includegraphics[max width=\textwidth, alt={}, center]{073926c5-03cc-41d4-82bf-315740ead663-8_684_992_461_427}
    2. \section*{Sheet for answering question 6 (cont.)}
      2. \(\_\_\_\_\)
    5. \(\_\_\_\_\)
Edexcel D2 2017 June Q1
7 marks Moderate -0.8
1.
ABCDEF
A-8375826997
B83-9410377109
C7594-97120115
D8210397-105125
E6977120105-88
F9710911512588-
The table above shows the least distances, in km , between six towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .
  1. Starting at A, and making your working clear, find an initial upper bound for the travelling salesperson problem for this network, using
    1. the minimum spanning tree method,
    2. the nearest neighbour algorithm.
      (5) By deleting A, and all of its arcs, a lower bound for the travelling salesperson problem for this network is found to be 500 km . By deleting B, and all of its arcs, the corresponding lower bound is found to be 474 km .
  2. Using the results from (a) and the given lower bounds, write down the smallest interval that you can be confident contains the solution to the travelling salesperson problem for this network.
    (2)
Edexcel D2 Q1
6 marks Moderate -0.8
This question should be answered on the sheet provided. The table below shows the distances in miles between five villages. Jane lives in village A and is about to take her daughter's friends home to villages B, C, D and E. She will begin and end her journey at A and wishes to travel the minimum distance possible.
ABCDE
A\(-\)4782
B4\(-\)156
C71\(-\)27
D852\(-\)3
E2673\(-\)
  1. Obtain a minimum spanning tree for the network and hence find an upper bound for the length of Jane's journey. [4 marks]
  2. Using a shortcut, improve this upper bound to find an upper bound of less than 15 miles. [2 marks]