0

我无法理解 MST 是否会是一棵树。

假设给定一个图 G = (V, E)，连接 V 中的所有顶点并具有最小总权重的边 T ⊆ E 的任何子集必须是一棵树，或者它可以是其他一些子图 - 有些边可能有负权重。- 所有的边都有正权重。

我在想，对于某些可能具有负权重的边，它必须是一棵树，而对于所有边都具有正权重的边，它可以是其他一些子图。

如果我是对的或错的，请帮助我。

如果一定是一棵树，你能解释一下连通性和极简性的矛盾吗？但是，如果您认为它可能是其他子图，那么您能否向我展示一个可能不是树的连通图的权重较低的示例。

4

3 回答 3

0

如果您有负权重，则不能保证最小跨度子图是一棵树。考虑一个由 3 个顶点组成的完整图，所有边的权重为 -1。

编辑有点误解了你的问题：

如果你有负权重：它可能不是一棵树

所有权重都是非负的（>=0）：有一个最小生成树，但可能还有另一个它不是树并且具有相同的权重总和。

所有权重都是正数 (>0)：它是一棵树。

于 2013-11-11T06:24:26.533 回答
0

最小生成树/森林 (MST/F) 和最小生成图 (MSG) 之间存在差异。

最小跨度图（MSG）：连接图 G 的所有连接组件中的所有节点，从而使总成本最小。

对于非负成本，MSF 等于 MSG。

例如，图 G 是一个三角形，每条边的成本为 1。MSG 将连接 2 条边上的 3 个顶点。这与使用 Kruskal、Prim 或 Boruvka 算法计算 G 得到的 MSF 相同。

对于负成本，MSF 可能不等于相应的 MSG，而且 MSG 并不总是 MSF。

例如，图 G 是一个三角形，每条边的成本为 -1。MSG 将使用每一个优势，因为它会降低整体成本。因此，您将获得一个循环。根据定义，一棵树或森林不包含循环。使用正成本，您将永远不会在 MSG 中获得循环，因为添加产生循环的边总是会增加 MSG 的总成本。用 Kruskal、Prim 或 Boruvka 计算 G 将返回一个 MSF。

于 2015-03-16T18:17:50.637 回答
-1

一些事实足以回答您的问题：

  1. 如果 T 是连接所有顶点的边的子集，则 T 不一定是树。
  2. 如果 T 是连接所有顶点的边的子集，并且 T 最小化权重之和，那么我们知道：
    • T 不一定是唯一的。
    • T 总是包含形成树的边的子集。（“连通性”）
    • 如果所有权重都严格为正，则 T 是一棵树。（“极简”）
  3. 找到一些权重总和最小的 T 就像找到一个 MST 一样容易：
    • 找到一些 MST（例如使用 Kruskal 或 Prim 算法）。
    • 添加所有具有负权重的边。

最小化权重的子集 T 的一个简单示例是图 G=(V,E)，其中所有边的权重为 -1，然后 T 为 E。

于 2013-11-11T09:17:55.483 回答