Application of Frequency Graph Based on Group Theory in the Traveling Salesman Problem
For the minimum spanning tree (MST) and travelling salesman problem (TSP),two kinds of special graphs in complete graph were introduced and the intersection operation for the graphs was defined.Each kind of special graphs and the intersection operation formed one semi-group.According to the proper-ty of semi-group,the frequency graph was computed.The frequency properties for edges in optimal Hamil-tonian cycle (OHC) and MST were analyzed.The lower frequency bound for the OHC edges was proven,and it greatly reduced the search space of OHC and decreased the hardness of TSP.Furthermore,the fre-quency properties for the OHC edges in frequency graphs were verified with some TSP instances.
semi-groupspecial graphfrequency graphtravelling salesman problemminimum spanning tree
万方数据
维普
