9

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

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

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

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

4

4 回答 4

8

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

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

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

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

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

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

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

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

于 2010-04-11T12:42:13.530 回答
6

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

是的。让我们假设我们有一个MST不包含最小权重边缘。现在将这个边缘包含到MST将导致一个cycle. 现在总会有另一条边cycle可以被移除以移除循环并仍然保持graph( MST)连接。

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

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

于 2010-04-11T12:44:46.020 回答
0

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

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

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

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

于 2010-04-11T12:43:50.550 回答
0

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

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

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

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

所以本质上，不可能有一个最小权重的边没有进入队列，这意味着任何构造的 MST 都会有它。

于 2010-04-12T13:16:49.540 回答