I want to create an algorithm that determines if a given weighted undirected graph has a unique MST or not. I found an answer here, but I do not understand it. It says:
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.
Can someone explain this more thoroughly? I don't really understand what we're supposed to be doing after we find out original tree. From what I understand, once we find our original tree, we add $1$ to all the weights that are in the tree and the graph, and 0 if it is not. We then run the MST-finding algorithm again, and if we find a different tree, then we have our answer.
Why does this work?
Thank you.
Best Answer
Suppose that you have a weighted graph $G$ on $n$ vertices with integer weights, and let $W_{MST}(G)$ be the weight of the minimum spanning tree of $G$. This is the same algorithm only using plain-number mapping for simplicity (at the cost of having integer weights, but you can fix that too if you really want). The general intuition is to create an MST, and then discourage the algorithm from using these particular edges by adding a small $\varepsilon$ weight that would change the weight by a negligible amount (at most $(n-1)\cdot \varepsilon$, that is, the number of edges in a tree times $\varepsilon$).
I hope this helps $\ddot\smile$