我正在尝试回答一些对/错问题。当我用 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 中选择它。
我的主张合理吗？也许他们还不够？那么有什么建议吗？
对 b) 的建议：你的直觉告诉你这是错误的，所以尝试构建一个反例。如果你找到了一个，那就解决了，否则你通常可以通过分析你构建的反例失败的原因来了解为什么一个主张是正确的。不过，我不会告诉你你的答案或你的直觉是否正确。
\n作业肯定早就交了，所以答案是：
\n\n\nQa) 如果 G 具有一个具有唯一最重边 e 的环，则 e 不能是任何 MST 的一部分。
\n
真的。假设您有一个包含T边的生成树e。e如果从树中删除边，您将得到一个包含两个非空连通分量 C1 和 C2 的图。循环中至少有一个其他边必须连接 C1 和 C2（否则就不是循环）。让我们g成为这样的边缘。通过移除和添加T'得到的树是权值小于 的生成树。因此不是 MST。TegTT
\n\nQb) Dijkstra 算法计算出的最短路径树必然是 MST。
\n我的回答是对的，但我的直觉告诉我有些不对劲。
\n
直觉是对的，那是错的。考虑
\n 6\n A---B\n3 | | 1\n C---D\n 3\n其中最短路径树是根据顶点计算的A。最短路径树是
6\n A---B\n3 |\n C---D\n 3\n总权重为12，但唯一的MST是
\n A B\n3 | | 1\n C---D\n 3\n重量为 7。
\n\n\nQc) Prim 的算法适用于负加权边。
\n
真的。从正权重的正确性推断出这一点的一种方法是向所有边添加恒定权重W，以便所有边权重都是正的（例如W = 1 + max { |weight(e)| : e \xe2\x88\x88 E }）。
由于具有顶点的树V总是有V - 1边，因此任何生成树的总权重在(V - 1)*W修改的权重和未修改的权重之间有所不同，因此当且仅当它是未修改的边权重的 MST 时，树才是修改权重的 MST。
通过向所有权重添加常量不会改变边的权重排序，因此 Prim 的算法以相同的顺序为修改的边权重和未修改的权重构建相同的生成树。
\n从正权重的正确性来看，Prim算法用修改后的权重构建的树是修改后的权重的MST。
\n\n\nQd) 如果 G 具有一个具有唯一最轻边 e 的循环，则 e 必须是每个 MST 的一部分。
\n
错误的。考虑
\n 1 1\n A---B---C\n | / \\ |\n 1 | /4 5\\ | 1\n |/ 6 \\|\n D-------E\n该循环BDE具有唯一的权重为 4 的最轻边BD，但 MST 不包含该循环的任何边。
e 但是，如果图中G存在唯一的最亮边，则它必须是每个 MST 的一部分。这与 a) 是对偶的：考虑一个不包含T的生成树。通过添加到，我们得到一个必须有环的图（因为是生成树而不是）。中的任何循环都必须包含，否则将是 中的循环。因此，选择中的任意一个循环（正好有一个循环，但这并不重要）并删除除 之外的任何边。设结果图为。GeeTT'TeTT'eTCT'eCT''
总权重 otT''小于 的总权重T，因为是通过用较轻的边替换边T''获得的。是连接的（因为它是通过删除循环的边获得的），并且包含顶点和边。因此它是一棵生成树，因此不是最小的。TT''T'VV - 1T