edited by
1,360 views
6 votes
6 votes
Consider the following statements

I. Let T be a minimum spanning tree of a graph G.Then for any two vertices u and v the path from u to v in T is the shortest path from u to v in the graph G

II.Suppose that average edge weight for a graph G is Aavg.  Then the minimum spanning tree of G will have weight at most (n-1)Aavg.  where n is the number of vertices in graph G.

which of the above statements are true ?

A)Only I B)Only II C)both I and II D)None of these
edited by

1 Answer

1 votes
1 votes

statement 1: wrong.because there may be a shortest path, but it is not included in MST as it may cause a Loop

Statement 2 is correct .look at simple average .n*tavg will result in the entire graph..but to be MST, you have to take n-1 edges at most.

so it will be (n-1)*T avg  at most

N=number of vertices

So B is correct answer

hope u got my point

Related questions

0 votes
0 votes
3 answers
1
iarnav asked Apr 29, 2018
1,506 views
Question 1) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST?Question2 ) Prim's algorithm works with negative weighted edges?
0 votes
0 votes
2 answers
3
iarnav asked Apr 28, 2018
384 views
Let G be a connected simple graph with non distinct edge weights. Now, e be the lightest edge in G. So, does this edge e is present in every MST of G?My take - when all e...