1
$\begingroup$

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.

  • 0
    Welcome to mathSE. Si$n$ce you are new one comment to your question: Although it is obvious from the conte$x$t what MST stands for. Please consider e$x$plai$n$ing your abreviations in the next questions in the beginning.2012-10-22

1 Answers 1

0

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.

  • 0
    got it :) .This discussion helped in understanding MST's a little better.2012-10-22