Register

GO Classes DPP | Algorithm|MST

822 views
8 8 votes
Let G be a connected, undirected graph of $50$ vertices and $200$ edges. The weight of a minimum spanning tree of G is $800$ . When the weight of each edge of G is decreased by ten, the weight of a minimum spanning tree becomes $\_\_\_\_$ .

3 Answers

1 1 vote

A minimum spanning tree (MST) for a graph with $\mathbf{V}$ vertices always contains exactly $\mathbf{V}-1$ edges.

1. Number of Edges in MST: The graph has 50 vertices, so its MST will always have 50 $1=49$ edges.

2. Effect of Weight Change: Decreasing the weight of every edge in the graph by the same amount (10) doesn't change the relative order of the weights. This means the same set of 49 edges that formed the original MST will also form the new MST.

3. Calculate the New Weight:

  • The original MST weight was $800$.
     
  • Each of the $\mathbf{4 9}$ edges in that MST is now $\mathbf{1 0}$ units lighter.
     
  • Total weight decrease $=49$ edges $\times 10=\mathbf{4 9 0}$.
     
  • New MST weight $=800-490=\mathbf{3 1 0}$.
0 0 votes
let's x1, x2, x3,... x49 are the edges of mst

so x1+x2+... +x49 = 800

but weight of every edge is decreased by 10,but that doesn't change the mst edges, so new edges are x1-10, x2-10, x3-10... x49-10

so we will remove 10 from both sides.... That will do 49 times

New mst weight is x1-10 + x2-10 +... + x49-10 = 800 - 490

New weight is 310
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | Alg...Next → · LL1 table
← Previous in category · GO Classes DPP | Alg...Next in category → · GO Classes DPP | Alg...
Position:
Show:

Related questions

6 6 votes
4 4 answers
1.0k
1.0k views
GO Classes asked Oct 3, 2025
1,000 views
GO Classes DPP | Algorithm|MST
The number of distinct minimum spanning trees for the weighted graph below is____________ 
5 5 votes
3 3 answers
590
590 views
GO Classes asked Oct 3, 2025
590 views
GO Classes DPP | Algorithm|MST
Consider a graph with the following weighted edges: Which one of the following sequences cannot be the order of edges added to a Minimum Spanning Tree (MST) using Kruskal...
5 5 votes
2 2 answers
554
554 views
GO Classes asked Oct 3, 2025
554 views
GO Classes DPP | Algorithm|ASYMPTOTIC ANALYSIS
Arrange the following functions by their asymptotic growth rate in increasing order.$f_1(n)=(\log n)^{\log n}$ $f_2(n)=2^{\sqrt{\log _2 n}}$ $f_3(n)=n^{1 / 3}(\log n)^3$ ...
6 6 votes
2 2 answers
605
605 views
GO Classes asked Oct 3, 2025
605 views
GO Classes DPP | Algorithm|ASYMPTOTIC ANALYSIS
Consider the following three statements regarding asymptotic notation:I. $\log \left(n^c\right)=\Theta(\log n)$ where $c>0$ is a constantII. $3^{n+5}=\Theta\left(3^n\righ...