Algorithms on graphs II

Sample questions

Original practice questions written in the style of the exam.

1. Question 16 marks

   A road inspector must travel along every road in the network below at least once, starting and finishing at $A$. Road lengths are in km.

   Road	AB	AC	AD	BC	BE	CD	CE	CF	DF
   Length	6	9	7	5	8	4	3	10	6

   Use the route inspection algorithm to find the length of the shortest inspection route. State which roads must be travelled twice.

   Mark scheme

   • B1 Total length of roads $= 58\,\text{km}$ (1)
   • B1 Odd vertices: $A$ (3), $B$ (3), $C$ (5), $D$ (3) (1)
   • M1 All three pairings considered: $AB + CD = 6 + 4 = 10$ (1)
   • A1 $AC + BD = 9 + 9 = 18$ and $AD + BC = 7 + 5 = 12$ (1)
   • A1 Repeat roads $AB$ and $CD$ (1)
   • A1 Shortest route $= 58 + 10 = 68\,\text{km}$ (1)
2. Question 26 marks

   The table shows the travel times, in minutes, between five towns.

   	A	B	C	D	E
   A	–	27	23	26	22
   B	27	–	10	28	16
   C	23	10	–	29	19
   D	26	28	29	–	18
   E	22	16	19	18	–

   (a) Use the nearest neighbour algorithm, starting at $A$, to find an upper bound for the travelling salesperson problem.

   (b) By deleting $A$ and finding a minimum spanning tree for the remaining towns, find a lower bound.

   (c) Write down an interval within which the optimal tour length must lie.

   Mark scheme

   • (a) M1 Route $$ (1)