Exercise 38
1 . The following weight adjacency matrix shows the information of a graph with five vertices A , B , C , D and E :
A B C D E A - 76 32 43 31 B 76 - 52 12 22 C 32 52 - 31 33 D 43 12 31 - 14 E 31 22 33 14 -
Prim ’ s algorithm , starting at A , is used to find the minimum spanning tree for this graph .
( a ) State the edge of the greatest weight .
( b ) By using the algorithm , find the minimum spanning tree .
( c ) Write down the weight of the minimum spanning tree .
[ 1 ]
[ 3 ]
[ 1 ]
2 . The following cost adjacency matrix shows the information of a graph with seven vertices A , B , C , D , E , F and G :
A B C D E F G A - 38 89 63 70 26 51 B 38 - 56 82 x 44 73 C 89 56 - 42 30 40 55 D 63 82 42 - 70 52 62 E 70 x 30 70 - 60 40 F 26 44 40 52 60 - 28 G 51 73 55 62 40 28 -
9
Prim ’ s algorithm , starting at B , is used to find the minimum spanning tree for this graph . The cost corresponding to the edge BE is x , where x� .
( a ) Write down the maximum possible value of x such that BE is the first edge to be chosen in this algorithm .
[ 1 ]
It is given that x � 29 .
( b ) By using the algorithm , find the minimum spanning tree .
( c ) Write down the cost of the minimum spanning tree .
[ 3 ]
[ 1 ] www . seprodstore . com
133