7.04e Route inspection: Chinese postman, pairing odd nodes

4 Paulo sells vegetables from his van. He drives around the streets of a small village. The network shows the streets in the village. The number on each edge shows the time, in minutes, to drive along that street. Paulo starts from his house located at vertex \(A\) and drives along all the streets at least once before returning to his house. \includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-10_1518_1605_598_198} The total of all the times in the diagram is 79.5 minutes.

1. Find the length of an optimal Chinese postman route around the village, starting and finishing at \(A\). (Shortest routes between vertices may be found by inspection.)
2. For an optimal Chinese postman route, state:
   1. the number of times the vertex \(F\) would occur;
   2. the number of times the vertex \(D\) would occur.
3. Toto is standing for the position of Mayor in the local elections. He intends to travel along all the roads at least once. He can start his journey at any vertex and can finish his journey at any vertex.
   1. Find the length of an optimal route for Toto.
      [0pt]
   2. State the vertices from which Toto could start in order to achieve this optimal route. [3 marks]

5 The network shows the paths mown through a wildflower meadow so that visitors can use these paths to enjoy the flowers. The lengths of the paths are shown in metres. \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-10_1097_1603_413_214} The total length of all the paths is 1400 m .
The mower is kept in a shed at \(A\). The groundskeeper must mow all the paths and return the mower to its shed.

1. Find the length of an optimal Chinese postman route starting and finishing at \(A\).
2. State the number of times that the mower, following the optimal route, will pass through:
   1. \(C\);
   2. \(D\).

4 Amal delivers free advertiser magazines to all the houses in his village. The network shows the roads in his village. The number on each road shows the time, in minutes, that Amal takes to walk along that road. \includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-08_846_1264_445_388}

1. Amal starts his delivery round from his house, at vertex \(A\). He must walk along each road at least once.
   1. Find the length of an optimal Chinese postman route around the village, starting and finishing at Amal's house.
   2. State the number of times that Amal passes his friend Dipak's house, at vertex \(D\).
2. Dipak offers to deliver the magazines while Amal is away on holiday. Dipak must walk along each road at least once. Assume that Dipak takes the same length of time as Amal to walk along each road.
   1. Dipak can start his journey at any vertex and finish his journey at any vertex. Find the length of time for an optimal route for Dipak.
   2. State the vertices at which Dipak could finish, in order to achieve his optimal route.
3. 1. Find the length of time for an optimal route for Dipak, if, instead, he wants to finish at his house, at vertex \(D\), and can start his journey at any other vertex.
   2. State the start vertex.

4 [Figures 4 and 5, printed on the insert, are provided for use in this question.]
The network shows the routes along corridors from the playgrounds \(A\) and \(G\) to the assembly hall in a school. The number on each edge represents the maximum number of pupils that can travel along the corridor in one minute. \includegraphics[max width=\textwidth, alt={}, center]{587bccdf-abd7-4a08-a76e-61374f322e2e-04_1043_1573_559_228}

1. State the vertex that represents the assembly hall.
2. Find the value of the cut shown on the diagram.
3. State the maximum flow along the routes \(A B D\) and \(G E D\).
4. 1. Taking your answers to part (c) as the initial flow, use a labelling procedure on Figure 4 to find the maximum flow through the network.
   2. State the value of the maximum flow and, on Figure 5, illustrate a possible flow along each edge corresponding to this maximum flow.
   3. Verify that your flow is a maximum flow by finding a cut of the same value.
5. On a particular day, there is an obstruction allowing no more than 15 pupils per minute to pass through vertex \(E\). State the maximum number of pupils that can move through the network per minute on this particular day.

6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]
The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{0c40b693-72d3-459c-bbb7-b9584a108b8e-07_713_1456_539_294}

1. 1. Find the value of the cut \(C\).
   2. State what can be deduced about the maximum flow from \(S\) to \(T\).
2. Figure 4, printed on the insert, shows a partially completed diagram for a feasible flow of 20 litres per second from \(S\) to \(T\). Indicate, on Figure 4, the flows along the edges \(M P , P N , Q R\) and \(N R\).
3. 1. Taking your answer from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 5.
   2. Use flow augmentation on Figure 5 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   3. Illustrate the maximum flow on Figure 6.

