Does the graph have two / three different minimal intermediate trees?

Question

I am trying to find an effective method for determining whether a given graph G has two different minimal spanning trees. I am also trying to find a method to check for the presence of three different minimal spanning trees. The naive solution I have is the Kruskal algorithm once and find the total weight of the minimum spanning tree. Later, removing the edge from the graph and running the Kruskal algorithm again and check whether the weight of the new tree is the weight of the original minimum spanning tree, and therefore for each edge in the graph. Runtime is O (| V || E | log | V |), which is not very good, and I think there is a better way to do this.

Any suggestion would be helpful, thanks in advance

Answer 1

You can change the Kruskal algorithm to do this.

First sort the edges by weight. Then, for each weight, filter out all irrelevant edges in ascending order. Corresponding edges form a graph on the connected components of the minimum pairing — the forest — so far away. You can count the number of spanning trees in this graph. Take the product over all the weights and you have calculated the total number of minimum spanning trees on the graph.

You restore the same runtime as the Kruskal algorithm if you only care about cases with one tree, two trees, and three or more trees. I think you are completing a determinant calculation or something to list the spanning trees as a whole, so you are likely to end up with the worst case O (MM (n)).

Answer 2

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

What does this mean if there is more than one MST, we can always change only one edge from the MST and get another MST. Therefore, if you check each edge, try replacing the edge with the same weight, and if you get another ST, this is MST, you will get a faster algorithm.

Answer 3

Let G be a graph with n vertices and m edges; that the weight of any edge e is equal to W (e); and that P is a tree with a minimum weight on G that weighs the cost (W, P).

Let δ = be the minimum positive difference between any two edge weights. (If all the weights of the edges are the same, then δ is indeterminate, but in this case any ST is MST, so it does not matter.) Take ε such that δ> n · ε> 0.

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

The method above determines if there are at least two different MSTs in time O (h (n, m)) if O (h (n, m)) limits the time spent by the MST of G.

I do not know if a similar method can handle the presence of three (or more) different MSTs; its simple extensions fall into simple counterexamples.