Your Practice Set – Applications and Interpretation for IBDP Mathematics
( d ) Hence , find the total number of walks of length 4 from C to A . [ 2 ]
( e ) Use the Chinese postman algorithm to find a possible route of minimum weight that passes through all edges , starting and finishing at E .
[ 3 ]
( f ) Write down the corresponding weight of the route . [ 1 ]
2 . Consider the following weighted graph :
( a ) Write down
( i ) the degree of A ;
( ii ) the number of vertices of odd degree ;
( iii ) the number of vertices of even degree .
Kruskal ’ s algorithm is used to find the minimum spanning tree for this graph .
[ 3 ]
( 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 F .
[ 3 ]
( f ) Write down the corresponding weight of the route . [ 1 ]
138
SE Production Limited