Effect of adding/removing edge

Determine how adding or removing an edge affects the length of the optimal Chinese postman route, requiring re-analysis of odd vertices.

6 questions · Standard +0.2

7.04c Travelling salesman upper bound: nearest neighbour method
Sort by: Default | Easiest first | Hardest first
Edexcel D1 2017 January Q5
9 marks Standard +0.3
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{8c9bce2c-4156-4bf6-8d02-9e01d6f11948-06_897_1499_239_283} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} [The total weight of the network is 106.7]
Figure 3 models a network of cycle tracks that have to be inspected. The number on each arc represents the length, in km , of the corresponding track. Angela needs to travel along each cycle track at least once and wishes to minimise the length of her inspection route. She must start and finish at A.
  1. Use an appropriate algorithm to find the tracks that will need to be traversed twice. You should make your method and working clear.
  2. Find a route of minimum length, starting and finishing at A . State the length of your route. A new cycle track, AC, is under construction. It will be 15 km long. Angela will have to include this new track in her inspection route.
  3. State the effect this new track will have on the total length of her route. Justify your answer.
Edexcel D1 2013 Specimen Q4
10 marks Standard +0.3
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5fa867a2-0a3d-4f0b-9f9c-15584f2be5c0-05_879_1068_248_497} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} [The total weight of the network is 73.3 km ]
Figure 2 models a network of tunnels that have to be inspected. The number on each arc represents the length, in km , of that tunnel.
Malcolm needs to travel through each tunnel at least once and wishes to minimise the length of his inspection route.
He must start and finish at A .
  1. Use the route inspection algorithm to find the tunnels that will need to be traversed twice. You should make your method and working clear.
  2. Find a route of minimum length, starting and finishing at A . State the length of your route. A new tunnel, CG, is under construction. It will be 10 km long.
    Malcolm will have to include the new tunnel in his inspection route.
  3. What effect will the new tunnel have on the total length of his route? Justify your answer.
Edexcel D1 2012 January Q2
8 marks Standard +0.3
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e02c4a9a-d2ab-489f-b838-9b4d902c4457-3_650_1357_260_354} \captionsetup{labelformat=empty} \caption{Figure 2
[0pt] [The weight of the network is 129 miles]}
\end{figure} Figure 2 models a network of canals. The number on each arc gives the length, in miles, of that canal. Brett needs to travel along each canal to check that it is in good repair. He wishes to minimise the length of his route.
  1. Use the route inspection algorithm to find the length of his route. State the arcs that should be repeated. You should make your method and working clear. A canal between B and F , of length 12 miles, is to be opened and needs to be included in Brett's inspection route.
  2. Determine if the addition of this canal will increase or decrease the length of Brett's minimum route. You must make your reasoning clear.
Edexcel D1 2012 June Q4
12 marks Standard +0.3
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-5_661_1525_292_269} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} \section*{[The total weight of the network is 1436 m ]}
  1. Explain the term valency. Figure 3 models a system of underground pipes. The number on each arc represents the length, in metres, of that pipe. Pressure readings indicate that there is a leak in the system and an electronic device is to be used to inspect the system to locate the leak. The device will start and finish at A and travel along each pipe at least once. The length of this inspection route needs to be minimised.
  2. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You should make your method and working clear.
  3. Find the length of the inspection route. Pipe HI is now found to be blocked; it is sealed and will not be replaced. An inspection route is now required that excludes pipe HI . The length of the inspection route must be minimised.
  4. Find the length of the minimum inspection route excluding HI. Justify your answer.
  5. Given that the device may now start at any vertex and finish at any vertex, find a minimum inspection route, excluding HI.
OCR D1 2006 June Q6
16 marks Standard +0.3
  1. Calculate the shortest distance that the mole must travel if it starts and ends at vertex \(A\).
  2. The pipe connecting \(B\) to \(H\) is removed for repairs. By considering every possible pairing of odd vertices, and showing your working clearly, calculate the shortest distance that the mole must travel to pass along each pipe on this reduced network, starting and finishing at \(A\).
Edexcel D1 2010 June Q4
10 marks Moderate -0.3
\includegraphics{figure_2} [The total weight of the network is 73.3 km] Figure 2 models a network of tunnels that have to be inspected. The number on each arc represents the length, in km, of that tunnel. Malcolm needs to travel through each tunnel at least once and wishes to minimise the length of his inspection route. He must start and finish at A.
  1. Use the route inspection algorithm to find the tunnels that will need to be traversed twice. You should make your method and working clear. [5]
  2. Find a route of minimum length, starting and finishing at A. State the length of your route. [3] A new tunnel, CG, is under construction. It will be 10 km long. Malcolm will have to include the new tunnel in his inspection route.
  3. What effect will the new tunnel have on the total length of his route? Justify your answer. [2]
(Total 10 marks)