Algorithms MCQ - Algorithm Design Techniques

21 A undirected graph G has n nodes. Its adjacency matrix is given by an n x n square matrix whose
1. diagonal elements are 0's, and
2. non-diagonal elements are l's.
Which one of the following is TRUE?

In adjacency matrix if diagonal elements are 0’s and non-diagonal are 1’s then it is complete graph and in complete graph of n vertices total n^n–2 Spanning trees are possible and cost of each tree. is (n – 1) because for n vertex graph, (n – 1) edges required in a tree.

22 Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?

Option A is correct, there exists a cut set in G having all edges of maximum weight

23 Consider a weighted complete graph G on the vertex set {v₁, v₂,..., v_n} such that the weight of the edge (v_i, v_j) is 2 |i - j|. The weight of a minimum spanning tree of G is

Minimum spanning tree of such a graph is

Weight of the minimum spanning tree
= 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) |
= 2n – 2

24 Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w. Which of the following is FALSE?

e is needed not to be present in every spanning tree since there may be edges (in cycle formed by adding e), which has same weight as e has.

Common Data for Q. 25 & Q. 26

Suppose the letters a, b, c, d, e have probabilities

respectively

25 For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree?

In prims algorithm we can select arbitary vertex and them, find all the edges that connect the tree to new vertex and find the minimum and add it to the tree. So option “C” is correct
(d, f), C), (d, a), (a, b), (c, e), (F, h), (g, h) (g, i).