在不影响图的最小生成树的情况下添加尽可能轻的边？
Adding the lightest possible edges without affecting the graph's minimum spanning tree?
我们有一个图 G 并希望在每个顶点对之间添加边，这些边尽可能轻而不影响最小生成树。
给定最小生成树和一对顶点，如何计算在不影响 MST 的情况下可以添加到它们之间的最轻边的权重？
我认为添加一条比两个顶点所具有的其他所有边都重的边会起作用，但在我进行的试验中它似乎是错误的。
生成树的边数由顶点数决定。因此，如果向 MST 添加一条边，则需要删除另一条边才能获得生成树。但是，您不能删除任何边缘。显然，删除不在两个顶点之间的路径上的边会断开图形。因此，您只能删除这条路径上的一条边。如果你想找到最小生成树，你当然会删除最重的边。
当且仅当新边的权重大于旧路径上最重的边权重时，这棵新的生成树比原来的生成树重。因此，新边必须比这条边重，才能保持原来的MST。
只是重新捕捉并用我自己的话解释（接受答案后）：
找到 v 和 u 之间新添加的边 e 的最小权重（图 G 中的顶点），这样它就不会提高（ lighten) G的最小生成树的权重，做如下：
- 在树上找到
v和u之间的路径（这样的路径只有一条）。
- 找到该路径上最重的边。
- 使新添加的边与该重量一样重或更重。
这不会影响树的总重量。
我们有一个图 G 并希望在每个顶点对之间添加边，这些边尽可能轻而不影响最小生成树。 给定最小生成树和一对顶点，如何计算在不影响 MST 的情况下可以添加到它们之间的最轻边的权重？
我认为添加一条比两个顶点所具有的其他所有边都重的边会起作用，但在我进行的试验中它似乎是错误的。
生成树的边数由顶点数决定。因此，如果向 MST 添加一条边，则需要删除另一条边才能获得生成树。但是，您不能删除任何边缘。显然，删除不在两个顶点之间的路径上的边会断开图形。因此，您只能删除这条路径上的一条边。如果你想找到最小生成树，你当然会删除最重的边。
当且仅当新边的权重大于旧路径上最重的边权重时，这棵新的生成树比原来的生成树重。因此，新边必须比这条边重，才能保持原来的MST。
只是重新捕捉并用我自己的话解释（接受答案后）：
找到 v 和 u 之间新添加的边 e 的最小权重（图 G 中的顶点），这样它就不会提高（ lighten) G的最小生成树的权重，做如下：
- 在树上找到
v和u之间的路径（这样的路径只有一条）。 - 找到该路径上最重的边。
- 使新添加的边与该重量一样重或更重。
这不会影响树的总重量。