Determine if a given weighted graph has unique MST

问题:

I'm looking for an algorithm (or any other way) to determine if a given weighted graph has unique MST (Minimum spanning tree) in O(ElogV)?

I don't know anything about the weights (e.g. weight(e1) != weight(e2)), and the algorithm just return True if this graph has only one unique MST or False if not.

I started by using Kruskal's algo, and check if find-set(u)==find-set(v) so there is a circle in the MST, but this way does not cover all the scenarios as I thought :(

Thanks a lot! Tomer.

回答1:

You can prove whether it has a unique MST in O(E log(V)).

First find a minimum spanning tree with standard techniques.

Go back to your original tree, and replace all weights with pairs of numbers, the original weight, and then 0 or 1 based on whether or not it is in the MST you found. These pairs of numbers can be added together pairwise, and compared pairwise as well - just like normal numbers.

Now use the standard techniques to find a minimum spanning tree with these funny weights. The MST that you find will be the MST which shares the least edges with your original tree. Thus if there are multiple MSTs, you are guaranteed to find a different one.