4 . Consider the following weighted graph :
A
10
B
15
C
( a ) Write down
F E
23 25
D
( i ) the degree of B ;
( ii ) the number of vertices of odd degree ;
( iii ) the number of vertices of even degree .
[ 3 ] Kruskal ’ s algorithm is used to find the minimum spanning tree for this graph .
( b ) State the edge of the smallest weight . [ 1 ]
( c ) By using the algorithm , find the minimum spanning tree . [ 3 ]
( d ) Write down the weight of the minimum spanning tree . [ 1 ]
( e ) Use the Chinese postman algorithm to find a possible route of minimum weight that passes through all edges , starting and finishing at
C . [ 3 ]
( f ) Write down the corresponding weight of the route . [ 1 ]
© SE Production Limited 14 All Rights Reserved 2021