Top MCQs on Minimum Spanning Tree (MST) in Graphs with Answers

Question 1

An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below. What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes? (GATE CS 2011)

1/12(11n^2 – 5n)
n^2 – n + 1
6n – 11
2n + 1

Discuss it

Question 2

The length of the path from v5 to v6 in the MST of previous question with n = 10 is

Discuss it

Question 3

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}. 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? (GATE CS 2010)

Discuss it

Question 4

In the graph given in above question, 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?

Discuss it

Question 5

An undirected graph G has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0‘s and (ii) non-diagonal elements are 1‘s. which one of the following is TRUE?

Graph G has no minimum spanning tree (MST)
Graph G has a unique MST of cost n-1
Graph G has multiple distinct MSTs, each of cost n-1
Graph G has multiple spanning trees of different costs

Discuss it

Question 6

Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?

(a—b),(d—f),(b—f),(d—c),(d—e)
(a—b),(d—f),(d—c),(b—f),(d—e)
(d—f),(a—b),(d—c),(b—f),(d—e)
(d—f),(a—b),(b—f),(d—e),(d—c)

Discuss it

Question 7

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false? (GATE CS 2000)

Every minimum spanning tree of G must contain emin
If emax is in a minimum spanning tree, then its removal must disconnect G
No minimum spanning tree contains emax
G has a unique minimum spanning tree

Discuss it

Question 8

Consider a weighted complete graph G on the vertex set {v1,v2 ,v} such that the weight of the edge (v,,v) is 2|i-j|. The weight of a minimum spanning tree of G is: (GATE CS 2006)

n — 1
2n — 2
nC2
2

Discuss it

Question 9

Let G be a weighted graph with edge weights greater than one and G\'be the graph constructed by squaring the weights of edges 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?

T\' = T with total weight t\' = t²
T\' = T with total weight t\' < t²
T\' != T but total weight t\' = t²
None of the above

Discuss it

Question 10

Consider the following graph:

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal\'s algorithm?

(b,e)(e,f)(a,c)(b,c)(f,g)(c,d)
(b,e)(e,f)(a,c)(f,g)(b,c)(c,d)
(b,e)(a,c)(e,f)(b,c)(f,g)(c,d)
(b,e)(e,f)(b,c)(a,c)(f,g)(c,d)

Discuss it

1 2 3

There are 22 questions to complete.

Last Updated :

Take a part in the ongoing discussion

Trending in News