Decision Mathematics 1: Algorithms on graphs IIEdexcel A-Level Further Maths: Topic test

1. 1
   A road network has five junctions $P$, $Q$, $R$, $S$ and $T$. The road lengths in km are $PQ=6$, $PR=4$, $QR=5$, $QS=7$, $RS=3$, $RT=8$ and $ST=5$. An inspector must travel along every road and return to the start.

   (a)

   Which vertices have odd degree?

   [1 mark]

   • A$P$ and $T$
   • B$Q$ and $S$
   • C$R$ and $S$
   • D$Q$ and $R$

   (b)

   What is the length of the shortest route that travels along every road and returns to its starting vertex?

   [1 mark]

   • A$38$ km
   • B$46$ km
   • C$52$ km
   • D$45$ km

   (c)

   The road $RT$ is closed. Find the length of the shortest route along every remaining road that returns to its start.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A network of paths has a total length of 62 km. Exactly four vertices, $A$, $B$, $C$ and $D$, have odd degree. The shortest distances between them, in km, are $AB=7$, $AC=11$, $AD=5$, $BC=6$, $BD=9$ and $CD=8$.

   (a)

   How many different ways are there of pairing up the four odd vertices?

   [1 mark]

   • A$3$
   • B$2$
   • C$4$
   • D$6$

   (b)

   Which pairing of the odd vertices gives the shortest repeated distance?

   [1 mark]

   • A$AB$ and $CD$
   • B$AC$ and $BD$
   • C$AD$ and $BC$
   • D$AB$ and $AD$

   (c)

   Find the length of the shortest route that travels along every path and returns to its starting vertex.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A salesman must visit five towns $A$, $B$, $C$, $D$ and $E$, each once, and return to the start. The network of distances in km between the towns is complete and satisfies the triangle inequality: $AB=12$, $AC=9$, $AD=15$, $AE=11$, $BC=10$, $BD=14$, $BE=8$, $CD=13$, $CE=7$ and $DE=6$.

   (a)

   Use the nearest neighbour algorithm, starting at $A$, to find an upper bound for the length of the optimal tour.

   [3 marks]

   (b)

   By deleting vertex $D$, find a lower bound for the length of the optimal tour.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A courier operates between five depots $A$, $B$, $C$, $D$ and $E$ joined by roads with lengths in km: $AB=8$, $AC=5$, $AE=11$, $BC=6$, $BD=9$, $CD=7$, $CE=10$ and $DE=4$.

   (a)

   An inspector must travel along every road and return to the starting depot. Find the length of the shortest route.

   [6 marks]

   (b)

   A different driver must visit every depot exactly once and return to the start, so the roads are first converted into a complete network of shortest distances. Show that $AD=12$ and $BE=13$ in this network. Then use the nearest neighbour algorithm from $A$ to find an upper bound, and delete $E$ to find a lower bound, for the optimal tour.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   A connected network has six vertices with degrees $2$, $3$, $3$, $4$, $4$ and $4$. The total length of all its roads is 52 km. The two vertices of odd degree are $X$ and $Y$, and the shortest distance between $X$ and $Y$ is 9 km.

   (a)

   Which statement about the network is correct?

   [1 mark]

   • AIt has a closed route that uses every road exactly once
   • BEvery route that uses every road must repeat at least three roads
   • CIt has a trail that uses every road exactly once, but no such closed route
   • DNo route can use every road exactly once

   (b)

   What is the length of the shortest route that travels along every road and returns to its start?

   [1 mark]

   • A$61$ km
   • B$52$ km
   • C$70$ km
   • D$43$ km

   (c)

   Find the length of the shortest route that travels along every road and finishes at a different vertex from where it starts, and say where it should start and finish.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   In a classical travelling salesman problem on a complete network of five vertices that satisfies the triangle inequality, the vertex $V$ is deleted. The minimum spanning tree of the other four vertices has weight 24, and the two shortest edges at $V$ have lengths 5 and 8. Doubling the edges of a minimum spanning tree of the whole network gives a closed walk of length 52 that visits every vertex.

   (a)

   What lower bound for the optimal tour does the deleted vertex method give?

   [1 mark]

   • A$24$
   • B$29$
   • C$13$
   • D$37$

   (b)

   Which statement about the length $T$ of the optimal tour must be true?

   [1 mark]

   • A$T\le37$
   • B$37\le T\le52$
   • C$T\ge52$
   • D$T=45$

   (c)

   In the closed walk of length 52, vertex $Y$ is visited a second time on a section $X\to Y\to Z$ whose edges have lengths 10 and 14. The direct edge $XZ$ has length 19. Find the improved upper bound after using this shortcut.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   A village has six junctions $G$, $H$, $J$, $K$, $L$ and $M$ joined by roads whose lengths in km are $GH=5$, $GJ=7$, $HJ=4$, $HK=8$, $JL=6$, $KL=3$, $KM=9$ and $LM=5$. A road inspector must travel along every road and return to the starting junction.

   (a)

   Identify the vertices of odd degree and find the total length that must be repeated for each possible pairing of them.

   [3 marks]

   (b)

   Find the length of the shortest route, and state which roads are travelled twice.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   A nature reserve has five junctions $P$, $Q$, $R$, $S$ and $T$ joined by paths whose lengths in km are $PQ=7$, $PR=9$, $PT=11$, $QR=5$, $QS=8$, $RS=6$, $RT=10$ and $ST=4$.

   (a)

   A warden must walk along every path and return to the starting junction. Find the length of the shortest route.

   [6 marks]

   (b)

   A guide must instead visit every junction exactly once and return to the start. The shortest distances between junctions, in km, are $PQ=7$, $PR=9$, $PS=15$, $PT=11$, $QR=5$, $QS=8$, $QT=12$, $RS=6$, $RT=10$ and $ST=4$. Use a minimum spanning tree to find an upper bound for the optimal tour, then use shortcuts to improve it.

   [6 marks]

   Total for question 8: 12 marks

End of questions