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 ______. Algorithms gatecse-2015-set3 algorithms spanning-tree easy numerical-answers + – go_editor asked Feb 15, 2015 • edited Nov 21, 2017 by kenzou go_editor 10.9k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply kickassakash commented Nov 19, 2023 reply Follow Share gate pyq on same topic https://gateoverflow.in/39673/gate-cse-2016-set-1-question-14 0 votes 0 votes Akash 15 commented Jan 5 reply Follow Share 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$ 0 votes 0 votes Ray Tomlinson commented Jan 22 reply Follow Share Try to solve by just taking small graph 0 votes 0 votes Please log in or register to add a comment.
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$ Anoop Sonkar answered Feb 15, 2015 • edited Jun 24, 2018 by Milicevic3306 Anoop Sonkar comment Share Follow See all 2 Comments See all 2 2 Comments reply Kuldeep Pal commented Jan 15, 2018 reply Follow Share In question 300 edges given what does that statement say ? I didn't get it ? 1 votes 1 votes nailwalhimanshu commented Jan 16, 2018 reply Follow Share 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. 4 votes 4 votes Please log in or register to add a comment.
10 votes 10 votes No of edges =99 , now mention condition 99*5 = 495+500 = 995 chaman_amit answered May 2, 2015 chaman_amit comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Regina Phalange answered Apr 29, 2017 Regina Phalange comment Share Follow See all 0 reply Please log in or register to add a comment.
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$ JashanArora answered Jan 25, 2020 JashanArora comment Share Follow See all 0 reply Please log in or register to add a comment.