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

Question

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

1. G 的每个 MST 是否都包含最小加权边？
2. G 是否存在不包含最大加权边的 MST？

另外，如果有人能给出一些在处理此类 MST 问题时必须牢记的关键事项的提示，我会更加感激。

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

Answer 1

G是否存在不包含最大加权边的MST？

可能有，但不一定有。考虑如下 4 顶点图：

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

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

G的每个MST是否包含最小加权边？

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

此外，如果有人能够提示处理此类 MST 问题时必须牢记的关键事项，我会更加感激。

最好的选择是使用 MST 的一般属性来推理事物，并尝试构建您认为可以证明您的情况的具体反例。我对上面的每条推理都给出了一个例子。由于剪切和循环属性，您始终可以准确确定哪些边在 MST 中，因此您可以系统地测试每条边以确定它是否在 MST 中。

Answer 2

G的每个MST是否包含最小加权边？

是的。假设我们有一个不包含最小权重边的 MST。现在，将此边包含到 MST 将导致一个循环。现在循环中总会有另一条边，可以将其删除以删除循环并仍然保持图（MST）连接。

G是否存在不包含最大加权边的MST？

取决于图表。如果图本身是一棵树，那么我们需要将其所有n-1边包含在MST中，因此最大权重边不能被排除在外。此外，如果最大权重边是切边，因此排除它永远不会导致连通性，则不能排除最大权重边。但如果最大权重边缘是循环的一部分，则可以从MST中排除。

Answer 3

对于你的第一个问题，答案是否定的，kruskal 算法证明了这一点。它将始终选择最小成本边。

对于第二个问题，答案是肯定的，找到一个示例图很简单：

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

第三条边永远不会被选择，因为它引入了一个循环。所以基本上，如果成本最大的边插入到 MST 中会产生一个循环，那么它就不会被插入。

Answer 4

我看你也正在通过2009年的CSC263考试学习？ （这里也一样！）

查看最小值始终位于 MST 中的另一种方法是简单地查看这个最小边（称之为 e）：

<前><代码> e
v1 ---------------- v2

（假设这与其他顶点有连接）。现在，e 不包含在最终 MST 中意味着在不失一般性的情况下，我们在某个时刻有 v1 在 MST 中，但没有 v2。然而，添加 v2 而不添加 e 的唯一方法是说添加 v1 不会将 e 添加到队列中（因为根据定义，e 将位于队列顶部，因为它具有最低优先级），但是这个与 MST 构造定理相矛盾。

因此，本质上，不可能有一条具有最小权重的边不进入队列，这意味着构建的任何 MST 都会拥有它。