Your Practice Set – Applications and Interpretation for IBDP Mathematics
3 . Consider the following weighted graph :
Prim ’ s algorithm , starting at F , is used to find the minimum spanning tree for this graph .
( a ) |
Write down the adjacency matrix M of the graph . |
( b ) |
By using the algorithm , find the minimum spanning tree . |
( c ) |
Write down the weight of the minimum spanning tree . |
4 . |
Consider the following weighted graph : |
[ 2 ]
[ 3 ]
[ 1 ]
Prim ’ s algorithm , starting at I , is used to find the minimum spanning tree for this graph .
( a ) Write down the adjacency matrix M of the subgraph with five vertices D , F ,
G , H and I only .
( b ) State the edge of the greatest weight .
( c ) By using the algorithm , find the minimum spanning tree .
( d ) Write down the weight of the minimum spanning tree .
[ 2 ]
[ 1 ]
[ 4 ]
[ 1 ]
134
SE Production Limited