Distinct Edge Weights

Suppose we are given a connected, undirected, weighted graph. This is a graph $G = (V, E)$ together with a function $w: E \rightarrow \mathbb{R}$ that assigns a real weight $w(e)$ to each edge $e$, which may be positive, negative, or zero. This chapter describes several algorithms to find the minimum spanning tree of $\bold{G}$, that is, the spanning tree $T$ that minimizes the function

$$w(T):=\underset{e \space\varepsilon\space T}{\sum}w(e).$$

Distinct edge weights

An annoying subtlety in the problem statement is that weighted graphs can have more than one spanning tree with the same minimum weight; in particular, if every edge in $G$ has weight $1$, then every spanning tree of $G$ is a minimum spanning tree, with weight $V − 1$. This ambiguity complicates the development of our algorithms; everything would be much simpler if we could simply assume that minimum spanning trees are unique.