0

假设 e 是加权图中的一条边,它与顶点 v 相关,使得 e 的权重不超过与 v 相关的任何其他边的权重。证明存在包含该边的最小生成树。

4

1 回答 1

0

矛盾证明

假设存在一个顶点 v,使得 MST 不使用其最小权重边 e,而是使用另一个入射边,我们称其为 x。现在,假设我们将边 e 添加回 MST,从而形成一个循环。我们现在可以删除该循环中使用的前一个边 x。此时,我们有另一个 MST,其总成本低于之前找到的生成树。这是一个矛盾,因为如果边缘为 x 的生成树的成本高于边缘为 e 的生成树,那么它实际上并不是 MST。

于 2020-04-18T01:47:48.437 回答