Apps. and Interpretation for IBDP Maths Ebook 2 | Page 152

Your Practice Set – Applications and Interpretation for IBDP Mathematics
( e ) Using the nearest neighbour algorithm , starting and finishing at F , find an upper bound of the total weight of a cycle that passes through all six vertices .
[ 3 ] ( f ) Using the deleted vertex algorithm by deleting the vertex F , find a lower bound of the total weight of a cycle that passes through all six vertices . [ 4 ]
Solution
( a ) ( i ) 4 A1
( ii ) A , F A1
( b ) EF A1
( c )
Eulerian circuit does not exist .
A1
As not all vertices are of even degree .
A1
( d ) ( i ) 180 A1
( ii ) 140 A1
( e )
For any three edges correct
A1
For all edges correct
A1
1 .
Choose FE of weight 75
2 .
Choose ED of weight 90
3 .
Choose DC of weight 115
4 .
Choose CB of weight 120
5 .
Choose BA of weight 90
6 .
Choose AF of weight 105
Thus , the required upper bound is 595 .
A1
( f )
For any two edges correct
A1
For all edges correct
A1
1 .
Choose AB of weight 90
2 .
Choose DE of weight 90
3 .
Choose BE of weight 100
4 .
Choose CD of weight 115
Therefore , the weight of a minimum spanning tree
after deleting the vertex F is 395 .
A1
The required lower bound
� 395 � 75
� 105
�
575
A1
[ 2 ]
[ 1 ]
[ 2 ]
[ 2 ]
[ 3 ]
[ 4 ]
142
SE Production Limited