任意无向加权图K点连通扩充的逐次改善算法  

Optimizing recurrent algorithm for k-vertex-connected augmentation on arbitrary undirected weighted graph

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

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

出　　处：《辽宁工程技术大学学报（自然科学版）》2008年第1期82-84,共3页Journal of Liaoning Technical University (Natural Science)

基　　金：教育部博士学科点基金资助项目(2003005637)

摘　　要：为了对网络的可靠性寻求较好的近似算法,研究了任意无向不加权图情况下的极小K点连通扩充算法;在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理,并加以证明。最终推出了任意无向加权图K点连通最小扩充的逐次改善算法,应用该算法作了大量例题,得到比较满意的效果。为解决任意无向加权图最小扩充问题给出了一种新途径。The algorithm for K-vertex-connected minimal augmentation based on arbitrary undirected no-weighted graph is firstly researched. Then an efficient edge exchange approach is proposed,in which total weight value of graph G can be reduced under total edge of undirected weighted graph G and connected degree of each vertex kept constant.At the same time, the lemma of efficient edge exchange is given and proved. Finally, the optimizing recurrent algorithm for K-vertex-connected minimal augmentation on arbitrary undirected weighted graph is given. This algorithm is used in a large number of example, which proves that the results are satisfactory. So this is a new approach for solving minimal augmentation on arbitrary undirected weighted graph.

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

分 类 号：TN915[电子电信—通信与信息系统]