《寻找高连通子图的近似算法》由会员分享，可在线阅读，更多相关《寻找高连通子图的近似算法（67页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学硕士学位论文寻找高连通子图的近似算法姓名：刘芝梅申请学位级别：硕士专业：应用数学指导教师：曹炬华中科技大学硕士学位论文摘要寻找高连通子图问题是一个属于在计算理论上非常困难，在实际中有广泛应用的急待解决的问题。本文从优化理论的数学模型方面对寻找边连通子图问题和点连通子图问题进行研究，并根据寻找高连通子图问题的特点构造了相应的近似算法。关于寻找边连通子图问题，首先对简单的 2边连通子图问题提出了几种算法。以深度优先搜索为基础、利用最大生成树设计的深度优先算法，是最简明、最易操作的算法，运行速度很快。对复杂的图形，“D2”(Degree 2)算法首先对图形进行预处理，使图形简化，然后利用
2、最大分支集进行求解，该算法的近似度较高。去边算法是与以上两种算法截然不同的方法，该算法采用去边思想，先将图形拆散，然后加点、去边得到 2边连通的生成子图。实验表明，该算法对简单图形有较好的效果。最后将深度优先算法与 Nagamochi 和 Ibaraki 提出的算法的思想相结合，得出了解决 边连通子图问题（ 2 ）的一种有效的近似算法。关于寻找点连通子图问题，主要对寻找 2点连通子图问题提出了几种算法。基于 2边连通子图问题的深度优先算法，将处理技巧稍作改变得出了解决 2点连通子图问题的深度优先算法，并将该算法改进，提高近似度。本文也基于 2边连通子图问题的“D2”算法，利用相同的处理思路，稍
3、做改变得出了解决 2点连通子图问题的近似算法。本文最后进行了总结，并提出了有待进一步研究的问题。关键词：连通度生成子图近似算法深度优先搜索去边算法I华中科技大学硕士学位论文AbstractThe problem of finding highly connected subgraphs is an urgent problem that is verydifficult in computation theory, but has been widely used in practice. Two problems offinding edge-connected subgraphs and
4、vertex-connected subgraphs are studied from theaspects of mathematical model of optimization. According to the natures of finding highlyconnected subgraphs, several approximation algorithms are presented.First several algorithms are presented for the simple 2-edge-connected subgraphs. Basedon the id
5、ea of depth first search and by means of the maximum spanning tree, a depth firstalgorithm are presented. The algorithm is simple, manageable and fast. For the complexgraphs, “D2”(Degree 2) algorithm is effective. Do some preprocessing first, simplify thegraphs and make use of the maximum braches to
6、 obtain a solution. And the approximationration is improved. The removing-edge algorithm is absolutely different from the previoustwo. It introduces the idea of removing edges. It breaks up the original graph, then addsvertexes and removes edges to get 2-edge-connected spanning subgraphs. Experiment
7、shows it would be more effective for simple graphs. Finally, combining the depth firstalgorithm and the idea of the algorithm given by Nagamochi 和 Ibaraki, one effectivealgorithm for edge-connected subgraphs is obtained.Some algorithms are presented for 2-vertex-connected subgraphs. Based on the dep
8、th firstalgorithm for 2-edge-connected subgraphs, the depth first algorithm for 2-vertex-connected subgraphs is obtained by slight changes. And the algorithm is improved bysome changes to improving the approximation ration. Based on the “D2”algorithm for 2-edge-connected subgraphs, using the similar
9、 idea and approximation algorithm for 2-vertex-connected subgraphs is obtained.At last, all the works in this thesis are summarized and some prospects are proposed.Key words:ConnectivitySpanning SubgraphApproximation Algorithm Depth First SearchRemoving-edge AlgorithmII华中科技大学硕士学位论文1 绪论1.1 选题背景及其意义1.
10、1.1 寻找高连通子图的意义寻找高连通子图问题是图论的内容，也是网络优化最基本的问题，在车辆运输路线问题、各种通讯网路设计问题等方面有很重要的应用，例如可靠通信网络的构造。一个通信网络可模型化为一个图，图中的点代表通信站，边代表通信线路。这样图的点（边）连通度 k ( k )对应网络容许失灵的通信站（线路）数目的一个界限，即若有 k ( k )个通信站（线路）失灵可能会导致系统的通信中断，而少于 k ( k )个通信站（线路）失灵即可保证正常通信。换言之，图的连通度对应系统的可靠性。实际应用中，提高系统的可靠性往往要增加系统的成本和硬件的质量，因此如何构造在给定可靠性的条件下成本尽量低的系统，
11、自然就是人们要研究的问题。寻找给定连通度子图的应用，就是达到系统可靠，成本尽量低的目的123。1.1.2 寻找高连通子图问题的分类根据对连通度的不同要求，将寻找高连通子图的问题分为四类4：1)边连通度问题边连通度问题，就是在原无向图中找出一个边连通度为给定值 k 的最小生成子图，即 k 边连通生成子图。典型的应用就是网络构造时，设计一个满足给定可靠性且线路最少的网络。2)点连通度问题点连通度问题，就是在原无向图中找出一个点连通度为给定值 k 的最小生成子图，即 k 点连通生成子图。典型的应用就是网络构造时，设计一个满足给定可靠性且通信站（在通信网络中）最少的网络。3)强连通度问题强连通度问题，
12、就是在有向图中找出一个权重最小的任何两点都可以互相到达的问题，如交通网络的设计。4)连通度增加问题1华中科技大学硕士学位论文连通度增加问题，就是通过选择加入图中最少的边（点）来提高给定子图的边（点）连通度。典型的应用就是网络设计中，选择加入最少的线路（或通信站）来提高网络的可靠性。1.1.3 寻找高连通子图的复杂性尽管国内外大量学者很早就开始了寻找高连通子图问题的研究工作，但到目前为止，仍然没有获得令人满意的解决办法。这主要是问题本身的复杂性造成的。从计算复杂性角度来看，寻找高连通子图问题是属于计算机科学理论前沿领域的一类问题：NP 难题567。而对于 NP 难题，传统的理论和算法均有其局限性
13、，或者根本无法求解，或者其求解的计算量是爆炸的，即使用最快的计算机计算，所花的时间和费用也是人们不可接受的8910。虽然对寻找高连通子图问题的理论研究比较多，但在实际应用中还是很难消除程序误差。程序误差的存在，使实际应用中往往会出现这样的情况：将原始高连通图的权重做稍微改变，结果会大大不同；一个优化程序对某一个图效果相对较好，但对另一个图效果相对并不理想等。这些都是由高连通度问题本身的复杂性和算法本身所决定的11。从以上分析可知，很难设计一种算法，使之满足各种连通图和权重数据。所以，对于寻找高连通子图问题的研究，随然国内外学者都投入了大量的精力，但是由于NP 问题在理论上没有突破，所以对于寻找
14、高连通子图问题的研究也没有突破性进展。目前，主要是对于特定的某一类问题，研究相应的近似算法。1.1.4 寻找高连通子图的可行性在实际工作中，我们往往希望得到某个具体问题的最优化问题的精确解，一旦知道它是 NP 难题，那我们就不能很有效的解决这个一般问题。然而类似于寻找高连通子图这样的 NP 问题具有很重要的意义，经常会遇到。所以对于这类问题，有必要寻求有效的算法。目前，通常有两个研究途径1213：1.注意该问题是否过分一般性描述使我们忽视了问题的某些特殊性，或者说是否可以把问题限制得特殊一些，使我们能利用特殊性质有效地解决这个一般性问题的特例。2华中科技大学硕士学位论文这种研究方法是经典的。我
15、们证明某个问题是 NP 难题，然后又试图找出它的能有效求解的特别容易的特例。为了试图得到这样的特例，我们可以考虑某些常用的限制，如平面性、度有界、权限制等。有趣的是，我们并不总是幸运地发现这样容易的特例，即某些 NP 完全问题即使是受到很本质的限制仍保持 NP 完全性。在这种 NP 完全性证明中，局部替换是一种常用的手段。2.寻找该问题的近似算法。这是目前比较流行的研究方法。近似算法是基于“牺牲解的最优性，寻找某个好的、可有效计算的可行解”的思路设计出的算法。因为绝大多数的近似算法都是结合所要求解问题的特点，按照人们直观、常识或某些经验估计与策略等来设计的，故近似算法通常也称为启发式算法，且往
16、往不加区分的使用。随着对近似算法研究的不断深入，人们也总结出了一些有代表性的方法，比如，下列三种思想或方法可用于相当广泛的领域中，并成为近似算法设计的主要思路141516：(1)贪婪算法：该类算法基于当前所得的信息，在每一步所选取的决策总是试图使当前的解得到最大的改进，或使相应的目标函数值尽可能地增大或减小。因每次迭代仅考虑当前的解局部地达到最优，并不能或不去保证使其从全局或长远来看亦可达到最优，故贪婪算法有时也称为近视算法。(2)局部搜索法：该类方法是通过选取某一可行解，构造其邻域，然后在该邻域中按某种方式进行搜索，以找到某一较好的可行解这样的方式进行迭代的。(3)原始对偶法：该类方法的主要工具是线性规划的对偶理论。原理是利用互补松弛性条件等来找到一系列成对的原始、对偶近似解，知道所得原始近似解满足要求为止。对具体的图论问题，有以下几个典型的搜索技术：(1)广度优先搜索法：由顶点 v 开始，下一步访问所有那些与 v 相邻的、仍未访问的顶点。这一搜索方法按照其
