最小生成树和最短路径树是否总是至少有一条公共边？

Question

我正在学习图论，对于最小生成树和最短路径树之间的联系有疑问。

假设G是一张无向连通图，所有边都带有不同的权值。设T为G的最小生成树，T_s为某个节点s的最短路径树。这两棵树是否保证至少有一条公共边？

我认为这并非总是成立，但我找不到反例。是否有人能提供如何找到反例的建议？

- Spartacus

---

边缘权重必须是非负数吗？ - templatetypedef

是的，这总是成立的，因为与 s 相连的边中，连接到生成树的最短边也将成为最短路径树的成员。 - Tyler Durden

@TylerDurden 你怎么知道SPT中与s相邻的边之一也是MST中与s相邻的边之一？ - G. Bach

Answer 1

我认为这个陈述实际上是真的，所以我怀疑你能找到反例。

这里有一个提示 - 取图中的任何节点并为该节点找到最短路径树。现在考虑一下，如果你从该节点开始运行Prim's algorithm，是否可以保证至少一条MST边会进入最短路径树？

希望这可以帮助你！

- templatetypedef

---

我认为这个提示对证明或证伪该陈述没有帮助。如果我理解正确的话，它表明特定的MST集合和最短路径树集合总是共享一条边，并不意味着对于任何一般图的所有MST和最短路径树都是真实的。 - G. Bach

@G.Bach- 我的意图是这将是一个一般证明的大纲 - 从图中任意节点开始，先构建最短路径树，然后考虑从最短路径树的源节点开始 Prim 算法的第一步。由于边权值是唯一的，因此图中存在唯一的 MST，因此该证明适用于任意 MST。由于我们假设了任意最短路径树，因此该证明也适用于任意最短路径树。或者我漏掉了什么吗？ - templatetypedef

@templatetypedef 你的意思是Prim算法从s开始选择的第一条边也会在从s开始的任何最短路径树中吗？ - G. Bach

@BlueRaja-DannyPflughoeft- MST 没有固定的根节点 - 它们是全局唯一的。由于所有边权重都不同，图中只有一个 MST，因此如果我们运行任何算法来查找 MST，我们将保证得到相同的 MST。因此，我可以说通过在源节点 s 开始运行 Prim 算法创建的 MST 是全局 MST，所以我可以对以这种方式生成的 MST 提出的任何声明都是通用的。 - templatetypedef

啊，我错过了边缘权重是不同的这个事实。如果不是所有的边缘权重都不同，那么这个答案是否仍然正确呢？ - BlueRaja - Danny Pflughoeft

Answer 2

证明：对于顶点s及其最短路径树T_s，MST中的楔形图为w(s, v)，假设它不存在于T_s中。那么从v到s必然存在一条更短的路径，并且路径上有一个顶点（因为w(s, v)不是最短路径），假设为p，使得s->p->v，w(s, v) >= path(s->p->v)。在所有边都为正数且不同的情况下，删除w(s, v)并添加w(s, p)到T中，w(s, p) < w(s, v)，我们得到一个更小的最小生成树T '。

但是T是MST，这里有矛盾。假设不成立，这证明了T和T_s必须共享至少一条边，并且在MSTT中它是w(s, v)。

如果有一个权重为0的边，则情况类似。可以假设w(a，b) = 0的两个顶点是同一个顶点，并删除其中之一。当权重为非负数时，证明成立。

当一些权重为负数且w(s, p) > w(s，v)时，即w(p，v) <0，w(s, v) >= path(s->p->v)无法使w(s, p) < w(s, v)。但在MSTT中，w(s, v)也不应存在，因为path(s->p->v)以更小的代价使得s到v，用w(s, p)和w(p, v)替换T中的w(s, v)，如果需要，可以得到一个更小的最小生成树T '。仍然矛盾。

- vvy