第二章 图论模型

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学建模简明教程,国家精品课程,第二章 图论模型,一、,问题引入与分析,二、,图论的基本概念,三、,最短路问题及算法,四、,最小生成树及算法,五、,旅行售货员问题,六、,模型建立与求解,目录,下页,返回,上页,结束,1. 98,年全国大学生数学建模竞赛,B,题“最佳灾,今年,(1998,年,),夏天某县遭受水灾,.,为考察灾情、,组织自救，县领导决定，带领有关部门负责人到,全县各乡（镇）、村巡视,.,巡视路线指从县政府,所在地出发，走遍各乡（镇）、村，又回到县政,府所在地的路线,.,情巡视路线”中的前两个问题是这样的：,一、问题引入与分析,目录,下页,返回,上页,结束,1,）若分三组（路）巡视，试设计总路程最,短且各组尽可能均衡的巡视路线,.,2,）假定巡视人员在各乡（镇）停留时间,T,=2,小时，在各村停留时间,t,=1,小时，汽车行驶速度,V,=35,公里,/,小时,.,要在,24,小时内完成巡视，至少应分,几组；给出这种分组下最佳的巡视路线,.,目录,下页,返回,上页,结束,公路边的数字为该路段的公里数,.,目录,下页,返回,上页,结束,2.,问题分析：,本题给出了某县的公路网络图，要求的是在不,同的条件下，灾情巡视的最佳分组方案和路线,.,将每个乡（镇）或村看作一个图的顶点，各乡,镇、村之间的公路看作此图对应顶点间的边，各,次再回到点,O,，使得总权（路程或时间）最小,.,条公路的长度（或行驶时间）看作对应边上的权，,所给公路网就转化为加权网络图，问题就转化图论,中一类称之为旅行售货员问题，即在给定的加权网,络图中寻找从给定点,O,出发，行遍所有顶点至少一,目录,下页,返回,上页,结束,如第一问是三个旅行售货员问题，第二问是四,本题是旅行售货员问题的延伸,-,多旅行售货员问题,.,本题所求的分组巡视的最佳路线，也就是,m,条,众所周知，旅行售货员问题属于,NP,完全问题，,显然本问题更应属于,NP,完全问题,.,有鉴于此，,经过同一点并覆盖所有其他顶点又使边权之和达,到最小的闭链（闭迹）,.,个旅行售货员问题,.,即求解没有多项式时间算法,.,一定要针对问题的实际特点寻找简便方法，想找到,解决此类问题的一般方法是不现实的，对于规模较,大的问题可使用近似算法来求得近似最优解,.,目录,下页,返回,上页,结束,二、,图论的基本概念,目录,下页,返回,上页,结束,1),图的概念,2),赋权图与子图,3),图的矩阵表示,4),图的顶点度,5),路和连通,定义,一个,图,G,是指一个二元组,(V(G),E(G),，其中,:,其中元素称为图,G,的,顶点,.,组成的集合，即称为,边集,其中元素称为,边,.,定义,图,G,的,阶,是指图的顶点数,|,V(G)|,用,来表示；,图的边的数目,|,E(G)|,用,来表示,.,也用,来表示边,是非空有限集，称为,顶点集,，,1),2),E(G,),是顶点集,V(G),中的无序或有序的元素偶对,表示图，,简记,用,1),图的概念,目录,下页,返回,上页,结束,定义,若一个图的顶点集和边集都是有限集，则称,其为,有限图,.,只有一个顶点的图称为,平凡图,，其他的,所有图都称为,非平凡图,.,目录,下页,返回,上页,结束,定义,若图,G,中的边均为有序偶对,(,v,i,v,j,),，称,G,为,有向,图,.,称边 为,有向边,或,弧,称 是从,连接,称 为,e,的,尾,， 称 为,e,的,头,.,若图,G,中的边均为无序偶对 ，称,G,为,无向图,.,称,为,e,的,端点,.,边 为,无向边,，称,e,连接,和 ，顶点 和 称,既有无向边又有有向边的图称为,混合图,.,目录,下页,返回,上页,结束,常用术语,1),边和它的两端点称为互相,关联,.,2),与同一条边关联的两个端点称,为,相邻,的顶点，与同一个顶点,点关联的两条边称为,相邻,的边,.,3),端点重合为一点的边称为,环,，,端点不相同的边称为,连杆,.,4),若一对顶点之间有两条以上的边联结，则这些边,称为,重边,5),既没有环也没有重边的图，称为,简单图,目录,下页,返回,上页,结束,常用术语,6),任意两顶点都相邻的简单图,称为完全图,.,记为,K,v,.,7),若 ，,，,且,X,中任意两顶点不,相邻，,Y,中任意两顶点不相邻，则称为,二部图,或,偶图,；若,X,中每一顶点皆与,Y,中一切顶点相邻,称,为,完全二部图,或,完全偶图,记为,(,m=|,X|,n,=|Y|,),8),图 叫做,星,.,二部图,目录,下页,返回,上页,结束,定义,若图,G=,(,V,(,G,),E,(,G,),的每一条边,e,都赋以,一个实数,w(e,),，称,w(e,),为边,e,的,权,，,G,连同边上的权,称为,赋权图,.,定义,设 和 是两个图,.,1),若,称 是 的一个,子图,记,2),若 ， ，则称 是 的,生成子图,.,3),若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,为 的,由 导出的子图,，记为,.,4),若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的,由 导出的,边导出的子图,记为,.,2),赋权图与子图,目录,下页,返回,上页,结束,3),若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,4),若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的,由 导出的,边导出的子图,记为,.,为 的,由 导出的子图,，记为,.,目录,下页,返回,上页,结束,1),对无向图 ，其邻接矩阵 ，其中：,邻接矩阵,:,(,以下均假设图为简单图,).,3),图的矩阵表示,目录,下页,返回,上页,结束,2),对有向图,其邻接矩阵,其中：,目录,下页,返回,上页,结束,其中：,3),对有向赋权图,其邻接矩阵,对于无向赋权图的邻接矩阵可类似定义,.,目录,下页,返回,上页,结束,1),对无向图 ，其关联矩阵,其中：,关联矩阵,目录,下页,返回,上页,结束,2),对有向图 ，其关联矩阵,其中：,目录,下页,返回,上页,结束,目录,下页,返回,上页,结束,定义,1),在无向图,G,中，与顶点,v,关联的边的数目,(,环,算两次,),称为顶点,v,的,度,或,次数,，记为,d(v,),或,d,G,(v,).,称度为奇数的顶点为,奇点,，度为偶数的顶点为,偶点,.,2),在有向图中，从顶点,v,引出的边的数目称为顶点,v,的,出度,，记为,d,+,(v,),，从顶点,v,引入的边的数目称为,v,的,入度,，记为,d,-,(v),.,称,d(v,)=,d,+,(v)+d,-,(v),为顶点,v,的,度,或,次数,定理,的个数为偶数,推论,任何图中奇点,4),图的顶点度,目录,下页,返回,上页,结束,定义,1),无向图,G,的一条,途径,（或,通道,或,链,）是指,一个有限非空序列 ，它的项交替,地为顶点和边，使得对 ， 的端点是 和,称,W,是从 到 的一条,途径,，或一条,途径,.,整数,k,称为,W,的,长,.,顶点 和 分别称为,起点,和,终点,而 称为,W,的,内部顶点,.,2),若途径,W,的边互不相同但顶点可重复，则称,W,为,迹,或,简单链,.,3),若途径,W,的顶点和边均互不相同，则称,W,为,路,或,路径,.,一条起点为,终点为 的路称为,路,记为,5),路和连通,目录,下页,返回,上页,结束,定义,1),途径 中由相继项构成子序列,称为途径,W,的,节,.,2),起点与终点重合的途径称为,闭途径,.,3),起点与终点重合的的路称为,圈,(,或,回路,),，长,为,k,的圈称为,k,阶圈,，记为,C,k,.,4),若在图,G,中存在,(,u,v,),路，则称顶点,u,和,v,在图,G,中,连通,.,5),若在图,G,中顶点,u,和,v,是连通的，则顶点,u,和,v,之,之间的,距离,d,(,u,v,),是指图,G,中最短,(,u,v,),路的长；若没,没有路连接,u,和,v,，则定义为无穷大,.,目录,下页,返回,上页,结束,6),图,G,中任意两点皆连通的图称为,连通图,类似地，可定义,有向迹,，,有向路,和,有向圈,.,7),对于有向图,G,，若 ，且 有,头 和尾 ，则称,W,为,有向途径,.,例,在右图中：,途径或链：,迹或简单链：,路或路径：,圈或回路：,目录,下页,返回,上页,结束,三、最短路问题及算法,最短路问题是图论应用的基本问题，很多实际,问题，如线路的布设、运输安排、运输网络最小费,用流等问题,都可通过建立最短路问题模型来求解,.,最短路的定义,最短路问题的两种方法：,Dijkstra,和,Floyd,算法,.,1),求赋权图中从给定点到其余顶点的最短路,.,2),求赋权图中任意两点间的最短路,.,目录,下页,返回,上页,结束,2),在赋权图,G,中，从顶点,u,到顶点,v,的具有最小权,定义,1),若,H,是赋权图,G,的一个子图，则称,H,的各,边的权和 为,H,的,权,.,类似地，若,称为路,P,的,权,若,P,(,u,v,),是赋权图,G,中从,u,到,v,的路,称,的路,P*,(,u,v,),，称为,u,到,v,的,最短路,3),把赋权图,G,中一条路的权称为它的,长,，把,(,u,v,),路的最小权称为,u,和,v,之间的,距离,，并记作,d,(,u,v,).,目录,下页,返回,上页,结束,1),求赋权图中从给定点到其余顶点的最短路,解决上述问题的一个方法是由,Dijkstra,于,1959,年提出的算法，此算法不仅能求出赋权图指定两点,最短路,.,目前它是求无负权图最短路的最好方法,.,间的最短路，而且能求出从指定点到其余各顶点的,该算法基本原理,：若 是赋权图,G,中从 到 的最短路，则 必为从 到,的最短路，则称 是 的,先驱点,记为,它可用于追踪最短路的路径,.,最短路是一条路，且最短路的任一节也是最短路,目录,下页,返回,上页,结束,假设,G,为赋权有向图或无向图，,G,边上的权均非,负若 ，则规定,求下面赋权图,G,中顶点,v,0,到其余顶点的最短路,输入：图,G,的带权邻接矩阵,W,.,目录,下页,返回,上页,结束,Dijkstra,算法,:,求,G,中从顶点 到其余顶点的最短路,.,对每个顶点，定义两个标记（,l,(,v,),t,(,v,),），其中,:,l,(,v,),表示从顶点到的一条路的权,t,(,v,),表示的先驱点，它可用以确定最短路的路径,.,算法的过程就是在每一步改进这两个标记,(,l,(,v,),t,(,v,),使最终,l,(,v,),为从顶点,v,0,到,v,的最短路的权,S,：具有永久标号的顶点集,.,目录,下页,返回,上页,结束,Dijkstra,算法步骤,:,用上述算法求出的,l,(,v,),就是,v,0,到,v,的最短路的权,(1),初始化操作,:,置,S,=,v,0,l,(,v,0,)=0,对每个,令,(2),设,v,*,是使,l,(,v,),取最小值的 中的顶点，即,，则令 ，,.,若 ，停止,.,否则，转（,3,）,.,(3),更新,l,(,v,),、,t,(,v,),：对每个 ，若,l,(,v,),l,(,u,)+,w,(,u,v,),则令,l,(v,)=,l,(,u,)+,w,(,u,v,),转,(2),.,从,v,的先驱点标记,t,(,v,),追溯到,v,0,就得到,v,0,到,v,的最短,路的路径,.,(1),初始化操作,:,置,S,=,v,0,l,(,v,0,)=0 ,对每个,令,停止,.,否则，转（,3,）,.,则令 ，,.,若,(3),更新,l,(,v,),、,t,(,v,),:,对每个,若,l,(,v,),l,(,u,)+,w,(,u,v,),则令,l,(v,)=,l,(,u,)+,w,(,u,v,),转,(2),.,(2),设,v,*,是使,l,(,v,),取最小值的 中的顶点，即,(2),设,v,*,是使,l,(,v,),取最小值的 中的顶点,即,置,S,=,v,0,l,(,v,0,)=0,方框把,0,框起来,.,给与,v,0,相邻的顶点,分别标以,l,(,v,1,)=,w,(,v,0,v,1,)=w,01,1,l(v,2,)=2,l,(,v,4,)=7,l(v,6,)=4,l,(,v,7,)=8.,v,1, v,2, v,4, v,6, v,7,其余顶点均标以,即,l(v,3,)= ,l,(,v,5,)= .,(1),初始化操作,:,置,S,=,v,0,l,(,v,0,)=0 ,对每个,令,停止,.,否则，转（,3,）,.,则令 ，,.,若,(3),更新,l,(,v,),、,t,(,v,),:,对每个,若,l,(,v,),l,(,u,)+,w,(,u,v,),则,l,(v,)=,l,(,u,)+,w,(,u,v,),转,(2),.,(2),设,v,*,是使,l,(,v,),取最小值的 中的顶点，即,(2),设,v,*,是使,l,(,v,),取最小值的 中的顶点,即,对每个,记,t,(,v,),=v,0,即它们,的,先驱点均为,v,0,。,在,中取标号最小者,l,(,v,1,)=1,.,用方框把,1,框起来,.,令,(1),初始化操作,:,置,S,=,v,0,l,(,v,0,)=0 ,对每个,令,停止,.,否则，转（,3,）,.,则令 ，,.,若,(3),更新,l,(,v,),、,t,(,v,),:,对每个,若,l,(,v,),l,(,u,)+,w,(,u,v,),则,l,(,v,)=,l,(,u,)+,w,(,u,v,),转,(2),.,(2),设,v,*,是使,l,(,v,),取最小值的 中的顶点，即,的算法步骤,(3),重新,(2),设,v,*,是使,l,(,v,),取最小值的 中的顶点,即,令,用,Dijkstra,的标号,l,(,v,),、,t,(,v,) .,经计,改进顶点,算只有,v,3,满足条件,:,则给,v,3,标以,l,(,v,3,)=,4.,令,t,(,v,3,)=,v,1,此时其它,点的两个标号,l,(,v,),、,t,(,v,),保持不变。,(1),初始化操作,:,置,S,=,v,0,l,(,v,0,)=0 ,对每个,令,停止,.,否则，转（,3,）,.,则令 ，,.,若,(3),更新,l,(,v,),、,t,(,v,),:,对每个,若,l,(,v,),l,(,u,)+,w,(,u,v,),则,l,(,v,)=,l,(,u,)+,w,(,u,v,),转,(2),.,(2),设,v,*,是使,l,(,v,),取最小值的 中的顶点，即,(2),设,v,*,是使,l,(,v,),取最小值的 中的顶点,即,重复上面的做法，,能在改进为止。,直到所有顶点的两,个标号,l,(,v,),、,t,(,v,),不,目录,下页,返回,上页,结束,目录,下页,返回,上页,结束,目录,下页,返回,上页,结束,目录,下页,返回,上页,结束,定义,根据顶点,v,的标号,l(v,),的取值途径，使 到,v,的最短路中与,v,相邻的前一个顶点,w,，称为,v,的,先驱,点,，记为,t,(,v,),即,t,(,v,)=,w,.,先驱点可用于追踪最短路径,.,上例的标号过程也,可按如下方式进行：,首先写出左图带权邻接矩阵,因,G,是无向图，故,W,是对称阵,目录,下页,返回,上页,结束,目录,下页,返回,上页,结束,见,Visual C+6.0,程序,-,Dijkstra.cpp,目录,下页,返回,上页,结束,（,I,）求距离矩阵的方法,.,（,II,）求路径矩阵的方法,.,（,III,）查找最短路路径的方法,.,Floyd,算法：求任意两顶点间的最短路,.,举例说明,2),求赋权图中任意两顶点间的最短路,算法的基本思想,算法的基本思想,直接在图的带权邻接矩阵中用插入顶点的,方法依次构造出,v,个矩阵,D,(1),、,D,(2),、,、,D,(v,),，,使最后得到的矩阵,D,(v,),成为图的距离矩阵，同时,也求出插入点矩阵以便得到两点间的最短路径,目录,下页,返回,上页,结束,目录,下页,返回,上页,结束,（,I,）求距离矩阵的方法,.,设赋权图,G,的顶点集为,.,1,）,写出赋权图,G,的带权邻接矩阵,W,，,把它作为距,离,矩阵的初值，即,2,）对,k,=1,2,v,，计算,其中,表示从,v,i,到,v,j,且中间点仅为,v,1,v,2,v,k,的,k,个点的,所有路径中的最短路的长度。,于是 中元素 就是从 到 的,路径中间可插入任何顶点的路径中最短路的长度，,即 就是所求距离矩阵,.,目录,下页,返回,上页,结束,在建立距离矩阵的同时可建立路径矩阵,R,（,II,）求路径矩阵的方法,.,设 ，这里 的含义是从 到,的最短路要经过点号为 的点,.,算法开始于 ， ，,迭代到第,k,步，,即由 到 迭代，若某个元素改变（变小），,则由 到 迭代中，相应元素改为,k,，表示到第,k,次迭代,从 到 的最短路过点 比过原中间点更短,.,在求得 时求得 ，可由 来查找任何点对,之间最短路的路径,.,然后用同样的方法再分头查找若：,（,III,）查找最短路路径的方法,.,目录,下页,返回,上页,结束,(IV) Floyd,算法,:,求任意两顶点间的最短路,.,d(i,j,),：,i,到,j,的距离,r(i,j,),：,i,到,j,之间的插入点,输入,:,带权邻接矩阵,.,(1),赋初值,:,对所有,i,j,d(i,j,),w(i,j,),r(i,j,) j, k 1.,(2),更新,d(i,j,),r(i,j,),:,对所有,i,j,若,d(i,k)+d(k,j,),d(i,j,),则,d(i,j,),d(i,k)+d(k,j,),r(i,j,) k.,(3),若,k,=,v,，停止否则,k k+,1,，转,(2),目录,下页,返回,上页,结束,目录,下页,返回,上页,结束,例,求下图中加权图的任意两点间的距离与路径,.,目录,下页,返回,上页,结束,插入点,v,1,，,得：,矩阵中带“,=,”,的项为经迭代比较以后有变化的元素,.,插入点,v,2,，,得：,矩阵中带“,=,”,的项为经迭代比较以后有变化的元素,.,目录,下页,返回,上页,结束,插入点,v,3,，,得：,目录,下页,返回,上页,结束,插入点,v,4,，,得：,插入点,v,5,，,得：,目录,下页,返回,上页,结束,插入点,v,6,，,得：,目录,下页,返回,上页,结束,故从,v,5,到,v,2,的最短路为,8,由,v,6,向,v,5,追溯,:,由,v,6,向,v,2,追溯,:,所以从到的最短路径为：,见,Visual C+6.0,程序,Floyd.cpp,如下。,目录,下页,返回,上页,结束,四、最小生成树及算法,目录,下页,返回,上页,结束,1),树的定义与树的特征,定义,连通且不含圈的无向图称为,树,常用,T,表示,.,树中的边称为,树枝,.,树中度为,1,的顶点称为,树叶,.,孤立顶点称为,平凡树,.,平凡树,目录,下页,返回,上页,结束,1),G,是树（,G,无圈且连通）；,2),G,无圈，且有,n,-1,条边,；,3),G,连通，且有,n,-1,条边；,4),G,无圈，但添加任一条新边恰好产生一个圈,;,5),G,连通，且删去一条边就不连通了（即,G,为,最,最小连通图,）；,6),G,中任意两顶点间有唯一一条路,.,定理,2,设,G,是具有,n,个顶点的图，则下述命题等价：,定义,若,T,是包含图,G,的全部顶点的子图,它又是树,则称,T,是,G,的,生成树,.,图,G,中不在生成树的边叫做,弦,.,定理,3,图,G=(V,E),有生成树的充要条件是图,G,是连,通的,.,证明,:,必要性,是显然的,.,2,）图的生成树,目录,下页,返回,上页,结束,充分性,：,任取 ，令集合 ，这时生成树,的边集 为空集,.,因为 是连通图，点集 与,之间必有边相连，设 为这样的边，,目录,下页,返回,上页,结束,属于 而 属于 。则得 ，,。重复进行上述步骤，对于, , ,仍能找到边 满足其一端在点集 ，另一端在点集,中,.,由于 有一端在 之外，所以 与 中的,边不构成圈,.,当 时，得到,， ，,即图 有 条边且无圈，由定理,2,知，,这是一棵树，且为图 的一棵生成树,.,目录,下页,返回,上页,结束,可分为两种：避圈法和破圈法,A,避圈法,:,深探法和广探法,B,破圈法,（,II,）找图中生成树的方法,目录,下页,返回,上页,结束,定理,3,的充分性的证明提供了一种构造图的生,成树的方法,.,止,.,这种方法可称为,“,避圈法,”,或,“,加边法,”,成树的方法可分为两种：,深探法,和,广探法,.,A,避圈法,这种方法就是在已给的图,G,中，每步选出一,条边使它与已选边不构成圈，直到选够,n,-1,条边为,在避圈法中，按照边的选法不同，找图中生,目录,下页,返回,上页,结束,a),深探法,若这样的边的另一端均已有标号，就退到标号为,步骤如下：,i),在点集,V,中任取一点,u,ii),若某点,v,已得标号，检,端是否均已标号,.,若有边,vw,之,w,未标号,则给,w,代,v,，重复,ii).,i,-1,的,r,点,以,r,代,v,重复,ii),直到全部点得到标号为止,.,给以标号,0,.,查一端点为,v,的各边，另一,w,以标号,i,+1,，记下边,vw,.,令,例,用深探法求出下图,10,的一棵生成树,图,10,0,1,2,3,4,5,6,7,8,9,10,11,12,13,目录,下页,返回,上页,结束,13,a),深探法,图,10,0,1,2,3,4,5,6,7,8,9,10,11,12,步骤如下：,若这样的边的另一端均已有标号，就退到标号为,i),在点集,V,中任取一点,u,ii),若某点,v,已得标号，检,端是否均已标号,.,若有边,vw,之,w,未标号,则给,w,代,v,，重复,ii).,i,-1,的,r,点,以,r,代,v,重复,ii),直到全部点得到标号为止,.,给,u,以标号,0.,查一端点为,v,的各边，另一,w,以标号,i,+1,，记下边,vw,.,令,例,用,深探法求出下图,10,的一,棵生成树,目录,下页,返回,上页,结束,3,b),广探法,步骤如下：,i),在点集,V,中任取一点,u,ii),令所有标号,i,的点集为,是否均已标号,.,对所有未标,号之点均标以,i,+1,记下这些,iii),对标号,i,+1,的点重复步,步骤,ii),，直到全部点得到,给,u,以标号,0.,V,i,检查,V,i,V,V,i,中的边端点,边,.,例,用广探法求出下图,10,的一棵生成树,图,10,1,0,1,2,2,1,3,2,1,2,2,3,4,标号为止,.,图,10,目录,下页,返回,上页,结束,3,b),广探法,步骤如下：,i),在点集,V,中任取一点,u,ii),令所有标号,i,的点集为,是否均已标号,.,对所有未标,号之点均标以,i,+1,记下这些,iii),对标号,i,+1,的点重复步,步骤,ii),，直到全部点得到,给,u,以标号,0.,V,i,检查,V,i,V,V,i,中的边端点,边,.,例,用广探法求出下图,10,的一棵生成树,图,10,1,0,1,2,2,1,3,2,1,2,2,3,4,标号为止,.,显然图,10,的生成树,不唯一,.,目录,下页,返回,上页,结束,意舍弃一条边，将这个圈破掉，重复这个步骤直,例,用破圈法求出,下图的一棵生成树,.,B,破圈法,相对于避圈法，还有一种求生成树的方法叫做,“,破圈法,”,.,这种方法就是在图,G,中任取一个圈，任,到图,G,中没有圈,为止,.,目录,下页,返回,上页,结束,例,用破圈法求出下图的另一棵生成树,.,B,破圈法,不难发现，图的生成树不是唯一的,.,介绍最小树的两种算法：,Kruskal,算法,（或,避圈法,）和,破圈法,.,3),最小生成树与算法,目录,下页,返回,上页,结束,目录,下页,返回,上页,结束,步骤如下：,1),选择边,e,1,，使得,w(e,1,),尽可能小；,2),若已选定边 ，则从,中选取 ，使得,:,i),为无圈图，,ii),是满足,i),的尽可能小的权，,3),当第,2),步不能继续执行时，则停止,.,定理,4,由,Kruskal,算法构作的任何生成树,都是最小树,.,A,Kruskal,算法（或避圈法）,目录,下页,返回,上页,结束,例,10,用,Kruskal,算法求下图的最小树,.,在左图中 权值,最小的边有 任取一条,在 中选取权值,最小的边,中权值最小边有,从中选,任取一条边,会与已选边构成圈,故停止,得,中选取在中选取,中选取,.,但 与 都,目录,下页,返回,上页,结束,算法,2,步骤如下：,1),从图,G,中任选一棵树,T,1,.,2),加上一条弦,e,1,，,T,1,+e,1,中,立即生成一个圈,.,去掉此,圈中最大权边，得到新,树,T,2,以,T,2,代,T,1,重复,2),再,检查剩余的弦，直到全,部弦检查完毕为止,.,例,11,用破圈,法求下图的最小树,.,先求出上图的一棵生成树,.,加以弦,e,2,得到的圈,v,1,v,3,v,2,v,1,去掉最大的权边,e,2,得到一棵新,树仍是原来的树；,B,破圈法,再加上弦,e,7,，得到圈,v,4,v,5,v,2,v,4,去掉最大的权边,e,6,，得到一棵,新树；如此重复进行，直到全,全部的弦均已试过,得最小树,.,目录,下页,返回,上页,结束,五、旅行售货员问题,定义,设,G=(V,E),是连通无向图，包含图,G,的每个,顶点的路称为,G,的,哈密尔顿路,(,Hamilton,路,或,H,路,).,包含图,G,的每个顶点的圈，称为,G,的,哈密尔顿圈,(,或,Hamilton,圈,或,H,圈,).,含,Hamilton,圈的图称为,哈密尔顿图,(,或,Hamilton,图,或,H,图,).,目录,下页,返回,上页,结束,一个旅行售货员想去访问若干城镇，然后回,到出发地,.,给定各城镇之间的距离后，应怎样计划,他的旅行路线，使他能对每个城镇恰好经过一次,而总距离最小？,它可归结为这样的,图论问题：,在一个赋权完,全图中,找出一个最小权的,H,圈,称这种圈为,最优圈,.,但这个问题是,NP-hard,问题，即不存在多项式,时间算法,.,也就是说,对于大型网络,(,赋权图,),目前还,没有一个求解旅行售货员问题的有效算法，因此,只能找一种求出相当好（不一定最优）的解,.,旅行售货员问题或货郎担问题,.,目录,下页,返回,上页,结束,是先求一个,H,圈,然后适当,修改,以得到具有较小权的另,一个,H,圈,.,一个可行的办法,:,设找到一个初始,H,圈 ，则对所,有,适合 的 和 ，总可得到一个新的,H,圈： ，它是由,C,删去边 和 ，以及添加边 和,而得到，如右图所示。,目录,下页,返回,上页,结束,定义,若对于某一对,i,和,j,，有,则圈,C,ij,将是圈,C,的一个,改进,.,二边逐次修正法,:,在接连进行一系列修改之后,最后得一个圈,不能,再用此方法改进了，这个最后的圈可能不是最优的,但是它是比较好的，为了得到更高的精度，这个,程序可以重复几次，每次都以不同的圈开始,.,这种,方法叫做,二边逐次修正法,.,目录,下页,返回,上页,结束,较优,H,圈,:,其权为,W(C,3,)=,192,例,对下图,16,的,K,6,用二边逐次修正法求较优,H,圈,.,目录,下页,返回,上页,结束,分析,:,找出的这个解的好坏可用最优,H,圈的权,的下界与其比较而得出,.,即利用最小生成树可得最,优,H,圈的一个下界，,方法如下,：,设,C,是,G,的一个最优,H,圈，则对,G,的任一顶点,v,C-v,是,G-v,的路，也,G-v,是的生成树,.,如果,T,是,G-v,的,最小生成树,且,e,1,是,e,2,与,v,关联的边中权最小的两条,边,则,w(T)+w(e,1,)+w(e,2,),将是,w(C,),的一个下界,.,取,v=v,3,得,G-v,3,的一,最小生成树,(,实线,),其,权,w(T,)=122,与,v,3,关联,的权最小的两条边为,w(T)+w(v,1,v,3,)+w(v,2,v,3,),=,178,.,故最优,H,圈的权,v,1,v,3,和,v,2,v,3,故,w(C,),应满足,178,w(C,),192,.,目录,下页,返回,上页,结束,六、最佳灾情巡视路线的模型的建立与求解,问题转化为在,给定的加权网,络图中寻找从,给定点,O,出发,行遍所有顶点,至少一次再回,回到点,O,使得,总权,(,路程或时,时间,),最小,即,最佳旅行售货,员问题,.,目录,下页,返回,上页,结束,最佳旅行售货员问题是,NP,完全问题,采用一种,近似算法求其一个近似最优解，来代替最优解,.,算法一,求加权图的最佳旅行售货员回路近似算法,:,1),用图论软件包求出,G,中任意两个顶点间的最短路,构造出完全图,2),输入图 的一个初始,H,圈；,3),用对角线完全算法（见,3,）产生一个初始圈,;,4),随机搜索出 中若干个,H,圈，例如,2000,个；,5),对第,2),，,3),，,4),步所得的每个,H,圈，用二边逐次,修正法进行优化，得到近似最优,H,圈；,6),在第,5),步求出的所有,H,圈中，找出权最小的一个,此即要找的最优,H,圈的近似解,.,因二边逐次修正法的结果与初始圈有关,故本算法,第,2),，,3),，,4),步分别用三种方法产生初始圈，以保,证能得到较优的计算结果,.,问题一,若分为三组巡视，设计总路程最短且各,组尽可能均衡的巡视路线,.,此问题是多个售货员的最佳旅行售货员问题,.,4),目录,下页,返回,上页,结束,目录,下页,返回,上页,结束,此问题包含两方面：,a),对顶点分组, b),在每组中,求,(,单个售货员,),最佳旅行售货员回路,.,因单个售货员的最佳旅行售货员回路问题不存,存在多项式时间内的精确算法,.,故,多,也不,目录,下页,返回,上页,结束,而图中节点数较多，为,53,个，我们只能去寻求,一种较合理的划分准则，对图,1,进行粗步划分后,求,出各部分的近似最佳旅行售货员回路的权,再进一,进一步进行调整，使得各部分满足均衡性条件,3).,从,O,点出发去其它点，要使路程较小应尽量走,O,点到该点的最短路,.,故用软件包求出,O,点到其余顶点的最短路,.,这些最短路构成一棵,O,为树根的树,.,将从,O,点出发的树枝称为,干枝,.,从,O,点出发到其它点共有,6,条干枝，它们的名称,分别为，,.,在分组时应遵从准则：,准则,1,尽量使同一干枝上及分枝上的点分在同一组,.,准则,2,应将相邻的干枝上的点分在同一组；,准则,3,尽量将长的干枝与短的干枝分在同一组,.,分组,1,极不均衡,故考虑分组,2.,由上述分组准则，我们找到两种分组形式如下：,分组,1:,（，），（，），（，）,分组,2:,（，），（，），（，）,目录,下页,返回,上页,结束,分组,2:(,),(,),(,),对分组,2,中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路线,.,在每个子图所构造的完全图中,取一个尽量包含上图中树上的边的,H,圈作为其第,2),步输入的初始圈,.,分组,2,的近似解,目录,下页,返回,上页,结束,因为该分组的均衡度,.,所以此分法的均衡性很差,.,为改善均衡性，将第,组中的顶点,C,2,3,D,4,分给第,组（顶点,2,为这两组的公共点），重新分,分组后的近似最优解见表,2.,目录,下页,返回,上页,结束,因该分组的均衡度,所以这种分法的均衡性较好,.,问题二,当巡视人员在各乡（镇）、村的停留,停留时间一定,汽车的行驶速度一定,要在,24,小时内,完成巡视,至少要分几组及最佳旅行的巡视路线,.,目录,下页,返回,上页,结束,由于,T,=2,小时,t,=1,小时,V,=35,公里,/,小时,需访问,的乡镇共有,17,个，村共有,35,个,.,计算出在乡,(,镇,),及,村的总停留时间为,17 2+35=69,小时，要在,24,小时,内完成巡回，若不考虑行走时间，有,: 69/,i24,(,i,为,分的组数,).,得,i,最小为,4,，故,至少要分,4,组,.,由于该网络的乡,(,镇,),、村分布较为均匀,故有可,能找出停留时间尽量均衡的分组,当分,4,组时各组停,停留时间大约为,69/4=17.25,小时，则每组分配在路,路途上的时间大约为,24-17.25=6.75,小时,.,而前面讨,论过,分三组时有个总路程,599.8,公里的巡视路线，,分,4,组时的总路程不会比,599.8,公里大太多,不妨以,599.8,公里来计算,.,路上约用,599.8/35=17,小时,若平,均分配给,4,个组,每个组约需,17/4=4.25,h,6.75,h,故分成,4,组是可能办到的,.,目录,下页,返回,上页,结束,现在尝试将顶点分为,4,组,.,分组的原则：除遵从,前面准则,1,、,2,、,3,外，还应遵从以下准则：,准则,4,尽量使各组的停留时间相等,.,用上述原则在下图,上将图分为,4,组，同,时计算,各组的停留时间,然后用算法一算出各组的近似最,最佳旅行售货员巡回，得出路线长度及行走时间,从而得出完成巡视的近似最佳时间,.,用算法一计,计算时，初始圈的输入与分三组时同样处理,.,这,4,组的近似最优解见表,3.,目录,下页,返回,上页,结束,表,3,符号说明：加有底纹的表示前面经过并停留过,此次只经过不停留,;,加框的表示此点只经过不停留,.,可看出,表,3,分组的均衡度很好,且完全满足,24,小时完成巡视的要求,.,该分组实际均衡度,4.62%,再见,目录,下页,返回,上页,结束,