关于 MST，下列选项中哪些选项是正确的？
Which of the following options are correct with respect to a MST?
我正在上Algorithms: Design and Analysis II课程，其中一题如下：
Consider a connected undirected graph with distinct edge costs. Which
of the following are true? [Check all that apply.]
- Suppose the edge is not the cheapest edge that crosses the cut (,). Then does not belong to any minimum spanning tree.
- Suppose the edge is the most expensive edge contained in the cycle . Then does not belong to any minimum spanning tree.
- The minimum spanning tree is unique.
- Suppose the edge is the cheapest edge that crosses the cut (,). Then belongs to every minimum spanning tree.
据我所知，所有四个选项都是正确的。选项 1、2 和 4 来自 Cut 属性；选项 3 是正确的，因为边权重不同。然而，包括选项 1 被证明是错误的。为什么？
- No
- Yes
- Yes
- Yes
这里的主要部分是回答#3。 For a graph with all distinct edge costs that is true. 您可以使用第三个问题的答案得出所有其他问题的答案。
对于#1：
A1 --- B1
|
A2 --- B2
假设w(A1,B1) > w(A2,B2)，但您仍然需要将它们都包含在MST中。
首先让我们看一下 mst definition.MST 是连接无向图的一个子集，它具有将所有顶点连接在一起的不同边成本，没有任何循环并且具有最小可能的总边权重。
1.If边e是唯一一条从A到B遍历不引起循环的路它可能属于mst.
2.If有环C那么我们不能说mst它会是一个闭环path.That是环的定义
3.If 如您所述，每条边都有不同的成本，那么只有一棵唯一的最小生成树。
4.It 可能不会，因为它会导致像 cycle 或 circuit 这样的循环，那么我们不使用该边从 A 遍历到 B
我正在上Algorithms: Design and Analysis II课程，其中一题如下：
Consider a connected undirected graph with distinct edge costs. Which of the following are true? [Check all that apply.]
- Suppose the edge is not the cheapest edge that crosses the cut (,). Then does not belong to any minimum spanning tree.
- Suppose the edge is the most expensive edge contained in the cycle . Then does not belong to any minimum spanning tree.
- The minimum spanning tree is unique.
- Suppose the edge is the cheapest edge that crosses the cut (,). Then belongs to every minimum spanning tree.
据我所知，所有四个选项都是正确的。选项 1、2 和 4 来自 Cut 属性；选项 3 是正确的，因为边权重不同。然而，包括选项 1 被证明是错误的。为什么？
- No
- Yes
- Yes
- Yes
这里的主要部分是回答#3。 For a graph with all distinct edge costs that is true. 您可以使用第三个问题的答案得出所有其他问题的答案。
对于#1：
A1 --- B1
|
A2 --- B2
假设w(A1,B1) > w(A2,B2)，但您仍然需要将它们都包含在MST中。
首先让我们看一下 mst definition.MST 是连接无向图的一个子集，它具有将所有顶点连接在一起的不同边成本，没有任何循环并且具有最小可能的总边权重。
1.If边e是唯一一条从A到B遍历不引起循环的路它可能属于mst.
2.If有环C那么我们不能说mst它会是一个闭环path.That是环的定义
3.If 如您所述，每条边都有不同的成本，那么只有一棵唯一的最小生成树。
4.It 可能不会，因为它会导致像 cycle 或 circuit 这样的循环，那么我们不使用该边从 A 遍历到 B