Algorithms MCQ - Algorithm Design Techniques

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

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

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?

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

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

MST, The complete graph should be

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

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

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

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

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