6 . Consider the following weighted graph : 32
F E
9 19 ( a ) Is Eulerian circuit exists in the above graph ? Explain your answer .
[ 2 ] Prim ’ s algorithm , starting at C , is used to find the minimum spanning tree for this graph .
D
( 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 |
- |
17 |
23 |
44 |
27 |
18 |
26 |
B 17 - 6 27 21 30 10 C 23 6 - 21 27 36 16 D 44 27 21 - 19 28 23 E 27 21 27 19 - 9 11 F 18 30 36 28 9 - 20 G 26 10 16 23 11 20 -
( e ) Using the nearest neighbour algorithm , starting and finishing at G , 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 G , find a lower bound of the total weight of a cycle that passes through all seven vertices .
[ 4 ]
© SE Production Limited 22 All Rights Reserved 2021