图论法

《图论法》由会员分享，可在线阅读，更多相关《图论法（7页珍藏版）》请在金锄头文库上搜索。

1、图论算法图论算法在计算机科学种扮演者很重要的角色，它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基本算法加以解决。遗传算法是解优化问题的有效算法，而并行遗传算法是遗传算法研究中的一个重要方向，受到了研究人员的高度重视。特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化 （netwok optimizati

2、on）问题。 哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能

3、走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。深度优先搜索、广度优先搜索、无向图、有向图、最小生成树、最短路径。求最短路迪克斯特拉（Dijkstra）算法，其基本思想是按距从近到远为顺序，依次求得到的各顶点的最短路和距离，直至（或直至的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。(i) 令，对，令，。(ii) 对每个（），用代替。计算，把达到这个最小值的一个顶点记为，令。(iii). 若，停止；若，用代替，转(ii)。算法结束时，从到各顶点的距离由的最后一次的标号给出。在进入之前的标号叫T标号，进入时的标号叫P标号。算法就是不断修改各

4、项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，至各项点的最短路也在图上标示出来了。每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为。第二种解决这一问题的方法是由Floyd R W提出的算法，称之为Floyd算法。假设图权的邻接矩阵为，来存放各边长度，其中： ； 之间没有边，在程序中以各边都不可能达到的充分大的数代替；

5、 是之间边的长度，。对于无向图，是对称矩阵，。Floyd算法的基本思想是：递推产生一个矩阵序列，其中表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。计算时用迭代公式：是迭代次数，。最后，当时，即是各顶点之间的最短通路值。prim算法构造最小生成树设置两个集合和,其中用于存放的最小生成树中的顶点，集合存放的最小生成树中的边。令集合的初值为（假设构造最小生成树时，从顶点出发），集合的初值为。prim算法的思想是，从所有，的边中，选取具有最小权值的边，将顶点加入集合中，将边加入集合中，如此不断重复，直到时，最小生成树构造完毕，这时集合中包含了最小生成树的所有边。Kruskal算法构造最

6、小生成树科茹斯克尔（Kruskal）算法是一个好算法。Kruskal算法如下:(i)选，使得。(ii)若已选好，则从中选取，使得 中无圈，且 。(iii)直到选得为止。人员分派问题：工作人员去做件工作，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？这个问题的数学模型是：是二分图，顶点集划分为，当且仅当适合做工作时，求中的最大对集。匈牙利算法：（i）从中任意取定一个初始对集。（ii）若把中的顶点皆许配，停止，即完美对集；否则取中未被许配的一顶点，记，。（iii）若，停止，无完美对集；否则取。（iv）若是被许配的，设，转（iii）；否则，取可增广轨，令

7、，转（ii）。把人员指派问题、匈牙利算法稍加修改就能够用来求二分图的最大对集。Kuhn-Munkres算法（i）选定初始可行顶点标号，确定，在中选取一个对集。（ii）若中顶点皆被许配，停止，即的权最大的完美对集；否则，取中未被许配的顶点，令， 。(iii)若，转（iv）；若，取 ， ， ，。（iv）选中一顶点，若已被许配，且，则，转（iii）；否则，取中一个可增广轨，令，转（ii）。其中是中的相邻顶点集。经过的每条边的迹叫做的Euler迹；闭的Euler迹叫做Euler回路或回路；含Euler回路的图叫做Euler图。直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即

8、不重复地行遍所有的边再回到出发点。包含的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton轨叫做Hamilton圈或圈；含Hamilton圈的图叫做Hamilton图。直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。Fleury算法：1o. ，令。2o. 假设迹已经选定，那么按下述方法从中选取边：（i）和相关联；（ii）除非没有别的边可选择，否则不是的割边(cut edge)。(所谓割边是一条删除后使连通图不再连通的边)。3o. 当第2步不能再执行时，算法停止。对于非Euler图，1973年，Edmonds

