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

9
Exercise 37
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
-
16
22
40
30
B
16
-
12
18
24
C
22
12
-
36
32
D
40
18
36
-
12
E
30
24
32
12
-
Kruskal ’ s algorithm is used to find the minimum spanning tree for this graph .
( a ) State the edge ( s ) of the smallest 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 :

9

A
B
C
D
E
F
G
A
-
33
x
51
72
36
54
B
33
-
66
70
45
64
76
C
x
66
-
30
39
80
56
D
51
70
30
-
78
62
72
E
72
45
39
78
-
90
30
F
36
64
80
62
90
-
58
G
54
76
56
72
30
58
-
Kruskal ’ s algorithm is used to find the minimum spanning tree for this graph . The cost corresponding to the edge AC is x , where x � 30 and x� .
( a ) State the edge ( s ) of the smallest cost .
( b ) Write down the maximum possible value of x such that AC is the only sixth edge to be chosen in this algorithm .
[ 1 ]
[ 1 ]
129 www . seprodstore . com