c++ - 数据结构中的 MST 和唯一性问题已解决 Ex？

Question

我准备参加博士入学考试。数据结构的老解题之一如下:

关于简单、无向、加权和连通图 G 的 MST，以下哪些说法是正确的？ (边缘权重不一定不同。)

1) 如果 G 中任意割之间的最轻边是唯一的，则 MST 是唯一的。

2)如果所有边的权重都不同，则MST是唯一的。

3) 如果 e=(u, v) 的权重等于 u 和 v 之间所有路径中的最大最轻边，则 e 在 MST 中。

答案:其中一个是正确的。

谁能详细解释一下，哪个是真的？为什么？有没有证据或者一定要举个例子或者反例？

Answer 1

我有一些链接，我会根据这些链接尝试回答您的问题，但我不是 MST 方面的专家。我认为这可以帮助您获得一些直觉，所以我发布了这个。

[编辑和更正。感谢@Niklas B. 指出我的错误]

1) 看这个here .查看第 3 页上的 (d) 数解决方案。它说 如果图中最亮的边是唯一的，则它必须是每个 MST 的一部分。

因此，根据定理，我们可以说，每个唯一的最轻边都必须属于每个 MST。根据问题，据说 任何切割之间的最轻边都是唯一的。因此，MST 中的每条边都必须是最轻的。因此，MST 必须是唯一的。

2) 根据链接@Niklas B提供here ，您可以看到 如果每条边都有不同的权重，那么将只有一个唯一的最小生成树。 证明也在那里。所以我认为 2 是正确的。

3) 查看链接 here .如您所述，如果 e=(u, v) 的权重等于 u 和 v 之间所有路径中的最大最轻边，则 e 在 MST 中。让我们看一个示例.

我们要找到最小的最大权重边。。从 1 到 2 的最简单路径(即具有最小最大权重边的路径)是:1 > 3 > 4 > 2。因为最大边缘权重只有 2。但是如果我在图像上这样切割，你会看到最轻的边缘是 4。(即 e)。显然我们不能包括这个，因为它会违反 MST 的属性(property)。因此，3 不可能为真。

所以，我认为 1 和 2 都是正确的。我希望它有意义并对您有所帮助。