寻找高连通子图的近似算法

摘要

寻找高连通子图问题是一个属于在计算理论上非常困难，在实际中有广泛应用的急待解决的问题。本文从优化理论的数学模型方面对寻找边连通子图问题和点连通子图问题进行研究，并根据寻找高连通子图问题的特点构造了相应的近似算法。 关于寻找边连通子图问题，首先对简单的2－边连通子图问题提出了几种算法。以深度优先搜索为基础、利用最大生成树设计的深度优先算法，是最简明、最易操作的算法，运行速度很快。对复杂的图形，“D2”(Degree 2)算法首先对图形进行预处理，使图形简化，然后利用最大分支集进行求解，该算法的近似度较高。去边算法是与以上两种算法截然不同的方法，该算法采用去边思想，先将图形拆散，然后加点、去边得到2－边连通的生成子图。实验表明，该算法对简单图形有较好的效果。最后将深度优先算法与Nagamochi和Ibaraki提出的算法的思想相结合，得出了解决边连通子图问题的一种有效的近似算法。 关于寻找点连通子图问题，主要对寻找2－点连通子图问题提出了几种算法。基于2－边连通子图问题的深度优先算法，将处理技巧稍作改变得出了解决2－点连通子图问题的深度优先算法，并将该算法改进，提高近似度。本文也基于2－边连通子图问题的“D2”算法，利用相同的处理思路，稍做改变得出了解决2－点连通子图问题的近似算法。 本文最后进行了总结，并提出了有待进一步研究的问题。