wiz-icon
MyQuestionIcon
MyQuestionIcon
1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

An undirected graph G has n nodes. lts adjacency matrix is given by n×n square matrix whose

1. diagonal elements are 0's, and
2. non-diagonal elements are 1's.

Which one of the following is TRUE?

A
Graph G has multiple distinct MST's each of cost n1
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
B
Graph G has a unique MST Of cost n1
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
Graph G has no minimum spanning tree MST
No worries! We‘ve got your back. Try BYJU‘S free classes today!
D
Graph G has multiple spanning trees of different costs
No worries! We‘ve got your back. Try BYJU‘S free classes today!
Open in App
Solution

The correct option is A Graph G has multiple distinct MST's each of cost n1
Undirected graph G contains n nodes.



In undirected graph G the diagonal elements are 0 means there is no self loop of any vertex. When each vertex in G is connected through n vertices in the graph G so G is a complete graph.

In a complete graph apply the Cayley's theorem for the total number of minimum spanning tree in a complete graph G with n vertices is n2.

So G has multiple distinct MST's. The cost of its spanning tree is sum of all edges.

If G contains vertices then we will stop the algorithm after adding the n1 edges.

So each spanning tree have a cost n1


flag
Suggest Corrections
thumbs-up
0
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon