algorithm - 最小生成树和最短路径树是否总是共享至少一条边？

Question

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

设G是一个无向的连通图，其中所有边都以不同的成本加权。令T为G的 MST，令T _s为某个节点s的最短路径树。是否保证T和T_至少共享一条边？

我相信这并不总是正确的，但我找不到反例。有人对如何找到反例有建议吗？

Answer 1

我认为这句话实际上是正确的，所以我怀疑你能找到一个反例。

这是一个提示 - 取图中的任何节点并为该节点找到最短路径树。现在考虑如果你从那个节点开始运行Prim 算法会发生什么——你能保证来自 MST 的至少一条边会进入最短路径树吗？

希望这可以帮助！

Answer 2

证明对于顶点s及其最短路径树Ts ，MST T中的楔形是w( _s , v )，假设它在Ts中不存在_。那么从v到s一定有一条较短的路径，并且路径中有一个顶点（因为 w( s , v ) 不是最短路径），假设为p，并使s -> p -> v , w( s , v ) >= 路径( s -> p -> v）。删除 w( s , v ) 并在T中添加 w( s , p ) ，当所有边都为正且不同时， w( s , p ) < w( s , v )。我们得到一个较小的最小生成树T '。

但是T是一个 MST。这是矛盾的。假设不成立，证明T和T _s必须共享至少一条边，并且它是MST T中的 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 )。但是在 MST T中，w( s , v ) 也不应该存在，因为 path( s - > p -> v ) 使s变为v降低成本，替换 w( s, v ) 在 T 中与 w( s , p ) 和 w( p , v ) 如有必要使 aa 的最小生成树T ' 更小。还是矛盾的。