2

我正在尝试完成一些真/假问题。当我用 true 回答其中许多时，我开始担心... 请假设所有图表都是无向的并且没有不同的权重。负重应该没问题。

Qa) 如果 G 有一个具有唯一最重边 e 的循环，则 e 不能是任何 MST 的一部分。

我的回答是真的。例如，我们有一个包含节点 A、B、C、D、E 的图。

AB = 1
BC = 2
BD = 3
CD = 100
DE = 4

如您所见，BCD 是一个循环。我的论点是，既然它是一个循环，我们总是可以通过采取其他路线来避免独特的最重边缘 CD。因此这是真的。我的论点是否合理（足够）？

Qb) Dijkstra 算法计算的最短路径树必然是 MST。

我的回答是对的，但我的直觉告诉我出了点问题。嗯... Disjkstra 和 Prim 都是贪心算法。他们每次都选择最轻的加权边缘。是否存在最短路径树不是最小生成树的情况？我实际上很难理解这两个家伙之间的区别。

Qc) Prim 的算法适用于负加权边缘。

我的回答是真的。因为这就是 wiki 所说的...... :p 该算法是关于在所有边中找到成本最低的边。所以负加权边缘应该没关系，是吗？但是负加权循环呢？

Qd) 如果 G 有一个具有唯一最轻边 e 的循环，则 e 必须是每个 MST 的一部分。

我的回答是真的。我们必须访问 MST 中的所有节点。例如，在长度为 3 的循环中，我们总是可以用 2 步遍历该循环中的所有节点。如果有独特的最轻边缘，我们肯定会在 MST 中选择它。

我的主张合理吗？也许他们还不够？那么有什么建议吗？

4

2 回答 2

5

b) 的建议：你的直觉认为这是错误的，所以试着构建一个反例。如果你找到了，它就解决了，否则你通常可以通过分析你构建反例失败的原因来了解为什么一个主张是正确的。不过，我不会告诉你你的答案或直觉是否正确。

作业肯定早就到期了，所以答案：

Qa) 如果 G 有一个具有唯一最重边 e 的循环，则 e 不能是任何 MST 的一部分。

真的。T假设您有一个包含边缘的生成树e。如果e从树中移除边，您将得到一个包含两个非空连通分量 C1 和 C2 的图。循环中的至少一个其他边必须连接 C1 和 C2（否则它不会是循环）。让我们g成为这样的优势。通过删除和添加T'得到的树是一棵权重小于的生成树。因此不是 MST。TegTT

Qb) Dijkstra 算法计算的最短路径树必然是 MST。

我的回答是对的，但我的直觉告诉我出了点问题。

直觉是对的，那是错的。考虑

    6
  A---B
3 |   | 1
  C---D
    3

其中最短路径树是从 vertex 计算的A。最短路径树是

    6
  A---B
3 |
  C---D
    3

总重量为 12，但唯一的 MST 是

  A   B
3 |   | 1
  C---D
    3

重量为 7。

Qc) Prim 的算法适用于负加权边缘。

真的。从正权重的正确性中推断出这一点的一种方法是向所有边添加恒定权重W，以便所有边权重都是正的（例如W = 1 + max { |weight(e)| : e ∈ E }）。

由于具有V顶点的树总是有V - 1边，因此任何生成树的总权重在(V - 1)*W修改权重和未修改权重之间存在差异，因此当且仅当它是未修改边权重的树时，树是修改权重的 MST。

边的权重排序不会通过向所有权重添加常数来改变，因此 Prim 的算法以相同的顺序为修改后的边权重和未修改的权重构建相同的生成树。

通过对正权重的正确性，Prim 算法构造的具有修改权重的树是修改权重的 MST。

Qd) 如果 G 有一个具有唯一最轻边 e 的循环，则 e 必须是每个 MST 的一部分。

错误的。考虑

     1   1
   A---B---C
   |  / \  |
 1 | /4 5\ | 1
   |/  6  \|
   D-------E

该循环BDE具有唯一的最轻边BD，权重为 4，但 MST 不包含该循环的任何边。

但是，如果图中存在唯一的最轻边e ，则G它必须是每个 MST 的一部分。这与 a) 是双重的：考虑一个T不G包含e. 通过添加e，T我们获得了一个T'必须有循环的图（因为T是生成树而e不是T）。中的任何循环都T'必须包含e，否则将是 中的循环T。因此，选择任何循环C（T'恰好有一个，但这并不重要）并删除除efrom之外的任何边缘C。令结果图为T''。

总权重 otT''小于 的T，因为T''是T通过用较轻的边替换边获得的。T''是连接的（因为它是T'通过删除循环的边获得的），并且包含V顶点和V - 1边。因此它是一棵生成树，因此T不是最小的。

于 2011-10-29T12:15:50.500 回答
0

D 是真的。
Qd) 如果 G 有一个具有唯一最轻边 e 的循环，则 e 必须是每个 MST 的一部分。真的。

轻边缘 = 穿过切口的边缘，其重量是穿过切口的任何边缘的最小值。

现在让 T 是 G 的 MST。假设（出于矛盾的目的）T' 是 G 的不同 MST。由于 T 和 T' 不是同一棵树，并且它们都有 |V|–1 条边，因此存在T 中的某个边 e 不在 T' 中。从 T 中移除边 e 会导致（创建）G 的一个切割；因为 T 是一棵生成树，删除 e 会将 G 分成两个不相交的顶点集，它们一起包括 G 的所有顶点，这正是切割的含义。现在，由于 T 是一个 MST，边 e 必须是该切割上的（唯一）轻边，因此在每个 MST 中。但是通过构造，边 e 不在 T' 中。因此 T' 不是 MST，这与我们最初的假设相矛盾。

于 2012-10-18T07:41:11.603 回答