1 Fiona is a mobile hairdresser. One day she needs to visit five clients, A to E, starting and finishing at her own house at F . She wants to find a suitable route that does not involve her driving too far.

1. Which standard network problem does Fiona need to solve? The shortest distances between clients, in km, are given in the matrix below.

   	A	B	C	D	E
   A	-	12	8	6	4
   B	12	-	10	8	10
   C	8	10	-	13	10
   D	6	8	13	-	10
   E	4	10	10	10	-

2. Use the copy of the matrix in the Printed Answer Booklet to construct a minimum spanning tree for these five client locations.
   State the algorithm you have used, show the order in which you build your tree and give its total weight. Draw your minimum spanning tree. The distance from Fiona's house to each client, in km, is given in the table below.

   	A	B	C	D	E
   F	2	11	9	7	5

3. Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route.
4. (a) Find all the cycles that result from using the nearest neighbour method, starting at F .
   (b) Use these to find an upper bound for the length of Fiona's route.
5. Fiona wants to drive less than 35 km . Using the information in your answers to parts (iii) and (iv) explain whether or not a route exists which is less than 35 km in length.