The Gateway to Computer Science Excellence
+30 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 ______.
in Algorithms by Veteran (105k points)
edited by | 2.8k views

3 Answers

+48 votes
Best answer
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$
by Active (5k points)
edited by
In question 300 edges given what does that statement say ? I didn't get it ?
The total number of edges present in a graph is 300.

But as we know that the minimum number of edges required in a minimal connected single component graph is n-1.
+10 votes
No of edges =99 , now mention condition 99*5 = 495+500 = 995
by (91 points)
+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
by Loyal (9.7k points)

Related questions

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
50,645 questions
56,601 answers
102,227 users