Graph Has Two / Three Different Minimal Spanning Trees ?

Question

I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal spanning trees. The naive solution that I've though about is running Kruskal's algorithm once and finding the total weight of the minimal spanning tree. Later , removing an edge from the graph and running Kruskal's algorithm again and checking if the weight of the new tree is the weight of the original minimal spanning tree , and so for each edge in the graph. The runtime is O(|V||E|log|V|) which is not good at all, and I think there's a better way to do it.

Any suggestion would be helpful, thanks in advance

Gerena

Don't cross-post questions. If you believe that a question is off topic, you can delete it if it doesn't have any answers and re-ask it on the appropriate site, or you can flag it requesting for it to be migrated. But this question is probably fine here. – Who

Answer 1

You can modify Kruskal's algorithm to do this.

First, sort the edges by weight. Then, for each weight in ascending order, filter out all irrelevant edges. The relevant edges form a graph on the connected components of the minimum-spanning-forest-so-far. You can count the number of spanning trees in this graph. Take the product over all weights and you've counted the total number of minimum spanning trees in the graph.

You recover the same running time as Kruskal's algorithm if you only care about the one-tree, two-trees, and three-or-more-trees cases. I think you wind up doing a determinant calculation or something to enumerate spanning trees in general, so you likely wind up with an O(MM(n)) worst-case in general.

Godfree

"I think you wind up doing a determinant calculation" Yep. – Provencher

"Take the product over all weights and you've counted the total number of minimum spanning trees in the graph." I don't see what the values of the weights of the edges have to do with the number of MSTs. If I add some constant c to all edge weights, I don't change the number of MSTs since I don't change which sets of edges form an MST, but the product over the weights changes. I also don't understand what you mean by "irrelevant edges". – Choosey

Thanks for the answer , but what do you mean by irrelevant edges ? – Gerena

@Itamar Edges e for which there exists a path from one endpoint of e to the other on edges strictly lighter than e. This can be tested by making some extra find() calls before any of the edges in a weight class have their endpoints united. – Provencher

@DavidEisenstat , checking if any edge e is relevant makes the whole run time much more expesnsive , doesn't it ? – Gerena

@Itamar Only by a constant factor. Scan the edges in weight classes. For each weight w, process the edges of weight <w first. For each edge of weight w, query its endpoints in the disjoint-set data structure; the edge is relevant iff its endpoints are in different sets. Proceed to unite the edges of weight w. Etc. We make two extra finds for each edge on top of the one union Kruskal calls for. – Provencher

@G.Bach: "Take the product over all weights" is slightly confusing... What it actually means is that, for each distinct edge weight (i.e. for each group of equal-weight relevant edges), we can calculate the number of spanning trees in the "component graph"; and we should then multiply all those numbers of MSTs (one per distinct edge weight) together to get the number of MSTs on the original vertices. – Kurd

Answer 2

Suppose you have a MST T0 of a graph. Now, if we can get another MST T1, it must have at least one edge E different from the original MST. Throw away E from T1, now the graph is separated into two components. However, in T0, these two components must be connected, so there will be another edge across this two components that has exactly the same weight as E (or we could substitute the one with more weight with the other one and get a smaller ST). This means substitute this other edge with E will give you another MST.

What this implies is if there are more than one MSTs, we can always change just a single edge from a MST and get another MST. So if you are checking for each edge, try to substitute the edge with the ones with the same weight and if you get another ST it is a MST, you will get a faster algorithm.

Singh

Answer 3

Suppose G is a graph with n vertices and m edges; that the weight of any edge e is W(e); and that P is a minimal-weight spanning tree on G, weighing Cost(W,P).

Let δ = minimal positive difference between any two edge weights. (If all the edge weights are the same, then δ is indeterminate; but in this case, any ST is an MST so it doesn't matter.) Take ε such that δ > n·ε > 0.

Create a new weight function U() with U(e)=W(e)+ε when e is in P, else U(e)=W(e). Compute Q, an MST of G under U. If Cost(U,Q) < Cost(U,P) then Q≠P. But Cost(W,Q) = Cost(W,P) by construction of δ and ε. Hence P and Q are distinct MSTs of G under W. If Cost(U,Q) ≥ Cost(U,P) then Q=P and distinct MSTs of G under W do not exist.

The method above determines if there are at least two distinct MSTs, in time O(h(n,m)) if O(h(n,m)) bounds the time to find an MST of G.

I don't know if a similar method can treat whether three (or more) distinct MSTs exist; simple extensions of it fall to simple counterexamples.

Peppel