22
$\begingroup$

Given a weighted, undirected graph G: Which conditions must hold true so that there are multiple minimum spanning trees for G?

I know that the MST is unique when all of the weights are distinct, but you can't reverse this statement. If there are muliple edges with the same weight in the graph, there may be multiple MSTs but there might also be just one:

enter image description here

In this example, the graph on the left has a unique MST but the right one does not.

The closest I could get to finding conditions for non-uniqueness of the MST was this:

Consider all of the chordless cycles (cycles that don't contain other cycles) in the graph G. If in any of these cycles the maximum weighted edge exists multiple times, then the graph does not have a unique minimum spanning tree.

My idea was that for a cycle like this

enter image description here

with n vertices, you can leave out exactly one of the edges and still have all of the vertices be connected. Therefore, you have multiple choices to remove the edge with the highest weight to get a MST, so the MST is not unique.

However, I then came up with this example:

enter image description here

You can see that this graph does have a cycle that fits my condition: (E,F,G,H) but as far as I can see, the minimum spanning tree is unique:

enter image description here

So it seems like my condition isn't correct (or maybe just not completely correct). I'd greaty appreciate any help on finding the necessary and sufficient conditions for the non uniqueness of the minimum spanning tree.

$\endgroup$
  • 1
    $\begingroup$ Your smallest cycles are known as chordless cycles (more or less). $\endgroup$ – Yuval Filmus Jul 10 '16 at 11:22
10
$\begingroup$

in the first picture: the right graph has a unique MST, by taking edges $(F,H)$ and $(F,G)$ with total weight of 2.

Given a graph $G=(V,E)$ and let $M=(V,F)$ be a minimum spanning tree (MST) in $G$.

If there exists an edge $e=\{v,w\}\in E \setminus F$ with weight $w(e)=m$ such that adding $e$ to our MST yields a cycle $C$, and let $m$ also be the lowest edge-weight from $F\cap C$, then we can create a second MST by swapping an edge from $F\cap C$ with edge-weight $m$ with $e$. Thus we do not have uniqueness.

$\endgroup$
  • $\begingroup$ You're right, I corrected that graph in the question now. Do you know if this is the most general condition so that the MST is not unique? Or can it also somehow be determined without the need to first find a MST? $\endgroup$ – Keiwan Jul 10 '16 at 12:21
  • 1
    $\begingroup$ @Keiwan I believe that if you take into account this question then the condition outlined in this answeris also a necessary condition for having multiple MSTs. In other words: a graph $G$ has multiple MSTs if and only if the construction outlined by HueHang can be carried out. $\endgroup$ – Bakuriu Jul 10 '16 at 16:45
  • 1
    $\begingroup$ m needn't be the lowest edge weight from F∩C. In fact, it can only be the highest edge weight, otherwise M would not have been minimal in the first place. Suppose there were an edge e' with w(e') = m' > m = w(e) in F∩C. Then swapping e for e' would leave a spanning tree with total weight less than M's, contradicting the minimality of M. $\endgroup$ – Chad May 4 '17 at 3:21
2
$\begingroup$

A previous answer indicates an algorithm to determine whether there are multiple MSTs, which, for each edge $e$ not in $G$, find the cycle created by adding $e$ to a precomputed MST and check if $e$ is not the unique heaviest edge in that cycle. That algorithm is likely to run in $O(|E||V|)$ time.

A simpler algorithm to determine whether there are multiple MSTs of G in $O(|E|\log(|V|))$ time-complexity.

$\ $1. Run Kruskal's algorithm on $G$ to find an MST $m$.

$\ $2. Try running Kruskal's algorithm on $G$ again. In this run, whenever we have a choice among edges of equal weights, we will first try the edges not in $m$, after which we will try the edges in $m$. Whenever we have found an edge not in $m$ connects two different trees, we claim that there are multiple MSTs, terminating the algorithm.

$\ $3. If we have reached here, then we claim that $G$ has a unique MST.

An ordinary run of Kruskal's algorithm takes $O(|E|\log(|V|))$ time. The extra selection of edges not in $m$ can be done in $O(|E|)$ time. So the algorithm achieves $O(|E|\log(|V|))$ time-complexity.

Why can this algorithm determine if there are multiple MSTs?

Suppose we have an MST $m'$ that is not the same as $m$. It is enough to show that the algorithm running on $G$ will not reach step 3, since the edge found at the end of step 2, which is not in $m$ and connecting two different trees would have been included in the resulting MST had we run Kruskal's algorithm to completion. Let $w$ be the largest weight such that for any edge weighing less than $w$, it is in $m$ if and only if it is in $m'$. Because $m$ and $m'$ have the same number of edges of weight $w$, there exist edges of weight $w$ that are in $m'$ but not in $m$. If the algorithm has exited before processing edges of those edges, we are done. Otherwise, suppose the algorithm is going to process the first edge $e'$ among those edges now. Let $S$ be the set of all edges that have been preserved so far to be included in the resulting MST. $S\subset m$. Since the algorithm have not finished processing edge of weight $w$ not in $m$ such as $e'$, it must have not begun processing edges of weight $w$ in $m$. So edges in $S$ weigh less than $w$. That means $S\subset m'.$ Recall that $e'$ is in $m'$. Since $\{e'\}\cup S\subset m'$, where $m'$ is a tree, $e'$ must connect two different trees in $S$ and the algorithm exits at this point.

Note on further development
Step 1 and step 2 can be interleaved so that we can terminate the algorithm as soon as possible without processing of edges of greater weights.
In case you want to compute the number of MSTs, you may check an answer to how to compute the number of MSTs.

$\endgroup$
1
$\begingroup$

Let $G$ be a (simple finite) edged-weighted undirected connected graph with at least two vertices. Let ST mean spanning tree and MST mean minimum spanning tree. Let me define some less common terms first.

  • An edge is unique-cycle-heaviest if it is the unique heaviest edge in some cycle.
  • An edge is non-cycle-heaviest if it is never a heaviest edge in any cycle.
  • An edge is unique-cut-lightest if it is the unique lightest edge to cross some cut.
  • An edge is non-cut-lightest if it is never a lightest edge to cross any cut.
  • Two STs are adjacent if every ST has exactly one edge that is not in the other ST.
  • An MST is an isolated MST if it is not adjacent to another MST (when both MSTs are considered as STs).

When are there more than one minimum spanning tree?

To answer OP's question, here are five characterizations of $G$ that has more than one MST.

  • There are two adjacent MSTs.
  • There is no isolated MST.
  • There is an ST which is as light as or lighter than all adjacent STs and which is as light as one adjacent ST.
  • There is an edge which is neither unique-cycle-heaviest nor non-cycle-heaviest.
  • There is an edge which is neither unique-cut-lightest nor non-cut-lightest

The novelty of this answer is mostly the last two characterizations. The second from last characterization can be considered as the very next step of the OP's approach. The first three characterizations together can be considered as a slightly enhanced version of dtt's answer.

It is easier to think in the opposite term, whether $G$ has a unique MST. The following is the opposite and equivalent version of the above characterizations.

When is the minimum spanning trees unique?

Theorem: the following properties of $G$ are equivalent.

  • Uniqueness of MST: There is a unique MST.
  • No adjacent MST: there is no adjacent MSTs.
  • One isolated MST: there is an isolated MST.
  • One local minimum ST: there is an ST which is lighter than all adjacent STs.
  • Extreme cycle edge: every edge is either unique-cycle-heaviest or non-cycle-heaviest.
  • Extreme cut edge: every edge is either unique-cut-lightest or non-cut-lightest

Here comes my proof.

"Uniqueness of MST" => "No adjacent MST": obvious.

"No adjacent MSTs" => "One isolated MST": obvious.

"One isolated MST" => "One local minimum ST": An isolated MST is lighter than all adjacent STs.

"One local minimum ST" => "Extreme cycle edge": Let $m$ be an ST that is lighter than all adjacent STs.

  • Every edge in $m$ must be non-cycle-heaviest. Here is the proof. Let $l$ be an edge in $m$. If $l$ does not belong to any cycle, we are done. Now suppose $l$ belongs to a cycle $c$. If we remove $l$ from $m$, $m$ will be split into two trees, which will be named $m_1$ and $m_2$. As a cycle that connects $m_1$ and $m_2$ with $l$, $c$ must have another edge that connects $m_1$ and $m_2$. Name that edge $l'$. Let $m'$ be the union of $m_1$, $m_2$ and $l'$, which must be a spanning tree of $G$ as well. Since $m$ and $m'$ are adjacent, $m$ is lighter than $m'$. That means, $l$ is lighter than $l'$. So $l$ is non-cycle-heaviest.
  • Every edge not in $m$ must be unique-cycle-heaviest. Here is the proof. Let $h'$ be an edge not in $m$. If we add $h'$ to $m$, we will create a cycle $c$. Let $h$ be an edge in $c$ that is not $h'$. Consider the spanning tree $m'$ made from $m$ with $h$ replaced by $h'$. Since $m$ and $m'$ are adjacent, $m$ is lighter than $m'$. That means, $h$ is lighter than $h'$. So $h'$ is the unique heaviest edge in $c$. That is, $h'$ is unique-cycle-heaviest.

"Local minimum ST" => "Extreme cut edge": Proof is left as an exercise.

"Extreme cycle edge" => "Uniqueness of MST": Let $m$ be an MST. Let $e$ be an arbitrary edge. If $e$ is non-cycle-heaviest, $m$ must contain it. If edge $e$ is unique-cycle-heaviest, $m$ cannot contain it. (These two propositions can be proved by the standard reasoning about MST using cycle and edge exchange, similarly to what have been done just above). Hence $m$ is exactly the set of non-cycle-heaviest edges.

"Extreme cut edge" => "Uniqueness of MST": Proof is left as an exercise.

The above chains of implications proves the theorem.

Once again, the novelty of this answers is mostly the "extreme cycle edge" property and the "extreme cut edge" property, which uses the concepts, non-cycle-heaviest and non-cut-lightest. I have not seen those concepts elsewhere, although they are quite natural.


Here are two related interesting observations.

  • For any edge $e$, $e$ is non-cycle-heaviest $\Leftrightarrow$ $e$ is unique-cut-lightest $\Leftrightarrow$ $e$ is in every MST
  • For any edge $e$, $e$ is unique-cycle-heaviest $\Leftrightarrow$ $e$ is non-cut-lightest $\Leftrightarrow$ $e$ is not in any MST

Two sufficient but not necessary conditions for unique MST

the uniqueness of the heaviest edge in every cycle implies the "extreme cycle edge" property. So it is a sufficient condition. A counterexample to its being necessary condition is the graph with weights $ab\rightarrow 1, bc\rightarrow 1, cd\rightarrow 1, da\rightarrow 2, ac\rightarrow 2$.

the uniqueness of the lightest edge in every cut-set implies the "extreme cut edge" property. So it is a sufficient. A counterexample to its being necessary condition is a triangle with weights $1,1,2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.