7.04e Route inspection: Chinese postman, pairing odd nodes

Norris delivers newspapers to houses on an estate. The network shows the streets on the estate. The number on each edge shows the length of the street, in metres. Norris starts from the newsagents located at vertex \(A\), and he must walk along all the streets at least once before returning to the newsagents. \includegraphics{figure_5} The total length of the streets is 1215 metres.

1. Give a reason why it is not possible to start at \(A\), walk along each street once only, and return to \(A\). [1]
2. Find the length of an optimal Chinese postman route around the estate, starting and finishing at \(A\). [5]
3. For an optimal Chinese postman route, state:
   1. the number of times that the vertex \(F\) would occur; [1]
   2. the number of times that the vertex \(H\) would occur. [1]

The network below shows 13 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. The total of all the times is 384 minutes.

1. Use Dijkstra's algorithm on the network below, starting from \(M\), to find the minimum time to travel from \(M\) to each of the other towns. [7 marks]
2. 1. Find the travelling time of an optimum Chinese postman route around the network, starting and finishing at \(M\). [6 marks]
   2. State the number of times that the vertex \(F\) would appear in a corresponding route. [1 mark]

\includegraphics{figure_4}

\includegraphics{figure_3}

1. Apply Dijkstra's algorithm to the copy of this network in the answer booklet to find the least weight path from A to F. State the route of the path and give its weight. [6]

In the remainder of this question, any least weight paths required may be found without using a formal algorithm.

1. Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. [3]
2. Find the weight of the least weight route that uses every arc at least once, starting at A and ending at F. Explain how you reached your answer. [4]

Answer this question on the insert provided. The vertices in the network below represent the junctions between main roads near Ayton (A). The arcs represent the roads and the weights on the arcs represent distances in miles. \includegraphics{figure_4}

1. On the diagram in the insert, use Dijkstra's algorithm to find the shortest path from A to H. You must show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Write down the route of the shortest path from A to H and give its length in miles. [7]

Simon is a highways surveyor. He needs to check that there are no potholes in any of the roads. He will start and end at Ayton.

1. Which standard network problem does Simon need to solve to find the shortest route that uses every arc? [1]

The total weight of all the arcs is 67.5 miles.

1. Use an appropriate algorithm to find the length of the shortest route that Simon can use. Show all your working. (You may find the lengths of shortest paths between nodes by using your answer to part (i) or by inspection.) [5]

Suppose that, instead, Simon wants to find the shortest route that uses every arc, starting from A and ending at H.

1. Which arcs does Simon need to travel twice? What is the length of the shortest route that he can use? [2]

There is a set of traffic lights at each junction. Simon's colleague Amber needs to check that all the traffic lights are working correctly. She will start and end at the same junction.

1. Show that the nearest neighbour method fails on this network if it is started from A. [1]
2. Apply the nearest neighbour method starting from C to find an upper bound for the distance that Amber must travel. [3]
3. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting node A and all the arcs that are directly joined to node A. Start building your tree at node B. (You do not need to represent the network as a matrix.) Mark the arcs in your tree on the diagram in the insert. Give the order in which nodes are added to your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Amber must travel. [6]

A jeweller is making pendants. Each pendant is made by bending a single, continuous strand of wire. Each pendant has the same design as shown below. \includegraphics{figure_7} The lengths on the diagram are in millimetres. The sum of these lengths is 240 mm As the jeweller does not cut the wire, some sections require a double length of wire.

1. The jeweller makes a pendant by starting and finishing at \(B\) Find the minimum length of the strand of wire that the jeweller needs to make the pendant. Fully justify your answer. [4 marks]
2. The jeweller makes another pendant of the same design. Find the minimum possible length for the strand of wire that the jeweller would need. [2 marks]
3. By considering the differences between the pendants in part (a) and part (b), state one reason why the jeweller may prefer the pendant in part (a). [1 mark]

A council wants to convert all of the street lighting in a village to use LED lighting. The network below shows each street in the village. Each node represents a junction and the weight of each arc represents the length, in metres, of the street. The street lights are only positioned on one side of each street in the village. \includegraphics{figure_6} The total length of all of the streets in the village is 2250 metres. In order to determine the total number of street lights in the village, a council worker is required to walk along every street in the village at least once, starting and finishing at the same junction. The shortest possible distance the council worker can walk in order to determine the total number of street lights in the village is \(x\) metres.

1. Find the value of \(x\) Fully justify your answer. [4 marks]
2. A new council regulation requires that the mean distance along a street between adjacent LED street lights in a village be less than 25 metres. The council worker counted 91 different street lights on their journey around the village. Determine whether or not the village will meet the new council regulation. [2 marks]

A company delivers parcels to houses in a village, using a van. The network below shows the roads in the village. Each node represents a road junction and the weight of each arc represents the length, in miles, of the road between the junctions. \includegraphics{figure_6} The total length of all of the roads in the village is 31.4 miles. On one particular day, the driver is due to make deliveries to at least one house on each road, so the van must travel along each road at least once. However, the driver has forgotten to add fuel to the van and it only has 4.5 litres of fuel to use to make its deliveries. The van uses, on average, 1 litre of fuel to travel 7.8 miles along the roads of this village. Whilst making each delivery, the driver turns off the van's engine so it does not use any fuel. Determine whether the van has enough fuel for the driver to make all of the deliveries to houses on each road of the village, starting and finishing at the same junction. Fully justify your answer. [6 marks]

\includegraphics{figure_1} **Figure 1** [The total weight of the network is \(135 + 4x + 2y\)] The weights on the arcs in Figure 1 represent distances. The weights on the arcs CE and GH are given in terms of \(x\) and \(y\), where \(x\) and \(y\) are positive constants and \(7 < x + y < 20\) There are three paths from A to H that have the same minimum length.

1. Use Dijkstra's algorithm to find \(x\) and \(y\). [7]

An inspection route starting at A and finishing at H is found. The route traverses each arc at least once and is of minimum length.

1. State the arcs that are traversed twice. [1]
2. State the number of times that vertex C appears in the inspection route. [1]
3. Determine the length of the inspection route. [1]