Question

9. Apply figure and use adjacency matrix to represent the minimum spanning tree Kruskal algorithm to find the minimum spanning tree in the following 30 2 1) 25 9 10 12

Answer 1

Minumum Spanning Tree -:

A spanning of is the subgraph such that all the vertices are connected to each other and there is n-1 edges in this graph where n is no. of vertices.

In above example all edges with minimun weight is as follows

(1,2)=1

(1,7)=2

(2,3)=2

(5,11)=3

(5,6)=4

(2,5)=5

(8,11)=6

(10,11)=7

(9,10)=8

(7,10)=8

(6,9)=9

(3,6)=11

(4,7)=12

(1,4)=13

(5,8)=14

(5,9)=15

(6,7)=17

(1,3)=25

(3,5)=30

So using Kruskal's algorithm connect minimum edges disjoint sets to each other and make shure they do not connect in circle. So as per algorithm only following edges are connected to each other

(1,2),(1,7),(2,3),(5,11),(5,6),(2,5),(8,11),(10,11),(9,10)&(4,7)

Here

n=no. of vertices = 11

n-1=10= edges

Minimum spanning tree and it's adjacency matrix is sending by an image

Mini m 2. 6 O.