9、和Johnson给出下面的解法：设是连通赋权图。（i）求。（ii）对每对顶点，求（是与的距离，可用Floyd算法求得）。（iii）构造完全赋权图，以为顶点集，以为边的权。（iv）求中权之和最小的完美对集。（v）求中边的端点之间的在中的最短轨。（vi）在（v）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。（vii）在（vi）中得的图上求Euler回路即为中国邮递员问题的解。最大流问题-参照运筹学第十一章p229-p253许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个

10、最大流量。最大流问题的限制条件：一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）；二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。因此有下面所谓的可行流的定义。定义14 对于给定的网络D=（V,A,C）和给定的流 ，若 满足下列条件：（1） （1） 容量限制条件：对每一条弧 ，有 (7.9)（2）平衡条件：对于中间点：流出量=流入量，即对于每一个i (is,t)，有 (7.10)对于出发

11、带点 ，有 (7.11)对于收点 ，有 (7.12)则称 为一个可行流， 称为这个可行流的流量。注意，我们这里所说的出发点 是指只有从 发出去的弧，而没有指向 的弧；收点 是指只有弧指向 ，而没有从它的发出去的弧。寻求最大流的标号法（Ford , Fulkerson）从一个可行流出发 （若网络中没有给定 ，则可以设 是零流），经过标号过程与调整过程。1） 标号过程在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点，每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。标号过程开始，总先给vs标上(

12、0,+)，这时vs是标号而未检查的点，其余都是未标号点，一般地，取一个标号而未检查的点vi，对一切未标号点vj：(1) 在弧上 ， ，则给vj标号 。这里 。这时点vj成为标号而未检查的点。(2) 若在弧 上， ，给vj标号 。这里 。这时点vj成为标号而未检查的点。于是 成为标号而已检查过的点，重复上述步骤，一旦 被标上号，表明得到一条从 到 的增广链 ，转入调整过程。若所有标号都是已检查过，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。2）2 调整过程首先按 及其它点的第一个标号，利用“反向追踪”的办法，找出增广链。例如设vt的第一个标号为 （或 ），则弧 （或相应地 ）是上

13、的弧。接下来检查 的第一个标号，若为 （或 ），则找出 （或相应地 ）。再检查 的第一个标号，依此下去，直到 为止。这时被找出的弧就构成了增广链 。令调整量是 ，即 的第二个标号。令 去掉所有的标号，对新的可行流 ，重新进入标号过程。二分匹配二分图的相关性质(1) 二分图的最大匹配数等于最小覆盖数，即求最少的点使得每条边都至少和其中的一个点相关联，很显然直接取最大匹配的一段节点即可。 (2) 二分图的独立数等于顶点数减去最大匹配数，很显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集，这是|V|-2*|M|，同时必然可以从每条匹配边的两端取一个点加入独立集并且保持其独立集性质。

14、(3) DAG的最小路径覆盖，将每个点拆点后作最大匹配，结果为n-m，求具体路径的时候顺着匹配边走就可以，匹配边ij,jk,kl.构成一条有向路径。最大匹配： 图中包含边数最多的匹配称为图的最大匹配。 完美匹配： 如果所有点都在匹配边上，称这个最大匹配是完美匹配。最小覆盖： 最小覆盖要求用最少的点（集合或集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）最大匹配数最小路径覆盖：用尽量少的不相交简单路径覆盖有向无环图的所有结点。解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：结点集中的i和Y结点集中的i,如果有边i-j，则在二分图中引入边i-j，设二分图最大匹配为m,则结果就是n-m。最大独立集问题： 在个点的图G中选出m个点，使这m个点两两之间没有边求m最大值 如果图满足二分图条件，则可以用二分图匹配来做最大独立集点数 = N - 最大匹配数注意要点：（一）每个X节点都最多做一次增广路的起点；（二）如果一个Y节点已经匹配了，那么增广路到这儿的时候唯一的路径是走到Y节点的匹配点（可以回忆最大流算法中的后向边，这个时候后向边是可以增流的）。求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)