( d ) Write down the adjacency matrix M of the graph . [ 3 ]
( e ) Hence , find the total number of walks of length at most 3 from C to E .
[ 2 ]
The following table shows the least weight of a path connecting any two vertices .
( f ) Write down the value of
( i ) p ;
|
O |
A |
B |
C |
D |
E |
O |
- |
30 |
36.1 |
p |
36.1 |
30 |
A |
30 |
- |
20 |
30 |
34.1 |
q |
B 36.1 20 - 10 14.1 34.1 C p 30 10 - 10 30 D 36.1 34.1 14.1 10 - 20 E 30 q 34.1 30 20 -
( ii ) q . [ 2 ]
( g ) Using the nearest neighbour algorithm , starting and finishing at O , find an upper bound of the total distance of a cycle that passes through all six positions of scarecrows .
[ 3 ]
( h ) Using the deleted vertex algorithm by deleting the vertex C , find a lower bound of the total distance of a cycle that passes through all six positions of scarecrows , giving the answer correct to one decimal place .
[ 4 ]
© SE Production Limited 4 All Rights Reserved 2021