0

如果给定一个连通图 G，则将该图拆分为 Ga 和 Gb。如果你找到 Ga 和 Gb 的最小生成树（分别称为 Xa 和 Xb），用最小加权边连接 Xa 到 Xb 是否仍然形成生成树？那棵生成树是最小生成树吗？

到目前为止，这是我的逻辑。我相信几乎按照定义，将 Xa 连接到 Xb 至少会形成一棵生成树。（如果有一个反例会有所帮助）但是，我认为它不会总是形成最小生成树，因为根据图形的结构，您可能能够从 Xa 或 Xb 中删除一条边，然后添加连接它们的边缘，仍然有一棵树。在具有相同权重的多条边在不同顶点处连接 Xa 和 Xb 的情况下，可能会出现这种情况。

到目前为止我的逻辑正确吗？

4

2 回答 2

1

这是正确的，您并不总是通过连接 Xa 和 Xb 来获得最小生成树。但是，连接 Xa 和 Xb 的边没有必要具有相同的权重。请参见以下示例：

假设您有以下图 G：

A-B-C-D 
| | | | 
E-F-G-H

边 (B,C) 的成本为 1，(F,G) 的成本为 2，所有其他边的成本为 10。

然后将其划分为 Ga 和 Gb：

A-B   C-D 
| |   | | 
E-F   G-H

最小生成树 Xa 和 Xb 是：

A-B   C-D 
|       | 
E-F   G-H

如果您现在将它们与可能的最小边连接起来，您将获得成本为 61 的生成树：

A-B-C-D 
|     | 
E-F G-H

但这不是最小生成树。最小生成树（成本为 53）将是

A-B-C-D 
|       
E-F-G-H
于 2012-04-01T22:34:28.480 回答
0

不完全的。您应该假设一个解决方案并逆向设计一个反例。例如，假设对于图 G，最小生成树是 X。

  • 如果您拆分图形以便只穿过 X 一次，那么最小加权边必然是被移除的边，因此您无法构建反例。
  • 但是，如果您的分区在两个地方切割树，您就有一个反例。您断言您只需要添加一个边，但是通过构造，您在两个位置切割了最佳树，因此您需要添加两条边来重建最佳树（并且您的一个中还有一个无关的边分区）。（有关这方面的一个非常清楚的示例，请参见 seckl 的答案。）

您的第一个主张（“我相信根据定义，将 Xa 连接到 Xb 至少会形成一棵生成树。”）是正确的；您可以使用有关树的一些事实来证明它：具有 N 个节点和 N-1 条边的全连接图是一棵树，而树是具有 N 个节点和 N-1 条边的全连接图（不能形成循环）。或者您可以使用来自http://en.wikipedia.org/wiki/Tree_(graph_theory)#Definitions的等效条件

于 2012-04-01T22:32:47.620 回答