5 . Consider the following weighted graph :
F
50
A
E
61 65 G
B
D
61
C
( a ) Is Eulerian trail exists in the above graph ? Explain your answer . [ 2 ]
( b ) Write down the adjacency matrix M of the graph . [ 2 ]
( c ) Hence , find the total number of walks of length 4 from D to A .
[ 2 ] Kruskal ’ s algorithm is used to find the minimum spanning tree for this graph .
( d ) By using the algorithm , find the minimum spanning tree .
( e ) Write down the weight of the minimum spanning tree .
The following table shows the least weight of a path connecting any two vertices .
[ 3 ]
[ 1 ]
A B C D E F G A - 63 111 121 109 50 53 B 63 - 52 113 126 113 65 C 111 52 - 61 115 115 58 D 121 113 61 - 54 113 68 E 109 126 115 54 - 59 61 F 50 113 115 113 59 - 57 G 53 65 58 68 61 57 -
( f ) Using the nearest neighbour algorithm , starting and finishing at E , show that an upper bound of the total weight of a cycle that passes through all seven vertices is 398 .
[ 2 ]
© SE Production Limited 18 All Rights Reserved 2021