限制性支撑树最大容量扩张问题  

The Maximum Capacity Expansion of Spanning Tree Problem with Constraints

作　　者：杨子兰 杨惠娟 李睿 Yang Zilan;Yang Huijuan;Li Rui(Department of Information,Lijiang Culture and Tourism College,Lijiang,Yunnan 674199,China;School of Mathematics and Statistics,Zhaotong College,Zhaotong,Yunnan 657000,China)

机构地区：[1]丽江文化旅游学院信息学院,云南丽江674199 [2]昭通学院数学与统计学院,云南昭通657000

出　　处：《大理大学学报》2023年第12期10-14,共5页Journal of Dali University

基　　金：国家自然科学基金项目(11126355);云南省教育厅科学研究基金项目(2017ZDX270;2022J1217);云南省地方本科高校基础研究联合专项资金项目(202301BA070001-092)。

摘　　要：限制性支撑树最大容量扩张问题(the maximum capacity expansion of spanning tree problem with constraints,MCESTC)是NP-难问题。针对MCESTC问题,采用允许增加支撑树长度值的双边替换策略设计了一个启发式算法进行求解,并证明了算法的正确性。最后,用实例阐述运用该算法求解问题的过程,从而验证算法的有效性。The maximum capacity expansion of spanning tree problem with constraints(MCESTC)is NP-hard.A heuristic algorithm is designed to solve it by allowing an increase in the length value of the spanning tree through bilateral substitution strategy,and the correctness of the algorithm is proved.Finally,an example is used to illustrate the process of applying the algorithm to solve the problem,thereby verifying the effectiveness of the algorithm.

关 键 词：通信网络 支撑树 树边替换 双边替换 完美匹配 

分 类 号：O157.6[理学—数学]