6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]
The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{f98d4434-458a-4118-92ed-309510d7975a-06_796_1337_518_338}

1. 1. Find the value of the cut \(C\).
   2. Hence state what can be deduced about the maximum flow from \(S\) to \(T\).
2. Figure 4, printed on the insert, shows a partially completed diagram for a feasible flow of 32 litres per second from \(S\) to \(T\). Indicate, on Figure 4, the flows along the edges \(P Q , U Q\) and \(U T\).
3. 1. Taking your feasible flow from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 5.
   2. Use flow augmentation on Figure 5 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   3. Illustrate the maximum flow on Figure 6.

6 [Figures 3, 4 and 5, printed on the insert, are provided for use in this question.]
The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{1bf0d8b7-9f91-437a-bc18-3bfe5ca12223-07_849_1363_518_326}

1. Find the value of the cut \(C\).
2. Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 40 litres per second from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(A E , E F\) and \(F G\).
3. 1. Taking your answer from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 4.
   2. Use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
4. Illustrate the maximum flow on Figure 5.
5. Find a cut with value equal to that of the maximum flow.

6 The diagram shows a nature reserve which has its entrance at \(A\), eight information signs at \(B , C , \ldots , I\), and fifteen grass paths. The length of each grass path is given in metres.
The total length of the grass paths is 1465 metres. \includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-10_812_1192_584_424} To cut the grass, Ashley starts at the entrance and drives a mower along every grass path in the nature reserve. The mower moves at 7 kilometres per hour. 6

1. Find the least possible time that it takes for Ashley to cut the grass on all fifteen paths in the nature reserve and return to the entrance. Fully justify your answer.
   6
2. Brook visits every information sign in the nature reserve to update them, starting and finishing at the entrance. For the eight information signs, the minimum connecting distance of the grass paths is 510 metres. 6 (b)
   1. Determine a lower bound for the distance Brook walks to visit every information sign.
      Fully justify your answer.
      [0pt] [2 marks]
      6
   2. Using the nearest neighbour algorithm starting from the entrance, determine an upper bound for the distance Brook walks to visit every information sign.
      [0pt] [2 marks]
      6
   3. Brook takes one minute to update the information at one information sign. Brook walks on the grass paths at an average speed of 5 kilometres per hour. Ashley and Brook start from the entrance at the same time.
   6 (c) (i) Use your answers from parts (a) and (b) to show that Ashley and Brook will return to the entrance at approximately the same time. Fully justify your answer.
   6 (c) (ii) State an assumption that you have used in part (c)(i). \includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-13_2488_1716_219_153} \(7 \quad\) Ali and Bex play a zero-sum game. The game is represented by the following pay-off matrix for Ali.

   \multirow{2}{*}{}	Bex
   	Strategy	\(\mathbf { B } _ { \mathbf { 1 } }\)	\(\mathbf { B } _ { \mathbf { 2 } }\)	\(\mathbf { B } _ { \mathbf { 3 } }\)
   \multirow{4}{*}{Ali}	\(\mathbf { A } _ { \mathbf { 1 } }\)	2	-1	3
   	\(\mathbf { A } _ { \mathbf { 2 } }\)	-4	-2	2
   	\(\mathbf { A } _ { \mathbf { 3 } }\)	0	1	1
   	\(\mathrm { A } _ { 4 }\)	-3	2	-2

4 A communications company is conducting a feasibility study into the installation of underground television cables between 5 neighbouring districts. The length of the possible pathways for the television cables between each pair of districts, in miles, is shown in the table. The pathways all run alongside cycle tracks. 4

1. Give a possible reason, in context, why some of the table entries are labelled as ***. 4
2. As part of the feasibility study, Sally, an engineer needs to assess each possible pathway between the districts. To do this, Sally decides to travel along every pathway using a bicycle, starting and finishing in the same district. From past experience, Sally knows that she can travel at an average speed of 12 miles per hour on a bicycle. Find the minimum time, in minutes, that it will take Sally to cycle along every pathway.
   [0pt] [4 marks]

