是否存在一个不包含最小/最大加权边的最小生成树？

Question

如果我们有一个（任意的）连通无向图G，其边缘具有不同的权重，

1.每个G的最小生成树是否包含最小权重的边？

2.G的最小生成树中是否存在不包含最大权重边的MST？

此外，如果有人可以给出处理这种MST问题时必须记住的关键事项的提示，我将更加感激。

这是一个作业问题。谢谢。

- Martin08

Answer 1

有没有不包含最大权重边的 G 的 MST？

可能会有，但不一定存在。考虑下面这个 4 个顶点的图：

[A]--{2}--[B]
 |         |
 |         |
{1}       {3}
 |         |
 |         |
[C]-{50}--[D]

最小生成树由边集{CA，AB，BD}组成。最大边权重为50，沿着{CD}，但它不是MST的一部分。但如果G已经等于自己的MST，则显然它将包含自己的最大边。

每个G的MST都包含最小加权边吗？

是的。 MST具有“切割属性”。 “切割”只是将图的顶点分成两个不相交集合的分区。对于您可以进行的任何切割，如果该切割中的边的权重小于切割中其他边的权重，则此边属于图中所有MST。因为您保证了边权重不同，所以还保证了存在一条边小于所有其他边。

此外，如果有人能给出处理这种MST问题时必须记住的关键要点的提示，我会更感激。

您最好使用MST的一般属性进行推理，并尝试构建特定的反例，以证明您的论点。我在上面给出了每行推理的实例。由于切割和循环属性，您始终可以确定哪些边在MST中，因此可以系统地测试每个边，以确定它是否在MST中。

- John Feminella

Answer 2

每个G的最小生成树(MST)都包含最小权重边吗？

是的。假设我们有一个不包含最小权重边的MST。现在将这条边包含到MST中会产生一个环。现在总会有另一条边在环中，可以被移除以消除环并仍然保持图（MST）连接。

G的最小生成树（MST）是否可能不包含最大权重边？

这取决于图形。如果图本身是一棵树，则需要包括其n-1条边在MST中，因此无法排除最大权重边。此外，如果最大权重边是切割边，使其排除将永远不会导致连通性，则无法排除最大权重边。但是，如果最大权重边是循环的一部分，则可以从MST中排除它。

- codaddict

Answer 3

关于您的第一个问题，答案是否定的，克鲁斯卡尔算法证明了这一点。它总是选择最小成本边。

对于第二个问题，答案是肯定的，并且很容易找到一个示例图：

1 - 2 (cost 10)
2 - 3 (cost 100)
3 - 1 (cost 1000)

第三条边永远不会被选中，因为它会引入一个循环。所以基本上，如果具有最大成本的边在插入MST时会创建一个循环，那么它就不会被插入。

- IVlad

Answer 4

我看到你也正在通过2009年的CSC263考试学习？（我也是！）

另一种证明最小值总在MST中的方法是简单地看这条最小边（称为e）：

          e 
v1 ---------------- v2

（假设这与其他顶点有连接）。 现在，为了使 e 不包括在最终的 MST 中意味着在某一点上我们有 v1 在 MST 中但没有 v2，而不失一般性。然而，只有通过说添加 v1 没有将 e 添加到队列中（因为根据定义，e 将位于队列的顶部，因为它具有最低的优先级），但这与 MST 构造定理相矛盾，才能添加 v2 而不添加 e。

因此，基本上是不可能有一个最小权重的边没有进入队列，这意味着任何构建的 MST 都将具有它。

- Michael Gorelick