我们有一个图G，希望在每个顶点对之间添加尽可能轻的边，而不影响最小生成树。给定最小生成树和一对顶点，如何计算可以在不影响MST的情况下在它们之间添加的最轻边的权重?
本以为添加一条比这两个顶点的其他边都重的边会起作用，但在我进行的试验中似乎是错误的
生成树的边数由顶点数决定。因此，如果向MST添加一条边，则需要删除另一条边以获得生成树。然而，你不能移除任何边。显然，移除不在两个顶点之间路径上的边会断开图的连接。因此，您只能移除这条路径上的一条边。如果你想找到最小生成树，你当然要去掉最重的边。
如果新边的权值大于旧路径上最大边的权值，则新生成树比原生成树重。因此，为了保持原来的MST，新边必须比这个边重。
在接受了答案后，用我自己的话重新捕捉并解释一下:
要在v和u(图G中的顶点)之间找到新添加的边e的最小权值，使其不提高(减轻)G的最小生成树权值，请执行以下操作:
- 在树中查找
v和u之间的路径(只有一个这样的路径)。 - 查找路径上最重的边
- 使新添加的边与该边一样重或更重。
这不会影响树的总重量