来源：期刊VIP网 时间：
作者：王永;
单位：华北电力大学新能源学院;
摘要：针对最小生成树(minimum spanning tree, MST)和旅行商问题(travelling salesman problem, TSP),介绍了完全图上的两类特殊图并定义了这些图上的交运算，每类特殊图和交运算构成一个半群。根据半群性质计算出频率图，分析了最优哈密顿圈(optimal Hamiltonian cycle, OHC)和MST中边的频率性质，证明了频率图上OHC中边的频率下界，该频率下界用于缩小OHC的搜索空间，降低了TSP的求解难度。此外，采用一些TSP算例验证了频率图上OHC中边的频率性质。
关键词：半群;;特殊图;;频率图;;旅行商问题;;最小生成树
基金资助：国家重点研发计划项目(2022YFE0207000)
