图有2/3个不同的最小生成树？

Question

我正在尝试找到一种有效的方法来检测给定的图形 G 是否具有两个不同的最小生成树。我还在尝试找到一种方法来检查它是否有 3 个不同的最小生成树。我所讨论的天真解决方案是运行一次 Kruskal 的算法并找到最小生成树的总权重。稍后，从图中删除一条边并再次运行 Kruskal 算法，并检查新树的权重是否是原始最小生成树的权重，以及图中的每个边的权重。运行时为 O（|五||E|log|V|）这根本不好，我认为有更好的方法可以做到这一点。

任何建议都会有所帮助，提前感谢

Answer 1

假设G是一个有n个顶点和m条边的图；任何边e的权重是W（e）；并且P是G上的最小权重生成树，权值为成本（W， P）。

设δ =任意两个边权重之间的最小正差。(如果所有边的权重都相同，那么δ是不定的；但是在这种情况下，任何一个ST都是MST，所以没关系。)取ε使得δ

当e在P中时，用U(e)=W(e) ε创建一个新的权函数U()，否则U(e)=W(e)。计算Q，G在U下的MST . If Cost(U，Q)

上面的方法确定是否存在至少两个不同的 MST，如果 O（h（n，m）） 限定时间以找到 G 的 MST，则在时间 O（h（n，m）） 中。

我不知道类似的方法是否可以处理是否存在三个（或更多）不同的MST；它的简单扩展可以归结为简单的反例。

Answer 2

假设您有一个图的MST＜code＞T0＜/code＞。现在，如果我们可以得到另一个MST＜code＞T1＜/code＞，它必须至少有一个不同于原始MST的边缘＜code＞E＜/code>。从T1中去掉E，现在图形被分成两个部分。然而，在T0中，这两个组件必须连接，因此这两个部件之间将有另一条边，其权重与E完全相同（或者我们可以用另一条替换权重更大的一条，从而获得更小的ST）。这意味着用E替换另一条边。将为您提供另一个MST。

这意味着如果有不止一个MST，我们总是可以从一个MST改变一个边，得到另一个MST。因此，如果您正在检查每个边，请尝试用相同权重的边替换边，如果您得到另一个ST，它是一个MST，您将获得更快的算法。

Answer 3

你可以修改克鲁斯卡尔的算法来做到这一点。

首先，按权重对边进行排序。然后，对于升序的每个权重，过滤掉所有不相关的边。相关边形成了迄今为止最小生成林的连通分量的图。您可以计算此图中生成树的数量。对所有权重进行乘积，您已经计算了图中最小生成树的总数。

如果您只关心一棵树、两棵树和三棵或更多树的情况，则可以恢复与 Kruskal 算法相同的运行时间。我认为您最终会进行行列式计算或其他东西来枚举生成树，因此您通常可能会遇到 O（MM（n）） 最坏情况。