1,099 views
0 votes
0 votes


2) 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?


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

Expain?

 

3 Answers

1 votes
1 votes

Answer should be C) that is graph has multiple distinct MST each of Size (n-1)

Slution:

Consider n=3 .... and let names of nodes are A,B,C so our matrix will be [ 0 1 1 ]

                                                                                                                   [ 1 0 1 ]

                                                                                                                   [1 1 0 ]

Now ...We got a Triangle A,B,C in which AB=BC=CA=1 (that is Cost of path/Edge)

Now For Spanning tree We sholud have N nods and N-1 Edges ..So ..Possible Tree Are

1)A-B-C of length 2 that is Ab=1 and BC=1 that 1+1=2 which is (n-1)..

2)B-A-C of length 2 that has BA=1 and AC=1 and total of 2 ...like that ..so we have other tree also like 

CAB then CBA the BCA all are of SAME LENGTH that is (N-1) here N=3 so length is 3-1 that is 2.

So   Graph has multiple Spanning tree each of COST (N-1)

 

0 votes
0 votes

C is the Answer.

Here you have an undirected graph with n nodes. So, if you represent the Adjacency matrix the value for the adjacency will be 1 (By default the edge weight of the undiected grapgh is 1 as the distance between two vertices can not be 0).

If you clearly observe the mentioned points that, diagonal elements are 0's and non diagonal elements are 1's. This says that the graph is a complete simple graph, for any complete graph multiple MST's are possible but the cost will be be n-1.

You can take any example for complete graph and verify yourself.

0 votes
0 votes

Its a complete graph which has $n^{n-2}$ ST.

The adjacency matrix of a weighted graph can be used to store the weights of the edges.

Ref: http://users.monash.edu/~lloyd/tildeAlgDS/Graph/

Assuming all edge weight is 1.(as given by adjacency matrix) all ST will be MST with weight $n-1$.

So C will be correct.

A. False.

Theorem: A simple graph is connected if and only if it has a spanning tree. (note iff)

So, No MST is possible only for disconnected graph.

Ref: https://homepage.cs.uri.edu/faculty/hamel/courses/2012/fall2012/csc447/lecture-notes/csc447-ln026.pdf

B. False. Explained above.

D. False. Here all ST have same cost.

 

Related questions

4 votes
4 votes
1 answer
2
srestha asked Apr 30, 2018
3,102 views
1) Kruskal Algorithm2) Prims Algorithm3) Dijkstra Algorithm4) Bellman Ford Algorithm5) Floyd Warshall AlgorithmAmong these which one works for onlyi) Positive edge weight...
1 votes
1 votes
0 answers
3
Na462 asked Feb 19, 2018
617 views
Given a graph with positive and distinct edge weights. If I double or triple.. the edge weights then:- 1. Shortest path will remain same2. Mst will remain sameRight?Note ...
3 votes
3 votes
0 answers
4
smsubham asked Jan 6, 2018
519 views
Am getting 7. The answer given is 10.A - B , A - D , D - E , E - C are the edges i have included.