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

Your Practice Set – Applications and Interpretation for IBDP Mathematics
2 . Consider the following weighted graph :
( a )
Is Eulerian trail exists in the above graph ? Explain your answer .
( b )
Write down the adjacency matrix M of the graph .
( c )
Hence , find the total number of walks of length 3 from C to A .
Kruskal ’ s algorithm is used to find the minimum spanning tree for this graph .
[ 2 ]
[ 2 ]
[ 2 ]
( 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
A
-
35
45
75
40
80
B
35
-
45
75
50
105
C
45
45
-
30
75
130
D
75
75
30
-
50
75
E
40
50
75
50
-
55
F
80
105 130
75
55
-
( f ) Using the nearest neighbour algorithm , starting and finishing at D , find an upper bound of the total weight of a cycle that passes through all six vertices .
[ 3 ] ( g ) Using the deleted vertex algorithm by deleting the vertex D , find a lower bound of the total weight of a cycle that passes through all six vertices . [ 4 ]
144
SE Production Limited