655 views

3 Answers

7 votes
7 votes

Yes I think the claim is true as

If Edge weights are not distinct then we can have multiple Spanning trees 

Suppose Consider an example

here we choose edges with weight 1 then with 2 then with 3 

In case of 3 if we consider both edges whose weight is 3 the a cycle is formed so we consider only 1 edge by this we can have 2 Spanning trees with same weights

Spanning tree 1 :

Spanning Tree 2:

Let me know if I'm wrong

0 votes
0 votes
Yes, I agree with the claim made and for its proof,

Taking an instance where we have more than one similar edge weights could be the graph (not neccessarily) on which applying kruskal's algo could give us more than one M.S.T's .

NOTE:- The claim holds false everytime we have distinct edge weights.

Let me know if I was wrong.
0 votes
0 votes

It depends on whether edge weight is distinct or not.

Case 1: Edge weight is distinct.

MST is unique so Kruskal's algorithm (as its always works correctly to find MST) cannot give multiple MST.

Ref: https://cs.stackexchange.com/questions/10728/how-many-minimal-spanning-trees-are-there-when-all-edge-costs-are-distinct

Case 2: Edge weight not distinct

Multiple MST of same weight are possible. In this case Kruskal's algorithm may return different MST.

Good Read:

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm#Proof_of_correctness

Related questions

0 votes
0 votes
1 answer
1
go_editor asked Jun 7, 2016
410 views
What is the output of the following program?int main() { int i=0; do { if (i >=5) { i+=2; printf("%d \n", i); break; } else { printf("%d \n", ++i); continue; } } while (i...
0 votes
0 votes
2 answers
3
go_editor asked Jun 8, 2016
451 views
Which of the following statement(s) is(are) true?If $n$ is odd prime number then $2^{n-1} \text{ mod } n =1$If $2^{n-1} \text{ mod } n =1$ for a number $n$ then $n$ is pr...
2 votes
2 votes
1 answer
4
go_editor asked Jun 8, 2016
335 views
Write the truth table for the connective: "If A then B"