The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
171 views
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

 

in Algorithms by Active (3.9k points)
edited by | 171 views
+1
0---1--2---3---4---5----6----7----8----9   ===> 9* 4(1)=>36

1 Answer

+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
by (309 points)
selected by

Related questions

0 votes
3 answers
6
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,830 questions
54,735 answers
189,349 comments
80,095 users