1

这不是家庭作业。我正在尝试从教科书上做练习来理解MST (minimum spanning tree)。

假设我C在加权无向图中有一个循环G。据我了解，以下是正确的：

  • 中最重的边不C属于 的任何MST G。也就是说，没有G包含该边的 的 MST 。
  • 中最轻的边缘C属于. _ 也就是说，有一个 的 MST ，其中包含该边。GG

现在我想知道以下说法是否也正确。

  • 中最轻的边缘C属于 的所有MST G。也就是说，不存在不G包含该边的 MST 。
  • C除了最重的边缘之外，任何边缘都属于某个MST。也就是说，C除了最重的一条边之外，每条边都有一个包含该边的 MST。

你能证明最后的说法吗？

4

3 回答 3

1

你的第一个说法总是正确的。对于任何图形，最轻的边都在 MST 上。

第二个并不总是正确的。如果整个图是一个循环，则它总是正确的，因此每个节点都有 2 条与之相关的边。但是，在一般情况下，只要节点之间存在路径并且以总权(u,v)重 小于.kuvk

于 2012-12-15T11:49:40.113 回答
1

即使对于第一个声明，如果有多个最轻的边，也不需要将所有边都包含在 MST 中。

于 2012-12-15T13:25:24.577 回答
1

我不认为你的说法是有效的。问题是您只考虑更大图中的循环。

例如，考虑一个由循环中的 6 个节点组成的图 G（随机权重 >1）。您的声明可能适用于该图，但现在在图的中心添加 1 个节点并将其与成本为 1 的 6 个链接连接。整个图的 MST 现在将仅包含这 6 条边（形成星形）。

如果您现在查看您的声明，您会看到：

  • 您的周期中最轻的边缘不属于 MST (=star)
  • 循环中的所有边都不在 MST 中
于 2012-12-16T09:59:46.990 回答