4
$\begingroup$

Suppose all costs on edges are distinct. How many minimal spanning trees are possible?

I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because Kruskal's, and any other greedy algorithm should choose all the smallest weighted edges first. Then, if all weights on all edges are distinct, then there are no two equivalently weighted minimum spanning trees if a greedy algorithm is used.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Just one. $\endgroup$
    – Me.
    Commented Mar 24, 2013 at 14:56

3 Answers 3

Reset to default
10
$\begingroup$

Consider Kruskal's or Prim's algorithms to get minimal spanning trees. They consider arcs in increasing order of cost. If all costs are different, the order in which they are added is fixed, and so is the spanning tree constructed. It is unique in this case.

Improve this answer
$\endgroup$
8
  • 3
    $\begingroup$ That only shows Kruskal and Prim will return a unique tree? $\endgroup$
    – Hendrik Jan
    Commented Mar 24, 2013 at 15:56
  • 1
    $\begingroup$ Kruskal and Prim return a minimal spanning tree, if you look at the proof they do so, taking out an edge and putting in another maintaining the spanning tree gives a tree with a larger value, unless the edges switched have the same weight. Thus the tree constructed in this case is the minimal spanning tree. $\endgroup$
    – vonbrand
    Commented Mar 24, 2013 at 16:24
  • $\begingroup$ @vonbrand, one lacks a proof that it isn't possible to swap two set of edges of the same weight while maintaining the tree property. $\endgroup$
    – AProgrammer
    Commented Mar 25, 2013 at 10:31
  • 1
    $\begingroup$ @AProgrammer. Kruskal and Prim give a MST. Part of their correctness proof is that if in a step they leave out the next possible minimal cost edge, the resulting tree isn't minimal cost. See also Raphael's answer. $\endgroup$
    – vonbrand
    Commented Mar 25, 2013 at 13:24
  • 1
    $\begingroup$ So we need to look into one of the algorithm correctness proofs to extract what we need; that makes your answer a bit too short, especially since a direct proof is readily available. $\endgroup$
    – Raphael
    Commented Mar 26, 2013 at 13:45
4
$\begingroup$

Assume there were at least two distinct minimal spanning trees. What can you deduce?

Consider an edge $e_1$ in one tree and the cut it induces. What can you say about the edges that are both in this cut and in the other tree?

The ultimate hint:

With this knowledge, can you construct a smaller MST?

This is the standard argument when working spanning trees (and several other graph problems).

Improve this answer
$\endgroup$
0
$\begingroup$

You can give an explicit condition for whether an edge should be in the MST. Consider edge between x and y with weight w. Remove all edges with weights greater than or equal to w. Are x and y still connected? If so, edge e should not be in the MST, otherwise it should.

This isn't qualitatively different to previous answers. It makes sense to prove it using Kruskal's algorithm, but perhaps is an easier statement to think about in the context of uniqueness. More details at: http://tinyurl.com/d9lnb82.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.