Your Practice Set – Applications and Interpretation for IBDP Mathematics
( c ) Write down the number of vertices of
( 1 ) odd degree ;
( 2 ) even degree . [ 2 ]
( d ) Is Eulerian circuit exists in the above graph ? Explain your answer .
[ 2 ] Due to the difference between the populations of the four housing estates , the travelling time along the highway may not be proportional to the length of the highway . The following table shows the average times , in seconds , need for a bus to travel along each highway :
Highway AB AD AG BC BH CD CJ Time needed 30 40 60 35 30 45 10
Highway DE EF FG GH HI IJ Time needed 25 65 25 50 20 55
Kruskal ’ s algorithm is used to find the minimum spanning tree for this graph .
( e ) ( 1 ) State the highway with the shortest time needed to travel along .
( 2 ) By using the algorithm , find the minimum spanning tree .
( 3 ) Write down the corresponding total time of the minimum spanning tree . [ 5 ]
( f ) Use the Chinese postman algorithm to find a possible route of minimum time needed for a bus to travel along all highways , starting and finishing at E .
[ 4 ]
By adding three highways in the town , an Eulerian circuit will exist .
( g ) Suggest one possible combination of three highways to be added in the town . [ 3 ]
318
SE Production Limited