MST算法的重量变化

Question

鉴于上图和边缘权重，如果我们将边缘A-B的权重增加10.5，则在MST中将不再存在。

如果我们增加7.5或4.5或1.5-仍然会。为什么？我正在尝试自行解决这些问题。

谢谢。

Answer 1

Kruskal's algorithm，带有正确性的证据，意味着如果边缘的端点不能与重量相等或更轻的其他边缘连接，则边缘必须位于MST中；如果端点C0]，则边缘不得位于MST中可以与其他重量较小的边缘连接。

如果不使用边A-B，则最大权重最小的端点之间的路径将是A-E-G-B，最大权重为8。因此，如果A-B的成本小于8，则它将在MST中。如果成本大于8，则不会。

[请注意，如果您说如果将A-B的费用增加7.5，则它仍将属于MST，这是不正确的。这样一来，新费用将为8.5，并且将不包括在内。您可能要说的是，如果增加成本[[to 7.5。]，它将仍然存在于树中。