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

问题描述

我正在研究图论，并且对最小生成树和最短路径树之间的关系有一个疑问。 让 s 成为某个节点的最短路径树取值即可。是 T 和 T s 保证共享至少一个边缘吗？

我相信这并非总是如此，但我找不到反例。有没有人有关于如何找到一个反例的建议？ em>，所以我怀疑你可以找到一个反例。

这里有一个提示 - 在图中找出一个节点并找到该节点的最短路径树。现在考虑如果您要从该节点开始运行，会发生什么情况 - 您能否保证MST中至少有一条边会进入最短路径树？

希望这有助于您！

I'm studying graph theory and I have a question about the connection between minimum spanning trees and shortest path trees.

Let G be an undirected, connected graph where all edges are weighted with different costs. Let T be an MST of G and let Ts be a shortest-path tree for some node s. Are T and Ts guaranteed to share at least one edge?

I believe this is not always true, but I can't find a counterexample. Does anyone have a suggestion on how to find a counterexample?

解决方案

I think that this statement is actually true, so I doubt you can find a counterexample.

Here's a hint - take any node in the graph and find a shortest path tree for that node. Now consider what would happen if you were to run Prim's algorithm starting from that node - can you guarantee that at least one edge from the MST will find its way into the shortest path tree?

Hope this helps!

这篇关于最小生成树和最短路径树总是会共享至少一条边？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！