Minimum Spanning Tree Multiple choice Questions and Answers (MCQs)

YOU may join our Telegram for all subjects PDF BOOKS.

https://t.me/+Ccx9McEia7wyODg1

Minimum Spanning Tree Multiple choice Questions and Answers (MCQs)

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Which of the following is false in the case of a spanning tree of a graph G?
A
It is tree that spans G
B
It is a subgraph of the G
C
It includes every vertex of the G
D
It can be either cyclic or acyclic
Question 1 Explanation: 
A graph can have many spanning trees. Each spanning tree of a graph G is a subgraph of the graph G, and spanning trees include every vertex of the gram. Spanning trees are always acyclic.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Every graph has only one minimum spanning tree.
A
True
B
False
Question 2 Explanation: 
Minimum spanning tree is a spanning tree with the lowest cost among all the spacing trees. Sum of all of the edges in the spanning tree is the cost of the spanning tree. There can be many minimum spanning trees for a given graph.

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Consider a complete graph G with 4 vertices. The graph G has ..... spanning trees.
A
15
B
8
C
16
D
13
Question 3 Explanation: 
A graph can have many spanning trees. And a complete graph with n vertices has n(n-2) spanning trees. So, the complete graph with 4 vertices has 4(4-2) = 16 spanning trees.

Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
The travelling salesman problem can be solved using .....
A
A spanning tree
B
A minimum spanning tree
C
Bellman - Ford algorithm
D
DFS traversal
Question 4 Explanation: 
In the travelling salesman problem we have to find the shortest possible route that visits every city exactly once and returns to the starting point for the given a set of cities. So, travelling salesman problem can be solved by contracting the minimum spanning tree.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?
A
Graph M has no minimum spanning tree
B
Graph M has a unique minimum spanning trees of cost 2
C
Graph M has 3 distinct minimum spanning trees, each of cost 2
D
Graph M has 3 spanning trees of different costs
Question 5 Explanation: 
Here all non-diagonal elements in the adjacency matrix are 1. So, every vertex is connected every other vertex of the graph. And, so graph M has 3 distinct minimum spanning trees.

There are 5 questions to complete.