Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Me and my friend were arguing over how to calculate the number of unique MST's in the following situation: if I have a weighted graph G with E edges and all the edges have unique weights then I know that we can have only 1 unique MST. I was thinking what will be the case if only some of the edges 2 or 3 have same weights then how many minimum spanning trees are possible in such a case? I had the idea that there are three cases if I take exactly 2 edges as having same weight: 1) both the edges are in MST 2)neither of the 2 edges is in MST 3) either of the two is in MST.

but we didnt reached an answer with this approach.

share|improve this question
    
Welcome to mathSE. Since you are new one comment to your question: Although it is obvious from the context what MST stands for. Please consider explaining your abreviations in the next questions in the beginning. –  Julian Kuelshammer Oct 22 '12 at 6:43

1 Answer 1

up vote 0 down vote accepted

You can argue something like this:

Take a weighted graph $G = (V,E)$, with unique weights $w_2 < w_3 < \dots < w_E$, and equal weights $w_0 = w_1$. Start a minimum spanning tree algorithm (like Kruskal's) and examine the algorithm's actions when edge $e_0$ and edge $e_1$ are reached. There are multiple cases -

  1. If $e_0$ and $e_1$ can both be inserted without closing a cycle.
  2. If $e_0$ and $e_1$ can both be inserted individually, but they close a cycle together.
  3. If $e_0$ cannot be inserted, but $e_1$ can (or vice versa).
  4. If neither $e_0$ nor $e_1$ can be inserted.

In cases $1,3$, and $4$, the algorithm treats edges $e_0$ and $e_1$ like uniquely weighted edges (say $w_0$ and $w_1 + \epsilon$), inserts them with the correct procedure, and continues on to find a unique solution.

In case $2$, there are two possible minimum spanning trees, one where $e_0$ was inserted and one where $e_1$ was inserted.

share|improve this answer
    
thank you Michael that explanation is helpful. I think I was on the right track. –  revera Oct 22 '12 at 3:23
    
so this means that there will be 5 unique MST's if we take only 2 edges with same weights. –  revera Oct 22 '12 at 3:26
    
Well, not at the same time. Given the graph and the edge weights, depending on the case, you'll have either $1$ or $2$ minimum spanning trees. –  Michael Biro Oct 22 '12 at 3:31
    
got it :) .This discussion helped in understanding MST's a little better. –  revera Oct 22 '12 at 3:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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