我正在研究图论，我对最小生成树和最短路径树之间的联系有疑问。
让 G 是一个无向连通图，其中所有边都是加权的 不同的成本。让 Ť 成为MST G 然后让 Ť小号 是某个节点的最短路径树 小号。是 Ť 和 Ť小号 保证分享至少一个优势？
我相信这并非总是如此，但我找不到反例。有没有人有关于如何找到反例的建议？
我正在研究图论，我对最小生成树和最短路径树之间的联系有疑问。
让 G 是一个无向连通图，其中所有边都是加权的 不同的成本。让 Ť 成为MST G 然后让 Ť小号 是某个节点的最短路径树 小号。是 Ť 和 Ť小号 保证分享至少一个优势？
我相信这并非总是如此，但我找不到反例。有没有人有关于如何找到反例的建议？
我认为这个说法实际上就是这样 真正，所以我怀疑你能找到一个反例。
这是一个提示 - 获取图中的任何节点并找到该节点的最短路径树。现在考虑如果你跑步会发生什么 Prim的算法 从该节点开始 - 你能保证MST中至少有一条边可以进入最短路径树吗？
希望这可以帮助！
证明 到顶点 小号 和它的最短路径树 Ť小号，MST的楔子 Ť 是（小号， v），并假设它不存在 Ť小号 。然后必须有一个较短的路径 v 至 小号，路径中有一个顶点（因为w（小号， v）这不是最短的路径），这是假设的 p，并使 小号 - >p - >v，w（小号， v）> =路径（小号 - >p - >v）。删除w（小号， v）并添加w（小号， p） Ť ， 当所有边缘都是积极的和不同的，w（小号， p）<w（小号， v）。我们得到的最小生成树 Ť ”。
但 Ť 是一个MST.Here是矛盾。假设不成立，证明了这一点 Ť 和 Ť小号 必须分享至少一个边缘，它是w（小号， v在MST Ť。
如果有一个0成本的重量，情况是相似的。您可以假设w（a，b）= 0的两个顶点是相同的顶点，并删除其中一个顶点。 当权重为非负时，证明有效。
当一些权重为负和w（小号， p）> w（小号 ，v），即w（p ，v）<0，w（小号， v）> =路径（小号 - >p - >v）不能使w（小号， p）<w（小号， v）。但是在MST Ť，w（小号， v）也应该不存在，因为路径（小号 - >p - >v）使 小号 至 v 以更低的成本，替换w（小号， v）在T与w（小号， p）和w（p， v）如果有必要，使一个较小的生成树 Ť ”。仍然矛盾。