确定给定的加权图是否具有唯一的MST [英] Determine if a given weighted graph has unique MST

问题描述

我正在寻找一种算法(或其他方法)来确定给定的加权图在O(ElogV)中是否具有唯一的MST(最小生成树)?

I'm looking for an algorithm (or any other way) to determine if a given weighted graph has unique MST (Minimum spanning tree) in O(ElogV)?

我对权重一无所知(例如weight(e1)！= weight(e2))，如果该图仅具有一个唯一的MST，则算法仅返回True；否则，则返回False.

I don't know anything about the weights (e.g. weight(e1) != weight(e2)), and the algorithm just return True if this graph has only one unique MST or False if not.

我首先使用Kruskal的算法，然后检查find-set(u)== find-set(v)，以便在MST中有一个圆圈，但是这种方式并不能涵盖我认为的所有情况:((

I started by using Kruskal's algo, and check if find-set(u)==find-set(v) so there is a circle in the MST, but this way does not cover all the scenarios as I thought :(

非常感谢！ 墨粉

推荐答案

您可以在O(E log(V))中证明它是否具有唯一的MST.

You can prove whether it has a unique MST in O(E log(V)).

首先用标准技术找到最小生成树.

First find a minimum spanning tree with standard techniques.

返回到原始树，然后将所有权重替换为数字对，原始权重，然后根据其是否在您发现的MST中来替换为0或1.这些数字对可以成对加在一起，也可以成对比较-就像普通数字一样.

Go back to your original tree, and replace all weights with pairs of numbers, the original weight, and then 0 or 1 based on whether or not it is in the MST you found. These pairs of numbers can be added together pairwise, and compared pairwise as well - just like normal numbers.

现在使用标准技术来查找具有这些有趣权重的最小生成树.您找到的MST将是与原始树共享最小边的MST.因此，如果有多个MST，则可以确保找到一个不同的MST.

Now use the standard techniques to find a minimum spanning tree with these funny weights. The MST that you find will be the MST which shares the least edges with your original tree. Thus if there are multiple MSTs, you are guaranteed to find a different one.

这篇关于确定给定的加权图是否具有唯一的MST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！