我正在研究图论，并且对最小生成树和最短路径树之间的关系有一个疑问。 让 G 是一个无向，连通的图，其中所有边的权重不同。设 T 是 G 的MST，并让 T s 成为某个节点的最短路径树取值即可。是 T 和 T s 保证共享至少一个边缘吗？
我相信这并非总是如此，但我找不到反例。有没有人有关于如何找到一个反例的建议？ em>，所以我怀疑你可以找到一个反例。
这里有一个提示 - 在图中找出一个节点并找到该节点的最短路径树。现在考虑如果您要从该节点开始运行 Prim算法，会发生什么情况 - 您能否保证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!
更多推荐
最小生成树和最短路径树总是会共享至少一条边？
发布评论