任意无向加权图K点连通扩充的模拟退火算法

SIMULATED ANNEALING ALGORITHM FOR K-VERTEX-CONNECTED AUGMENTATION ON THE ARBITRARY UNDIRECTED WEIGHTED GRAPH

首先研究了任意无向不加权图情况下的极小K点连通扩充算法,在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理。最终推出了任意无向加权图K点连通最小扩充的模拟退火算法。

This paper firstly introduced algorithm for K-vertex-connected minimal augmentation under arbitrary undirected no-weighted graph ,and then gave an efficient edge exchanged approach ,in which total weight value of graph G could be reduced under total edge of undirected weighted graph G and connected degree of each vertex are constant. And the lemma of efficient edge exchange was given and proved. Finally, this paper gave simulated annealing algorithm for K-vertex-connected minimal augmentation on arbitrary undirected weighted graph.