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

The Gateway to Computer Science Excellence

+1 vote

Best answer

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,458 answers

195,370 comments

100,255 users