Route inspection with parameter

Find the optimal route length expressed in terms of a variable (e.g., x or y), often requiring consideration of different cases or inequalities.

5 questions · Standard +0.9

7.04c Travelling salesman upper bound: nearest neighbour method
Sort by: Default | Easiest first | Hardest first
OCR D1 2011 June Q6
22 marks Challenging +1.8
6 The arcs in the network represent the tracks in a forest. The weights on the arcs represent distances in km . \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-7_535_1267_395_440} Richard wants to walk along every track in the forest. The total weight of the arcs is \(26.7 + x\).
  1. Find, in terms of \(x\), the length of the shortest route that Richard could use to walk along every track, starting at \(A\) and ending at \(G\). Show all of your working.
  2. Now suppose that Richard wants to find the length of the shortest route that he could use to walk along every track, starting and ending at \(A\). Show that for \(x \leqslant 1.8\) this route has length \(( 32.4 + 2 x ) \mathrm { km }\), and for \(x \geqslant 1.8\) it has length \(( 34.2 + x ) \mathrm { km }\). Whenever two tracks join there is an information board for visitors to the forest. Shauna wants to check that the information boards have not been vandalised. She wants to find the length of the shortest possible route that starts and ends at \(A\), passing through every vertex at least once. Consider first the case when \(x\) is less than 3.2.
  3. (a) Apply Prim's algorithm to the network, starting from vertex \(A\), to find a minimum spanning tree. Draw the minimum spanning tree and state its total weight. Explain why the solution to Shauna's problem must be longer than this.
    (b) Use the nearest neighbour strategy, starting from vertex \(A\), and show that it stalls before it has visited every vertex. Now consider the case when \(x\) is greater than 3.2 but less than 4.6.
  4. (a) Draw the minimum spanning tree and state its total weight.
    (b) Use the nearest neighbour strategy, starting from vertex \(A\), to find a route from \(A\) to \(G\) passing through each vertex once. Write down the route obtained and its total weight. Show how a shortcut can give a shorter route from \(A\) to \(G\) passing through each vertex. Hence, explaining your method, find an upper bound for Shauna's problem.
Edexcel D1 2019 January Q6
12 marks Standard +0.8
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e7f89fa1-0afa-4aec-a430-14ec98f487c8-07_608_1468_194_296} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} [The weight of the network is \(20 x + 17\) ]
  1. Explain why it is not possible to draw a network with an odd number of vertices of odd valency. Figure 3 represents a network of 12 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
  2. During rush hour one day \(x = 9\)
    1. Starting at A, use Prim's algorithm to find a minimum spanning tree. You must state the order in which you select the arcs of your tree.
    2. Calculate the weight of the minimum spanning tree. You are now given that \(x > 3\) A route that minimises the total time taken to traverse each road at least once needs to be found. The route must start and finish at the same vertex. The route inspection algorithm is applied to the network in Figure 3 and the time taken for the route is 162 minutes.
  3. Determine the value of \(x\), showing your working clearly.
Edexcel FD1 AS 2023 June Q5
8 marks Challenging +1.2
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{9edb5209-4244-4916-b3ee-d77e395e8cab-06_873_739_178_664} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} [The weight of the network is \(20 x + 3\) ] Figure 4 shows a graph G that contains 8 arcs and 6 vertices.
  1. State the minimum number of arcs that would need to be added to make G into an Eulerian graph.
  2. Explain whether or not the route \(\mathrm { A } - \mathrm { C } - \mathrm { F } - \mathrm { E } - \mathrm { C } - \mathrm { D } - \mathrm { B }\) is an example of a path on G. Figure 4 represents a network of 8 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road. You are given that \(x > 1.6\) A route is required that
    The route inspection algorithm is applied to the network in Figure 4 and the time taken for the route is found to be at most 189 minutes. Given that the inspection route contains two roads that need to be traversed twice,
  3. determine the range of possible values of \(x\), making your reasoning clear.
Edexcel D1 2004 November Q5
10 marks Standard +0.3
  1. find the route the driver should follow, starting and ending at \(F\), to clear all the roads of snow. Give the length of this route. The local authority decides to build a road bridge over the river at \(B\). The snowplough will be able to cross the road bridge.
  2. Reapply the algorithm to find the minimum distance the snowplough will have to travel (ignore the length of the new bridge). \section*{6.} \section*{Figure 3}
    \includegraphics[max width=\textwidth, alt={}]{4bbe6272-3900-42de-b287-599638ca75e4-07_1131_1118_347_502}
    Peter wishes to minimise the time spent driving from his home \(H\), to a campsite at \(G\). Figure 3 shows a number of towns and the time, in minutes, taken to drive between them. The volume of traffic on the roads into \(G\) is variable, and so the length of time taken to drive along these roads is expressed in terms of \(x\), where \(x \geq 0\).
    1. On the diagram in the answer book, use Dijkstra's algorithm to find two routes from \(H\) to \(G\) (one via \(A\) and one via \(B\) ) that minimise the travelling time from \(H\) to \(G\). State the length of each route in terms of \(x\).
    2. Find the range of values of \(x\) for which Peter should follow the route via \(A\). \section*{7.} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-08_1495_1335_322_392}
      \end{figure} The company EXYCEL makes two types of battery, X and Y . Machinery, workforce and predicted sales determine the number of batteries EXYCEL make. The company decides to use a graphical method to find its optimal daily production of X and Y . The constraints are modelled in Figure 4 where $$\begin{aligned} & x = \text { the number (in thousands) of type } \mathrm { X } \text { batteries produced each day, } \\ & y = \text { the number (in thousands) of type } \mathrm { Y } \text { batteries produced each day. } \end{aligned}$$ The profit on each type X battery is 40 p and on each type Y battery is 20 p . The company wishes to maximise its daily profit.
    3. Write this as a linear programming problem, in terms of \(x\) and \(y\), stating the objective function and all the constraints.
    4. Find the optimal number of batteries to be made each day. Show your method clearly.
    5. Find the daily profit, in \(\pounds\), made by EXYCEL.
Edexcel D1 2003 January Q4
9 marks Standard +0.3
\includegraphics{figure_2} The arcs in Fig. 2 represent roads in a town. The weight on each arc gives the time, in minutes, taken to drive along that road. The times taken to drive along \(AB\) and \(DE\) vary depending upon the time of day. A police officer wishes to drive along each road at least once, starting and finishing at \(A\). The journey is to be completed in the least time.
  1. Briefly explain how you know that a route between \(B\) and \(E\) will have to be repeated. [1]
  2. List the possible routes between \(B\) and \(E\). State how long each would take, in terms of \(x\) where appropriate. [2]
  3. Find the range of values that \(x\) must satisfy so that \(DE\) would be one of the repeated arcs. [3] Given that \(x = 7\),
  4. find the total time needed for the police officer to carry out this journey. [3]