6 A council wants to monitor how long cars are being parked for in short-stay parking bays in a town centre. They employ a traffic warden to walk along the streets in the town centre and issue fines to drivers who park for longer than the stated time. The network below shows streets in the town centre which have short-stay parking bays. Each node represents a street corner and the weight of each arc represents the length, in metres, of the street. The short-stay parking bays are positioned along only one side of each street. \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-08_483_1108_733_466} The council assumes that the traffic warden will walk at an average speed of 4.8 kilometres per hour when not issuing fines. 6

1. To monitor all of the parking bays, the traffic warden needs to walk along every street in the town centre at least once, starting and finishing at the same street corner. Find the shortest possible time, to the nearest minute, it can take the traffic warden to monitor all of the parking bays. Fully justify your answer.
   6
2. Explain why the actual time for the traffic warden to walk along every street in the town centre at least once may be different to the value found in part (a).

6 A council wants to grit all of the roads on a housing estate. The network shows the roads on a housing estate. Each node represents a junction between two or more roads and the weight of each arc represents the length, in metres, of the road. \includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-08_1145_1458_539_292} The total length of all of the roads on the housing estate is 9175 metres.
In order to grit all of the roads, the council requires a gritter truck to travel along each road at least once. The gritter truck starts and finishes at the same junction. 6

1. The gritter truck starts gritting the roads at 7:00 pm and moves with an average speed of 5 metres per second during its journey. Find the earliest time for the gritter truck to have gritted each road at least once and arrived back at the junction it started from, giving your answer to the nearest minute. Fully justify your answer.
   [0pt] [6 marks]

   6	Explain how a refinement to the council's requirement, that the gritter truck must start and finish at the same junction, could reduce the time taken to grit all of the roads at least once. [2 marks] \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\)

   The planning involves producing an activity network for the project, which is shown in Figure 1 below. The duration of each activity is given in weeks. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-10_965_1600_559_221}
   \end{figure}

3. \begin{figure}[h] \end{figure} [The weight of the network is \(5 x + 246\) ]

1. Explain why it is not possible to draw a graph with an odd number of vertices of odd valency. Figure 2 represents a network of 14 roads in a town. The expression on each arc gives the time, in minutes, to travel along the corresponding road. Prim's algorithm, starting at A, is applied to the network. The order in which the arcs are selected is \(\mathrm { AD } , \mathrm { DH } , \mathrm { DG } , \mathrm { FG } , \mathrm { EF } , \mathrm { CG } , \mathrm { BD }\). It is given that the order in which the arcs are selected is unique.
2. Using this information, find the smallest possible range of values for \(x\), showing your working clearly. A route that minimises the total time taken to traverse each road at least once is required. The route must start and finish at the same vertex. Given that the time taken to traverse this route is 318 minutes,
3. use an appropriate algorithm to determine the value of \(x\), showing your working clearly.

\includegraphics{figure_1} Figure 1 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along that road. Oliver wishes to travel by road from A to K as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to K. State the quickest route. \hfill [6]

On a particular day Oliver must travel from B to K via A.

1. Find a route of minimal time from B to K that includes A, and state its length. \hfill [2]

Oliver needs to travel along each road to check that it is in good repair. He wishes to minimise the total time required to traverse the network.

1. Use the route inspection algorithm to find the shortest time needed. You must state all combinations of edges that Oliver could repeat, making your method and working clear. \hfill [7]

\includegraphics{figure_1}

1. Using an appropriate algorithm, obtain a suitable route starting and finishing at A. [5 marks]
2. Calculate the total length of this route. [2 marks]

\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]

\includegraphics{figure_2} An engineer needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Fig. 2. The number on each arc represents the length of that road in km. To check all the roads, he needs to travel along each road at least once. He wishes to minimise the total distance travelled. The engineer's office is at \(G\), so he starts and ends his journey at \(G\).

1. Use an appropriate algorithm to find a route for the engineer to follow. State your route and its length. [6]

The engineer lives at \(D\). He believes he can reduce the distance travelled by starting from home and inspecting all the roads on the way to his office at \(G\).

1. State whether the engineer is correct in his belief. If so, calculate how much shorter his new route is. If not, explain why not. [3]

\includegraphics{figure_3} Figure 3 shows a network of paths. The number on each arc gives the distance, in metres, of that path.

1. Use Dijkstra's algorithm to find the shortest distance from \(A\) to \(H\). [5]
2. Solve the route inspection problem for the network shown in Figure 3. You should make your method and working clear. State a shortest route, starting at \(A\), and find its length. [The total weight of the network is 1241] [6]

	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
