|
O |
A |
B |
C |
D |
E |
F |
G |
H |
I |
O |
- |
10 |
* |
* |
7 |
* |
5.66 |
q |
* |
* |
A 10 - * * * 5.66 p * 10 * B * * - 2 * 6.32 * * 2 * C * * 2 - * * * 4.24 * 6 D 7 * * * - * * 3 * 3 E * 5.66 6.32 * * - 2 * * * F 5.66 p * * * 2 - 3.16 * * G q * * 4.24 3 * 3.16 - * * H * 10 2 * * * * * - * I * * * 6 3 * * * * -
( f ) Write down the value of
( i ) p ;
( ii ) q .
[ 2 ]
Due to heavy snow , roads AH , HB , BC , CI , EB , GC and DI are blocked such that vehicles cannot use the above roads .
The following modified table shows the least distance of a path , in kilometres , connecting any two towns from O , A , D , E , F and G .
O A D E F G O - 10 7 7.66 5.66 q A 10 - 13.8 5.66 p 10.8 D 7 13.8 - 8.16 6.16 3 E 7.66 5.66 8.16 - 2 5.16 F 5.66 p 6.16 2 - 3.16 G q 10.8 3 5.16 3.16 -
( g ) Using the nearest neighbour algorithm , starting and finishing at A , find an upper bound of the total distance of a cycle that passes through all six towns , giving the answer correct to one decimal place .
[ 3 ]
( h ) Using the deleted vertex algorithm by deleting the vertex A , find a lower bound of the total distance of a cycle that passes through all six towns , giving the answer correct to one decimal place .
[ 4 ]
© SE Production Limited 4 All Rights Reserved 2021