图形有两个/三个不同的最小生成树吗？

Question

我正在寻找一种有效的方法来检测给定图G是否有两个不同的最小生成树。我也在尝试找到一种方法来检查它是否有3个不同的最小生成树。我想到的一个朴素解法是先运行Kruskal算法，找到最小生成树的总权重。然后，从图中删除一条边，再次运行Kruskal算法，并检查新树的权重是否与原始最小生成树的权重相同，如此逐个检查每条边。这种方法的运行时间为O（|V||E|log|V|），效率不高，我认为应该有更好的方法。 任何建议都将有所帮助，谢谢！

- user975343

---

请勿在多个网站同时发布同一问题。如果您认为某个问题不适合当前网站，请先删除该问题（前提是该问题没有任何回答），然后在适当的网站重新提问，或者通过标记请求将其迁移。但是这个问题可能适合在这里提问。 - Bernhard Barker

Answer 1

你可以修改Kruskal算法来实现这一点。首先，按权重对边进行排序。然后，对于每个升序的权重，过滤掉所有不相关的边。相关的边在当前最小生成树森林的连接组成图中。您可以计算此图中跨越树的数量。对所有权重取乘积，就可以计算出图中所有最小生成树的总数。如果您只关心单树、双树和三树或更多的情况，那么您将恢复与Kruskal算法相同的运行时间。我认为您最终会执行一个行列式计算或类似的操作来枚举跨越树，因此通常情况下最坏情况下是O(MM(n))。

- tmyklebu

---

我认为你最终会进行行列式计算。[是的]（http://en.wikipedia.org/wiki/Kirchhoff's_theorem）。 - David Eisenstat

将所有权重的乘积，你就计算出了图中最小生成树的总数。我不明白边的权重值与最小生成树的数量有什么关系。如果我给所有边的权重加上一个常数c，我并不会改变最小生成树的数量，因为我没有改变哪些边集合形成了最小生成树，但是权重的乘积会发生变化。我也不明白你所说的“无关边”是什么意思。 - G. Bach

谢谢您的回答，但是您所说的“无关边”是什么意思？ - user975343

@Itamar 存在一些边 e，使得在比 e 权重更轻的边上，存在从 e 的一个端点到另一个端点的路径。为了验证这一点，在权重类别的任何边的端点联合之前，可以进行一些额外的 find() 调用。 - David Eisenstat

@Itamar 只有一个常数因子。按权重分类扫描边缘。对于每个权重w，首先处理权重<w的边缘。对于权重为w的每条边，查询其在不相交集数据结构中的端点；当且仅当其端点在不同集合中时，该边缘是相关的。继续联合权重为w的边缘。等等。除了Kruskal所要求的一个联合之外，我们还为每个边缘进行了两次额外的查找。 - David Eisenstat

Answer 2

假设您有一个图形的 MST T0。现在，如果我们可以得到另一个 MST T1，则它必须至少有一条边 E 与原始 MST 不同。从 T1 中删除 E，现在图形被分成两个组件。但是，在 T0 中，这两个组件必须连接，因此将存在横跨这两个组件的另一条边，其权重与 E 完全相同（或我们可以用另一条具有更大权重的边替换其中一条，并获得更小的 ST）。这意味着用 E 替换另一条边将给您另一个 MST。

这意味着，如果有多个 MST，则我们始终可以更改 MST 的单个边缘并获得另一个 MST。因此，如果您正在检查每个边缘，请尝试用与其重量相同的替代边缘替换边缘，如果您获得另一个 ST，则为 MST，您将获得更快的算法。

- zw324

Answer 3

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

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

创建一个新的权重函数U()，其中U(e)=W(e)+ε当e在P中时，否则U(e)=W(e)。计算G在U下的MST Q。如果Cost(U,Q) < Cost(U,P)，则Q≠P。但是由于δ和ε的构造，Cost(W,Q) = Cost(W,P)。因此，在W下，P和Q是G的不同MST。如果Cost(U,Q) ≥ Cost(U,P)，则Q=P，W下不存在不同的MST。

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

我不知道是否有类似的方法可以处理是否存在三个（或更多）不同的最小生成树；它的简单扩展会遇到简单的反例。

- James Waldby - jwpat7