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

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

基于改进遗传算法的无向加权图的k点连通扩充

加权图的连通扩充问题已被证明是NP完全问题.作者提出一种改进遗传算法来解决无向加权图的k点连通扩充问题,通过改进遗传算法中的交叉和变异操作有效地改善了群体的效果,有助于搜索解空间中新的区域,能以较大概率搜索到全局最优.仿真结果表明,该算法在原来简单遗传算法上做了进一步改善,为解决加权图的扩充问题提供了新的方法.