( a ) ( i ) Write down the area of the Voronoi cell of the reservoir R
2
.
( ii ) Write down the gradient of the road separating the Voronoi cells of the reservoirs R
2 and R
3
.
( iii ) Hence , find its equation .
( iv ) State the significance of the Voronoi cell of the reservoir R
3
. [ 5 ]
( b ) If one extra reservoir is added to ( 3,1 ) such that the above road plan in the Voronoi diagram is modified , write down the road which is affected and has to be reconstructed .
[ 1 ]
This Voronoi diagram can also be considered as a graph of ten vertices , where the vertices represent the towns O , A , B , C , D , E , F , G , H and I , and the roads connecting the towns are considered as edges .
( c ) Write down
( i ) the number of edges ;
( ii ) the number of vertices of odd degree ;
( iii ) the number of vertices of even degree ;
( iv ) the adjacency matrix M of the graph . [ 8 ]
( d ) Hence , write down the total number of walks of length at least four and at most six from A to B .
[ 2 ]
( e ) ( i ) State one possible Hamiltonian cycle .
( ii ) State one possible Hamiltonian path that starts at H and end at
G .
( iii ) Explain why an Eulerian circuit does not exist .
[ 5 ] The following table shows some of the entries of the least distance of a path , in kilometres , connecting any two towns . The distances are calculated and correct to three significant figures if necessary .
© SE Production Limited 3 All Rights Reserved 2021