最小生成树灵敏度分析算法研究

Research on Sensitivity Analysis Algorithm of Minimum Spanning Tree

在最小生成树数学性质的基础上,给出最小生成树灵敏度分析算法.该算法在图的各种属性发生变化(如边的权值变化、增加或删除边或结点)的情况下,在原有最小生成树的基础上快速调整,而不是从头计算来得到新的最优解.算法还给出了每边权值在何范围内变化时,最优解不变.最后通过一个示例来说明算法的原理及应用.

Based on the mathematical properties of Minimum Spanning Tree（ MST）, a new MST algorithm for sensitivity analysis is presented. Without recomputing everything from scratch, the algorithm can quickly get a new MST from old MST when the graph subjects to discrete changes, such as additions or deletions of edges or vertices. The algorithm also can compute the allowable range of each edge＇s weight over which the current MST remains optimal. Finally, it provides a demonstration to explain the principle and application of the algorithm.