The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
1.9k views

An undirected graph $G$ has $n$ nodes. its adjacency matrix is given by an $n \times 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?

  1. Graph $G$ has no minimum spanning tree (MST)

  2. Graph $G$ has unique MST of cost $n-1$

  3. Graph $G$ has multiple distinct MSTs, each of cost $n-1$

  4. Graph $G$ has multiple spanning trees of different costs

asked in Algorithms by Veteran (52k points) | 1.9k views
+3
how we can say that graph will have distinct spanning trees..

in the qsn only adjacency matrix is gven, the cost matrix is needed to decide whether it will have unique spaaning trees or multiple sppanning trees...what if all the edges in that complete graph is distinct, then it will have only unique spanning tree..
+1
actually here , cost matrix should be same as adjacency matrix otherwise one can not decide
0

here given n×n square matrix whose

(i) diagonal elements are 0’s and

(ii) non-diagonal elements are 1’s.

it means on same node there is no edge, but from one node to all other nodes there is an edge. but nothing is mentioned regarding weight so how we can say Graph G has multiple distinct MSTs.

1 Answer

+22 votes
Best answer
Graph $G$ has multiple distinct MSTs, each of cost  $n-1$

From the given data given graph is a complete graph with all edge weights $1$. A MST will contain $n-1$ edges . Hence weight of MST is $n-1$.

The graph will have multiple MST. In fact all spanning trees of the given graph wll be MSTs also since all edge weights are equal.
answered by Boss (11.1k points)
edited by
+19
Number of spanning trees in complete graph = $n^{(n-2)} \text{ }$ (Cayley's formula)
0
reference or cayley formula plx
+3
+7
Cayley formula is applicable for graph which is

1)complete graph

2)labeled vertices

3)unweighted graph/or all edge weights are same.
0
@reena is right.
+1
yes c is correct
0
undirected too right?
+2
you dont have any info about weight matrix.. so option d should be there
0

@ashwani we can form the weight matrix using the given condition

"n×n square matrix whose (i) diagonal elements are 0’s and (ii) non-diagonal elements are 1’s."

0
@lakshaysaini there is no info about weight of edges...so option D should be right.
0

@sushmita

@reena_kandari

unweighted graph/or all edge weights are same.

To apply cayley formula this is not necessary

in Kn , cayley formula gives No of SPANNING TREES not min spanning trees..IF all weights are same/unweighted then all spanning trees are MSTs

Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,576 questions
54,190 answers
187,519 comments
71,147 users