MadeEasy Test Series 2019: Algorithms - Spanning Tree

Question

Consider a simple undirected weighted graph G(V, E) with 10 vertices and 45 edge, assume (u, v) are two vertices weight of a edge is =4lu- vl then the minimum cost of the spanning tree of G_

36

 

Comments

0---1--2---3---4---5----6----7----8----9   ===> 9* 4(1)=>36

Answer 1

The given undirected graph is a complete graph on 10 vertices,so no of edges in Minimum spanning tree = 9

An edge is included in MST iff it's cost is less than or equal to the weights of the remaining edges and doesn't form a cycle,

Now,the minimum possible weight is 4 because it is a simple graph,so loops are not allowed.

Now,if we consider edges,(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10),we obtain the required 9 edges each with a cost of 4

So,Total cost in MST = 9*4 = 36