D1: Algorithms on graphs IIEdexcel International A Level Maths: Topic test

1. 1
   A park ranger must walk along every path in a park at least once, starting and finishing at the car park $A$. The paths join six junctions $A$, $B$, $C$, $D$, $E$ and $F$. The path lengths, in hundreds of metres, are $AB=5$, $AC=7$, $BC=4$, $BD=6$, $CD=8$, $CE=3$, $DE=5$, $DF=9$ and $EF=4$. There are no other paths.

   (a)

   Which junctions have an odd number of paths meeting at them?

   [1 mark]

   • A$A$ and $F$
   • B$B$ and $E$
   • C$C$ and $D$
   • D$B$, $C$ and $E$

   (b)

   What is the shortest total length of path that must be walked a second time?

   [1 mark]

   • A$4$
   • B$11$
   • C$7$
   • D$15$

   (c)

   Find the length of the shortest route that starts and finishes at $A$ and uses every path at least once.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A mountain rescue base $H$ is joined to three huts $A$, $B$ and $C$ by tracks of length $HA=4$ km, $HB=5$ km and $HC=6$ km. There are no other tracks. A tour starts at $H$, visits every hut and returns to $H$.

   (a)

   Why can the classical travelling salesman problem not be solved on this network?

   [1 mark]

   • AThe triangle inequality is not satisfied
   • BThere are too many vertices for a tour to exist
   • CThe network is directed
   • DNo cycle visits every vertex exactly once

   (b)

   What is the length of the shortest tour in the practical problem?

   [1 mark]

   • A$30$ km
   • B$15$ km
   • C$22$ km
   • D$26$ km

   (c)

   Write down the lengths $AB$, $AC$ and $BC$ in the complete network of shortest distances between the three huts.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A surveyor must visit five weather stations $F$, $G$, $H$, $J$ and $K$, starting and finishing at $F$. Every pair of stations is joined by a direct road. The road lengths in km are $FG=8$, $FH=12$, $FJ=6$, $FK=10$, $GH=7$, $GJ=11$, $GK=9$, $HJ=13$, $HK=5$ and $JK=14$.

   (a)

   Use the nearest neighbour algorithm, starting at $F$, to find an upper bound for the length of the shortest route that visits every station once and returns to $F$. State the route you use.

   [3 marks]

   (b)

   By deleting $F$, find a lower bound for the length of the shortest route that visits every station once and returns to $F$.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   Five harbours $J$, $K$, $L$, $M$ and $N$ are linked by ferry routes. The only direct routes, and their lengths in nautical miles, are $JK=7$, $JL=9$, $JM=12$, $KL=5$, $KN=8$, $LN=6$ and $MN=4$.

   (a)

   An inspector must travel along every route at least once, starting and finishing at $M$. Determine the length of the shortest such journey. You must make your method and all your pairings clear.

   [6 marks]

   (b)

   The network of shortest distances between the harbours has $JK=7$, $JL=9$, $JM=12$, $JN=15$, $KL=5$, $KM=12$, $KN=8$, $LM=10$, $LN=6$ and $MN=4$. A cargo vessel must visit every harbour once, starting and finishing at $J$. (i) Use the nearest neighbour algorithm from $J$ to find an upper bound. (ii) By deleting $J$, find a lower bound.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   A museum security guard must patrol every corridor at least once, starting and finishing at the entrance $T$. The corridors join five junctions $P$, $Q$, $R$, $S$ and $T$. The corridor lengths, in tens of metres, are $PQ=6$, $PR=8$, $QR=5$, $QS=14$, $RS=7$, $RT=10$ and $ST=4$. There are no other corridors.

   (a)

   What is the sum of the degrees of the five junctions?

   [1 mark]

   • A$14$
   • B$7$
   • C$54$
   • D$10$

   (b)

   What is the shortest total length of corridor that must be patrolled a second time?

   [1 mark]

   • A$14$
   • B$21$
   • C$19$
   • D$12$

   (c)

   Find the length of the shortest patrol route, and state which corridors are walked twice.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   A complete network has four towns $U$, $V$, $W$ and $X$. Three of the road lengths, in km, are $UV=5$, $VW=7$ and $UW=14$.

   (a)

   Which statement about the triangle inequality for $U$, $V$ and $W$ is correct?

   [1 mark]

   • AIt is satisfied because $UV$ is the shortest arc
   • BIt is satisfied because $5+14>7$
   • CIt is not satisfied because $UW>UV+VW$
   • DIt cannot be tested without the other lengths

   (b)

   In the practical travelling salesman problem, what is the shortest distance from $U$ to $W$?

   [1 mark]

   • A$14$ km
   • B$12$ km
   • C$7$ km
   • D$26$ km

   (c)

   A driver on a tour is about to use the direct road $UW$. Explain how the driver can shorten the tour, and state the saving.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   Five field stations $R$, $S$, $T$, $U$ and $V$ are joined by a complete network of direct tracks whose lengths, in km, satisfy the triangle inequality: $RS=10$, $RT=6$, $RU=8$, $RV=7$, $ST=16$, $SU=4$, $SV=5$, $TU=12$, $TV=13$ and $UV=9$.

   (a)

   Use Kruskal's algorithm to find a minimum spanning tree for the stations. List the arcs in the order you select them, and state the weight of the tree.

   [3 marks]

   (b)

   Use your tree to find an upper bound for the shortest tour that visits every station once. Then use shortcuts to find a better upper bound, stating the tour you find and its length.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   A bus company's routes join five towns $L$, $M$, $N$, $P$ and $Q$. The only direct routes, and their lengths in km, are $LM=8$, $LN=5$, $LP=11$, $MN=6$, $MQ=9$, $NQ=7$ and $PQ=10$.

   (a)

   An inspector must travel along every route at least once, starting and finishing at $P$. Determine the length of the shortest such journey. You must make your method and all your pairings clear.

   [6 marks]

   (b)

   The network of shortest distances between the towns has $LM=8$, $LN=5$, $LP=11$, $LQ=12$, $MN=6$, $MP=19$, $MQ=9$, $NP=16$, $NQ=7$ and $PQ=10$. A tour $L\to N\to M\to Q\to P\to L$ of length $41$ km is known. (i) By deleting $P$, find a lower bound for the shortest tour. (ii) A planner claims that a tour of length $38$ km exists. Use your answer to comment on the claim, and state the interval that contains the shortest tour.

   [6 marks]

   Total for question 8: 12 marks

End of questions