数据结构中的 MST 和唯一性问题已解决 Ex？
MST and Uniquness Problems in Data Structure old-solved Ex?
我准备参加 P.hD 入学考试。数据结构的老解题之一如下：
以下关于简单、无向、加权和连通图 G 的 MST 的说法正确的是？ （边权重不一定不同。）
1) 如果 G 中任何切割之间的最轻边缘是唯一的，则 MST 是唯一的。
2)如果所有的边权重不同，MST是唯一的。
3) 如果 e=(u, v) 的权重等于 u 和 v 之间所有路径中的最大最轻边，则 e 位于 MST.
答案：其中一个是正确的。
谁能解释的更清楚些，哪个是真的？为什么？有没有证据或者一定要举个例子或者反例？
我得到了一些 links 并且基于这些 links 我会尝试回答你的问题，但我不是 MST 的专家。我认为这可以帮助您获得一些直觉，所以我发布了这个。
[编辑和更正。感谢@Niklas B. 指出我的错误]
1) 见此 here。查看第 3 页上的 (d) 数字解决方案。它说 If the lightest edge in a graph is unique, then it must be part of every MST.
所以，根据定理，我们可以说，every unique lightest edge must belong to every MST。根据问题，据说 lightest edge between any cut is unique。因此，MST 中的每条边都必须是最轻的。因此，MST 必须是唯一的。
2)根据link@Niklas B提供的here,可以看出If each edge has a distinct weight then there will be only one, unique minimum spanning tree.证明也是那里。所以我认为2是真的。
3) 参见 link here. As you've stated, if the weights of e=(u, v) be equal to maximum lightest edge in all paths between u and v then e be in the MST. Let's look at an example here.
我们要找到 smallest maximum weight edge.。从 1 到 2 的最简单路径（即最大权重边最小的路径）是：1 > 3 > 4 > 2。因为最大边缘权重只有 2。但是如果我在图像上这样切割，你会看到最轻的边缘是 4。（即 e）。显然我们不能包含它，因为它会违反 MST 的 属性。因此，3不可能是真的。
所以，我认为 1 和 2 都是正确的。希望对你有所帮助。
我准备参加 P.hD 入学考试。数据结构的老解题之一如下：
以下关于简单、无向、加权和连通图 G 的 MST 的说法正确的是？ （边权重不一定不同。）
1) 如果 G 中任何切割之间的最轻边缘是唯一的，则 MST 是唯一的。
2)如果所有的边权重不同，MST是唯一的。
3) 如果 e=(u, v) 的权重等于 u 和 v 之间所有路径中的最大最轻边，则 e 位于 MST.
答案：其中一个是正确的。
谁能解释的更清楚些，哪个是真的？为什么？有没有证据或者一定要举个例子或者反例？
我得到了一些 links 并且基于这些 links 我会尝试回答你的问题，但我不是 MST 的专家。我认为这可以帮助您获得一些直觉，所以我发布了这个。
[编辑和更正。感谢@Niklas B. 指出我的错误]
1) 见此 here。查看第 3 页上的 (d) 数字解决方案。它说 If the lightest edge in a graph is unique, then it must be part of every MST.
所以，根据定理，我们可以说，every unique lightest edge must belong to every MST。根据问题，据说 lightest edge between any cut is unique。因此，MST 中的每条边都必须是最轻的。因此，MST 必须是唯一的。
2)根据link@Niklas B提供的here,可以看出If each edge has a distinct weight then there will be only one, unique minimum spanning tree.证明也是那里。所以我认为2是真的。
3) 参见 link here. As you've stated, if the weights of e=(u, v) be equal to maximum lightest edge in all paths between u and v then e be in the MST. Let's look at an example here.
我们要找到 smallest maximum weight edge.。从 1 到 2 的最简单路径（即最大权重边最小的路径）是：1 > 3 > 4 > 2。因为最大边缘权重只有 2。但是如果我在图像上这样切割，你会看到最轻的边缘是 4。（即 e）。显然我们不能包含它，因为它会违反 MST 的 属性。因此，3不可能是真的。
所以，我认为 1 和 2 都是正确的。希望对你有所帮助。