GATE CSE 2015 | Set 3 | Question: 40

Question

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 ______.

Comments

gate pyq on same topic 

https://gateoverflow.in/39673/gate-cse-2016-set-1-question-14

---

Here $300$ edges in $G$ this information has no use for soln.
Only use $100$ vertices and the given weight of MST $500$, weight increase of $5$

---

 Try to solve by just taking small graph

 

Answer 1

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$

Comments

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.

Answer 2

No of edges =99 , now mention condition 99*5 = 495+500 = 995

Answer 3

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

Answer 4

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 5

To connect 100 vertex we need 99 edges.
as previously the MST has weight as 500.
Now that 500 +  (99 * 5 ) = 995 in total

so Final wight of MST is 995.

Comments

gate pyq on same topic 

https://gateoverflow.in/39673/gate-cse-2016-set-1-question-14

Answer 6

the formula is [total present cost] + [no.of edges * added amount] (just from repeated observations with various values, check for yourself)

total present cost is 500
no.of edges are n-1 = 99
added amount is 5

plug in the values we get 995