| 任意无向加权图K点连通扩充的模拟退火算法 |
| |
| 引用本文： | 王永德,孙雨耕. 任意无向加权图K点连通扩充的模拟退火算法[J]. 计算机应用与软件, 2007, 24(4): 54-55 |
| |
| 作者姓名： | 王永德 孙雨耕 |
| |
| 作者单位： | 青岛理工大学自动化工程学院,山东,青岛,266033;天津大学电气与自动化工程学院,天津,300072 |
| |
| 基金项目： | 高等学校博士学科点专项科研项目 |
| |
| 摘 要： | 首先研究了任意无向不加权图情况下的极小K点连通扩充算法,在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理.最终推出了任意无向加权图K点连通最小扩充的模拟退火算法.
|
| 关 键 词： | 模拟退火算法 无向加权图 K点连通 扩充 边交换 |
| 修稿时间： | 2006-05-24 |
SIMULATED ANNEALING ALGORITHM FOR K-VERTEX-CONNECTED AUGMENTATION ON THE ARBITRARY UNDIRECTED WEIGHTED GRAPH |
| |
| Wang Yongde,Sun Yugeng. SIMULATED ANNEALING ALGORITHM FOR K-VERTEX-CONNECTED AUGMENTATION ON THE ARBITRARY UNDIRECTED WEIGHTED GRAPH[J]. Computer Applications and Software, 2007, 24(4): 54-55 |
| |
| Authors: | Wang Yongde Sun Yugeng |
| |
| Affiliation: | 1. Automation School, Qingdao University of Technology, Qingdao 266033, Shandong, China; 2.School of Electrical and Automation Engineering, Tianjin University, Tianjin 300072, China |
| |
| Abstract: | 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. |
| |
| Keywords: | Simulated annealing algorithm Undirected weighted graph K-vertex-connected Augmentation Edge exchange |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
