Apps. and Interpretation for IBDP Maths Ebook 2 | Page 142

Your Practice Set – Applications and Interpretation for IBDP Mathematics

38

Paper 1 – Prim ’ s Algorithm
Example
The following cost adjacency matrix shows the information of a graph with five vertices
A , B , C , D and E :
A
B
C
D
E
A
-
40
27
58
59
B
40
-
43
46
28
C
27
43
-
44
37
D
58
46
44
-
41
E
59
28
37
41
-
Prim ’ s algorithm , starting at C , is used to find the minimum spanning tree for this graph .
( a ) State the edge of the smallest cost .
( b ) By using the algorithm , find the minimum spanning tree .
( c ) Write down the cost of the minimum spanning tree .
[ 1 ]
[ 3 ]
[ 1 ]
Solution
( a ) AC A1
( b )
For any two edges correct
A1
For all edges correct
A1
1 .
Choose AC of cost 27
2 .
Choose CE of cost 37
3 .
Choose BE of cost 28
4 .
Choose DE of cost 41
Thus , the minimum spanning tree is a tree
containing AC , CE , BE and DE .
A1
( c ) 133 A1
[ 1 ]
[ 3 ]
[ 1 ]
132
SE Production Limited