Distinct edge weight assumption in MST algorithms

Question

My lecture notes for minimum spanning trees say that:

A graph can have several minimum spanning trees but if the edge weights are distinct then the minimum spanning tree is unique. Without loss of generality, we can assume that the edge weights are distinct

I'm trying to convince myself that the distinct edge weights assumption in MST algorithms is a valid one but haven't made much progress. I thought about maybe considering the smallest absolute difference between two adjacent edge weights (call this $\delta$) and then let $\alpha = \delta / m$ where $m$ is the number of edges. If there's $k$ edges of the same weight $w$, order them arbitrarily and replace the edge weight by $w + i\times\alpha$ for $0\le i<k$. Then all edge weights are unique and any MST algorithm applied for these new weights should give a valid MST for the original weights. I'm not convinced that this works though.

Answer 1

You are on the right track. A bit more work is needed.

---

Suppose we have developed a comparison-based MST algorithm $\mathcal A$ for graphs of distinct edge-weights. (You will probably not see an MST algorithm that is not comparison-based.)

Let $G=(E,V,w)$ be a weighted graph where edge-weights might have duplicates. How can we obtain an MST of $G$ using $\mathcal A$?

We can run $\mathcal A$ on $G$, breaking ties among the same edge-weights arbitrarily and consistently, to obtain a spanning tree $T$. However, is $T$ an MST of $G$ still? That is your question.

Let we sort all edge-weights (with duplicates) according to the same tie breaking rules when we ran $\mathcal A$ to obtain $T$. Suppose we get $e_1, \cdots, e_m$. Let $\delta_E$ be the smallest nonzero absolute difference between two edge-weights. Let $\delta_G$ be the smallest nonzero absolute difference between the weights of two spanning trees of $G$. If all edge-weights are the same or all weights of spanning trees are the same, $T$ is trivially an MST. Assume otherwise, so both $\delta_E$ and $\delta_G$ are well-defined. Let $G^+=(V, E, w^+)$, where $$w^+(e_i)=w(e_i)+\frac{i\min(\delta_E, \delta_G)}{n^2}.$$ Then $$i<j\iff w^+(e_i)<w^+(e_j).$$ In particular, all edge-weights of $G^+$ are distinct.

Now we run $\mathcal A$ on $G^+$. Since the comparison order of all edges for $G$ is the same as that of $G^+$, the same spanning tree $T$ will be obtained. Since $\mathcal A$ is an MST algorithm, $w^+(T)\le w^+(T')$ for any spanning tree $T'$ of $G^+$ (or of $G$, since the spanning trees of $G$ are the same as the spanning trees of $G^+$).

$$w(T)<w^+(T)\le w^+(T')\le w(T')+(n-1)\frac{n\delta_G}{n^2}<w(T')+ \delta_G$$

By the definition of $\delta_G$, this means $w(T)<w(T')$.

Answer 2

The real question is: if we assign arbitrary priorities to edges of equal weights, can that break an MST algorithm ? Though this can lead to different MST's, neither the tree-ness property, nor the spanning property nor the minimum weight will be invalidated.

Assigning priorities can be done

• a priori, for instance by numbering the nodes and using the lexicographocal ordering based on (weight, number);

• a posteriori, by declaring that the edges effectively chosen during the resolution had a higher priority.