\(A\)	\(-\)	48	117	92	\(-\)	\(-\)	\(-\)
\(B\)	48	\(-\)	\(-\)	\(-\)	\(-\)	63	55
\(C\)	117	\(-\)	\(-\)	28	\(-\)	\(-\)	85
\(D\)	92	\(-\)	28	\(-\)	58	132	\(-\)
\(E\)	\(-\)	\(-\)	\(-\)	58	\(-\)	124	\(-\)
\(F\)	\(-\)	63	\(-\)	132	124	\(-\)	\(-\)
\(G\)	\(-\)	55	85	\(-\)	\(-\)	\(-\)	\(-\)

The table shows the lengths, in metres, of the paths between seven vertices \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\) in a network N.

1. Use Prim's algorithm, starting at \(A\), to solve the minimum connector problem for this table of distances. You must clearly state the order in which you selected the edges of your tree, and the weight of your final tree. Draw your tree using the vertices given in Diagram 1 in the answer book. [5]
2. Draw N using the vertices given in Diagram 2 in the answer book. [3]
3. Solve the Route Inspection problem for N. You must make your method of working clear. State a shortest route and find its length. (The weight of N is 802.) [7]

1. Explain why a network cannot have an odd number of vertices of odd degree. (2)

\includegraphics{figure_4} Figure 4 shows a network of paths in a public park. The number on each arc represents the length of that path in metres. Hamish needs to walk along each path at least once to check the paths for frost damage starting and finishing at \(A\). He wishes to minimise the total distance he walks.

1. Use the route inspection algorithm to find which paths, if any, need to be traversed twice. (4)
2. Find the length of Hamish's route. [The total weight of the network in Figure 4 is 4180 m.] (1)

(Total 7 marks)

1. Explain why it is impossible to draw a network with exactly three odd vertices. [2]

\includegraphics{figure_1} The Route Inspection problem is solved for the network in Fig. 1 and the length of the route is found to be 100.

1. Determine the value of \(x\), showing your working clearly. [4]

\includegraphics{figure_2}

1. Describe a practical problem that could be modelled using the network in Fig. 2 and solved using the route inspection algorithm. [1]
2. Use the route inspection algorithm to find which paths, if any, need to be traversed twice. [4]
3. State whether your answer to part (b) is unique. Give a reason for your answer. [1]
4. Find the length of the shortest inspection route that traverses each arc at least once and starts and finishes at the same vertex. [1]

Given that it is permitted to start and finish the inspection at two distinct vertices,

1. find which two vertices should be chosen to minimise the length of the route. Give a reason for your answer. [2]

\includegraphics{figure_2} Figure 2 models a network of roads which need to be inspected to assess if they need to be resurfaced. The number on each arc represents the length, in km, of that road. Each road must be traversed at least once and the length of the inspection route must be minimised.

1. Starting and finishing at \(A\), solve this route inspection problem. You should make your method and working clear. State the length of the shortest route. (The weight of the network is 77 km.) [5]

Given that it is now permitted to start and finish the inspection at two distinct vertices,

1. state which two vertices you should choose to minimise the length of the route. Give a reason for your answer. [2]

(Total 7 marks)

\includegraphics{figure_2} Figure 2 shows the network of pipes represented by arcs. The length of each pipe, in kilometres, is shown by the number on each arc. The network is to be inspected for leakages, using the shortest route and starting and finishing at A.

1. Use the route inspection algorithm to find which arcs, if any, need to be traversed twice. [4]
2. State the length of the minimum route. [The total weight of the network is 394 km.] [1]

It is now permitted to start and finish the inspection at two distinct vertices.

1. State, with a reason, which two vertices should be chosen to minimise the length of the new route. [2]

\includegraphics{figure_4} Figure 4 models a network of underground tunnels that have to be inspected. The number on each arc represents the length, in km, of each tunnel. Joe must travel along each tunnel at least once and the length of his inspection route must be minimised. The total weight of the network is 125 km. The inspection route must start and finish at A.

1. Use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. [5]

Given that it is now permitted to start and finish the inspection at two distinct vertices,

1. state which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer. [2]

(Total 7 marks)

\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)