如何证明无向图的最大生成树包含图中任意两个顶点A和B之间最宽的路径？
我已经尝试通过编辑来考虑 Kruskal 算法的证明，因此它会产生最大生成树，但我不明白为什么最大生成树必须包含最宽路径中的边，尤其是在有多个最宽路径的情况下。
最佳答案
关于最优性的证明通常是矛盾的。在这里，您可以通过说
Suppose there are vertices A and B with a widest path between them containing at least one edge not in any maximum spanning tree of the graph.
现在您必须证明这样一条边的存在会导致所需的矛盾。一个明确的路径是表明这条边可用于构建权重大于图中任何最大生成树的新生成树。因此，它们毕竟不是最大值。
矛盾的存在表明从 A 到 B 的假设最宽路径不存在。因此，证据就在眼前。
关于algorithm - 最宽路径算法正确性证明，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37711190/