Data Structures and Algorithms MCQ - Design Techniques

26 G is a graph on n vertices and 2n - 2 edges. The edges of G can be partitioned into two edge disjoint spanning trees. Which of the following is NOT true for G?

Minimum number of edges for a connected graph = n and for a connected tree = n – 1

Here given that 2 n – 2 edges and the edges of graph is partitioned into two edge disjoint trees.
So there are two vertex disjoint paths between every pair of vertices.

27 The weight of a sequence a₀, a₁, …, a_n-1of real numbers is defined as a₀+a₁/2+…+ a_a-1/2^n-1. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a₀, a₁, …,a_n-1 and Y the maximum possible weight of a subsequence of a₁, a₂, …,a_n-1. Then X is equal to

Using concepts of Dynamic Programming to find the maximum possible weight of a subsequence of X, we will have two alternatives.
1. Do not include a₀ in the subsequence: then the maximum possible weight will be equal to maximum possible weight of a subsequence of {a₁, a₂....a_n} which is represented by Y.
2. Include a₀: then maximum possible weight will be equal to a₀ + (each number picked om Y will get divided by 2) a₀ + Y/2. Here you can note that Y will itself pick optimal subsequence to maximum the weight.
Final answer will be Max (Case1, Case2) i.e. Max (Y, a₀ + Y/2). Hence B.

Common Data for Questions 28 and 29
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_ij in the matrix W below is the weight of the edge {i, j}.

28 What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

Minimal possible spanning tree having vertex “0” is a leaf rode is :–

total weight = 4 + 1 + 2 + 3 = 10

29 What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

Path from vertex 1 to 2 is
(1 – 0) + (0 – 4) + (4 – 2)
1 + 4 + 3 = 8

Linked Data Question 30 and 31

An undirected graph G(V, E) contains n(n > 2) nodes named v₁ , v₂ , …, v_n . Two nodes v_i , v_j are connected if and only if 0 < | i – j | ≤ 2. Each edge (v_i , v_j ) is assigned a weight i + j. A sample graph with n = 4 is shown below.

30 What will be the cost of the Minimum Spanning Tree (MST) of such a graph with n nodes?

If we construct graph for n = 6 vertices (V₁ , V₂ , V₃ , V₄ , V₅ , V₆ )
then minimum spanning tree for this graph is

total weight = 31
so if we put n = 6 in option “b” then we get 31
i.e. x² – n + 1
(6)² – 6 + 1 ⇒ 36 – 6 + 1 ⇒ 31.