Log In
33 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
edited by

4 Answers

55 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$

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
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
0 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:



Related questions

30 votes
7 answers
Suppose $c = \langle c[0], \dots, c[k-1]\rangle$ is an array of length $k$, where all the entries are from the set $\{0, 1\}$. For any positive integers $a \text{ and } n$, consider the following pseudocode. DOSOMETHING (c, a, n) $z \leftarrow 1$ ... , then the output of DOSOMETHING(c, a, n) is _______.
asked Feb 16, 2015 in Algorithms jothee 2.8k views
53 votes
5 answers
The graph shown below has $8$ edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight $36$ and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all $8$ edges of this graph is_______________.
asked Feb 13, 2015 in Algorithms makhdoom ghaya 7.4k views
32 votes
1 answer
Consider the relation $X(P,Q,R,S,T,U)$ with the following set of functional dependencies $F = \{ \\ \; \; \{P, R\} \rightarrow \{S, T\}, \\ \; \; \{P, S, U\} \rightarrow \{Q, R\} \\ \; \}$ Which of the following is the trivial functional dependency in $F^+$, where $F^+$ is closure ... $\{P, R\} \rightarrow \{R, T\}$ $\{P, S\} \rightarrow \{S\}$ $\{P, S, U\} \rightarrow \{Q\}$
asked Feb 14, 2015 in Databases jothee 4.5k views
20 votes
7 answers
While inserting the elements $71, 65, 84, 69, 67, 83$ in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is $65$ $67$ $69$ $83$
asked Feb 14, 2015 in DS jothee 2.1k views