0 votes 0 votes If average weight of a minimum spanning tree is Aavg.Then minimum spanning tree will have weight almost (n-1)Aavg, where n is no of vertices in the graph. It is true or false?why? Algorithms minimum-spanning-tree graph-algorithms true-false + – gshivam63 asked May 31, 2016 • edited Jun 24, 2022 by makhdoom ghaya gshivam63 1.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Let a disconnected graph. In disconnected graph, minimumcostspanningtree is not possible. Given statement is wrong. Digvijay Pandey answered May 31, 2016 Digvijay Pandey comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Yes True. If there are n vertices, then minimum number of edges in MST is (n-1) , As MST must be connected with minimum weight edges If avg weight of 1 edge is Aavg then, for (n-1) edges weight (n-1)Aavg srestha answered May 31, 2016 srestha comment Share Follow See all 3 Comments See all 3 3 Comments reply gshivam63 commented May 31, 2016 reply Follow Share Aavg is average Weight of whole minimum spanning tree and not of only one edge. So I didn't get ur answer. Plz explain 0 votes 0 votes gshivam63 commented May 31, 2016 reply Follow Share @shrestha Aavg is average Weight of whole minimum spanning tree and not of only one edge. So I didn't get ur answer. Plz explain 1 votes 1 votes cse23 commented Sep 4, 2016 reply Follow Share we can have more than one minimum spanning tree for a given connected graph(when weights of edges are not unique) but minimum weight in each tree is always same which is given as Aavg is this question. and when all the weights are same then avg wt. of MST =(n-1) * weight of an edge but here Aavg is not wt. of an edge it is weight of whole spanning tree. hence this statement should be false. 0 votes 0 votes Please log in or register to add a comment.