Your Practice Set – Applications and Interpretation for IBDP Mathematics
4 . Consider the following weighted graph :
( a ) Is Eulerian circuit exists in the above graph ? Explain your answer .
[ 2 ] Prim ’ s algorithm , starting at A , is used to find the minimum spanning tree for this graph .
( b ) |
State the edge of the least weight . |
( c ) |
By using the algorithm , find the minimum spanning tree . |
( d ) |
Write down the weight of the minimum spanning tree . |
The following table shows the least weight of a path connecting any two vertices . |
[ 1 ]
[ 3 ]
[ 1 ]
A B C D E F G A - 80 180 87 72 160 61 B 80 - 131 103 152 240 141
C 180 131 - 93 252 340 241 D 87 103 93 - 159 247 148
E 72 152 252 159 - 97 83 F 160 240 340 247 97 - 99 G 61 141 241 148 83 99 -
( e ) Using the nearest neighbour algorithm , starting and finishing at D , find an upper bound of the total weight of a cycle that passes through all seven vertices .
[ 3 ] ( f ) Using the deleted vertex algorithm by deleting the vertex D , find a lower bound of the total weight of a cycle that passes through all seven vertices . [ 4 ]
146
SE Production Limited