algorithm - 图有两个/三个不同的最小生成树？

Question

我试图找到一种有效的方法来检测给定的图 G 是否有两个不同的最小生成树。我还试图找到一种方法来检查它是否有 3 个不同的最小生成树。我考虑过的天真的解决方案是运行一次 Kruskal 算法并找到最小生成树的总权重。之后，从图中删除一条边并再次运行 Kruskal 算法，并检查新树的权重是否是原始最小生成树的权重，以及图中每条边的权重。运行时是 O(|V||E|log|V|) 这一点都不好，我认为有更好的方法来做到这一点。

任何建议都会有所帮助，在此先感谢

Answer 1

您可以修改 Kruskal 的算法来执行此操作。

首先，按权重对边缘进行排序。然后，对于每个权重升序，过滤掉所有不相关的边。相关边形成了一个关于最小跨度森林到目前为止的连接组件的图。您可以计算此图中的生成树的数量。取所有权重的乘积，您已经计算了图中最小生成树的总数。

如果您只关心一棵树、两棵树和三棵或更多棵树的情况，您将恢复与 Kruskal 算法相同的运行时间。我认为你最终会进行行列式计算或枚举生成树的东西，所以你可能最终会遇到 O(MM(n)) 最坏的情况。

Answer 2

假设您有一个T0图的 MST。现在，如果我们能得到另一个 MST T1，它必须至少有一个E与原始 MST 不同的边。抛开E，T1现在图形被分成两个部分。但是，在 中T0，这两个组件必须连接，因此这两个组件之间会有另一条边，其权重完全相同E（或者我们可以将权重更大的一个替换为另一个并获得更小的 ST）。这意味着用这个替代边缘E会给你另一个 MST。

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

Answer 3

假设 G 是一个有 n 个顶点和 m 个边的图；任意边 e 的权重为 W(e)；并且 P 是 G 上的最小权重生成树，权重为 Cost(W,P)。

令 δ = 任意两条边权重之间的最小正差。（如果所有边的权重都相同，则 δ 是不确定的；但在这种情况下，任何 ST 都是 MST，所以没关系。）取 ε 使得 δ > n·ε > 0。

当 e 在 P 中时，使用 U(e)=W(e)+ε 创建一个新的权重函数 U()，否则 U(e)=W(e)。计算 Q，即 G 在 U 下的 MST。如果 Cost(U,Q) < Cost(U,P) 则 Q≠P。但是通过 δ 和 ε 的构造，成本（W，Q）= 成本（W，P）。因此 P 和 Q 是 G 在 W 下的不同 MST。如果 Cost(U,Q) ≥ Cost(U,P) 则 Q=P 并且 G 在 W 下的不同 MST 不存在。

上面的方法确定是否存在至少两个不同的 MST，在时间 O(h(n,m)) 中，如果 O(h(n,m)) 限制了找到 G 的 MST 的时间。

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