Data Structures and Algorithms - Design Techniques

Avatto > > UGC NET COMPUTER SCIENCE > > PRACTICE QUESTIONS > > Data Structures and Algorithms > > Design Techniques

31. The length of the path from v₅ to v₆ in the MST of previous question with n = 10 is

Answer
Comment
Array

Option : C
Explanation :
Length of path V₅ to V₆ in mst of n = 10 vertices is

Path from V₅ to V₆ contain 8+4+3+6+10 = 31

You must be logged in to post a comment.

You must be logged in to post a comment.

32. Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edge in G. Let T and T' be the minimum spanning trees of G and G' respectively, with total weights t and t'. Which of the following statements is TRUE?

Answer
Comment
Array

Option : D
Explanation :

so both tree are different and. t' ≠ t²
so option D is correct

You must be logged in to post a comment.

You must be logged in to post a comment.

33. 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 _______.

Answer
Comment
Array

Option : A
Explanation :
MST, The complete graph should be

Total sum = 10 + 9 + 2 + 15 + 16 + 7 + 4 + 6 = 69

You must be logged in to post a comment.

You must be logged in to post a comment.

34. Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change

Answer
Comment
Array

Option : A
Explanation :
Minimum sparring tree of G does not change, because every edge weight is positive and distinct, so to increase the value of each edge by same constant value it does not change tree.
Q is false because path may be change. Here path from B to C can. be via A but after increase by 1 path must be from B to C direct.
Example

You must be logged in to post a comment.

You must be logged in to post a comment.

35. Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1,2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is _______.

Answer
Comment
Array

Option : A
Explanation :

Here 3 can’t be taken because it will produce a cycle so take 4.
This solution is 1 + 2 + 4 = 7

You must be logged in to post a comment.

You must be logged in to post a comment.

Related Quiz.
Design Techniques

Forgot your password?

I agree with the Terms.