更改为图中的非MST边缘以更改MST [英] Change to non-MST edge in graph to change MST

问题描述

设计一个采用加权图G的算法，并找到
成本中最小的非MST边的变化，这会导致G的
最小生成树发生变化。

到目前为止，我的解决方案（需要建议）：

要更改MST ，我们需要改变非MST边缘st的权重它比MST中它的起始顶点和结束顶点的路径中的最大边缘小一些。

所以我们可以从MST的边缘开始，每个顶点检查是否存在非MST边缘。如果有，可以完成一个bfs到达边缘的终点（在MST中）。非MST边缘权重必须更新为小于路径中最大边缘权重的值。

这将导致非MST边缘包含在MST中和以前的最大边缘将从MST中删除。

有人可以告诉我们这个解决方案是否正确吗？谢谢。

解决方案

您发现了这个想法。
但是，您的答案需要进行调整，以表明您希望找到最低限度的更改，而不是要修改您在步行中遇到的每个非MST边缘。

如果这是一个学校问题，您也将被要求提供一个正确性证明。为了构建它，我建议依靠克鲁斯卡尔的证明，并解释为什么你的改变会让克鲁斯卡尔选择修改的边缘，而不是从路径上的其他最大权重边缘。

Devise an algorithm that takes a weighted graph G and finds the smallest change in the cost to a non-MST edge that would cause a change in the minimum spanning tree of G.

My solution so far (need suggestions):

To make a change to the MST, we need to change the weight of a non-MST edge s.t. it is one less than the maximum edge in the path of its start vertex and end vertex in the MST.

So we can start by walking the edges of MST, and for every vertex, check if there is a non-MST edge. If there is, a bfs to reach the edge's end point (in the MST) can be done. The non-MST edge weight must be updated to one less than the maximum edge weight in the path.

This would cause the non-MST edge to be included in the MST and the previous maximum edge to be removed from MST.

Can someone tell if this solution is correct ? Thanks.

解决方案

You found the idea. However, your answer needs to be tuned to show that you want to find the minimum change and not that you want to modify each non-MST edge you come across in your walk.

If this is a school question, you will also be asked to provide a proof of corectness. in order to build it, I would suggest to rely on Kruskal's proof, and to explain why your change would have Kruskal choose the modified edge instead of that other max-weight edge from the path.

这篇关于更改为图中的非MST边缘以更改MST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！