edited by
10,735 views
44 votes
44 votes
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is increased by five, the weight of a minimum spanning tree becomes ______.
edited by

5 Answers

Best answer
71 votes
71 votes
First find no of edges in mst.
Mst has $n-1$ edges where $n$ is no of vertices. $100-1 =99$ edges
Each $99$ edges in mst increases by $5$ so weight in mst increased $99*5=495$
Now total weight of mst $=500+495=995$
edited by
4 votes
4 votes
Since there are 100 vertices, there must be 99 edges in Minimum Spanning Tree (MST). When weight of every edge is increased by 5, the increment in weight of MST is = 99 * 5 = 495 So new weight of MST is 500 + 495 which is 995
3 votes
3 votes

Adding or multiplying all the edges of an MST by a constant does not change the MST, it only changes the value of MST.

Vertices = 100.

Hence, edges in the MST = 99.

Weight = 500

 

Since the MST would remain the same; just the edge weights would be upgraded by 5, upgraded MST weight:

$500+99(5)=995$

Answer:

Related questions

36 votes
36 votes
4 answers
1
go_editor asked Feb 14, 2015
9,210 views
Given that hash table $T$ with $25$ slots that stores $2000$ elements, the load factor $a$ for $T$ is _________.
32 votes
32 votes
4 answers
4
go_editor asked Feb 14, 2015
8,941 views
Consider the following array of elements.$\langle 89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100 \rangle$The minimum number of interchanges needed to convert it into a ma...