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

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

作　　者：王永德[1] 孙雨耕[2] 

机构地区：[1]青岛理工大学自动化工程学院,山东青岛266033 [2]天津大学电气与自动化工程学院,天津300072

出　　处：《计算机应用与软件》2007年第4期54-55,共2页Computer Applications and Software

基　　金：教育部博士学科点基金资助项目No.2003005637。

摘　　要：首先研究了任意无向不加权图情况下的极小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.

关 键 词：模拟退火算法 无向加权图 K点连通扩充 边交换 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]