运筹学第06章图论概述.ppt

《运筹学第06章图论概述.ppt》由会员分享，可在线阅读，更多相关《运筹学第06章图论概述.ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学运筹学 第六章第六章 图论概述图论概述本章重点本章重点n图的基本概念n常见的四个问题的求解方法图的含义图的含义n图是一种模型u如公路、铁路交通图，通讯网络图等n图是对现实的抽象u很多问题都可以用顶点和边来表示，一般顶点表示实体，边(顶点与顶点之间的连线)表示实体之间的关系，顶点和边的集合定义为图图图论的提出图论的提出(1)n用图来描述事物及其联系，最早是由瑞士数学家欧拉(Euler)于1736年解决哥尼斯堡七桥问题时提出的n如右图所示，哥尼斯堡地区被河流分为了四个区域，四个区域之间有七座桥相连，问是否有一条路线，可以经过所有的桥并且每座桥只经过一次？BACD图论的提出图论的提出(2)n用

2、图来表示这个问题u用四个顶点表示四个地区u用七条边表示七座桥n要寻找这样的一条路线：经过所有的边并且每条边只经过一次n该问题已经证明无解图的基本概念图的基本概念(1)n图：图：顶点和边的集合n点的集合用V表示，边的集合用E表示，则图可以表示为G=(V,E)n如下图G=(V,E)其中，V=A,B,C,D E=e1,e2,e3,e4,e5,e6,e7 E中，e1=(A,D),e2=(B,D),e3=(C,D)e4=(B,C),e5=(A,C),e6=(A,C),e7=(B,C)e2e1e3e4e5e6e7图的基本概念图的基本概念(2)n边都没有方向的图称为无向图无向图，前面所讲的图就是无向图。无向

3、图的边eij=(vi,vj)=(vj,vi)=ejin当图中的边都有方向时，称为有向图有向图。为了区别于无向图，有向图用G(V,A)表示n在有向图中，有向边又称为弧弧，用 aij=(vi,vj)表示，(vi,vj)(vj,vi)，弧的方向用箭头标识n既有边又有弧的图称为混合图混合图n下图中从左向右依次为：无向图，有向图，混合图图的基本概念图的基本概念(3)n集合V中元素的个数称为图G的顶点数顶点数，记作p(G)。前例中，p(G)=4n集合E(或A)中元素的个数称为图G的边数边数，记作q(G)。前例中，q(G)=7n若e=(u,v)E(或a=(u,v)A)，则称u和v为e(或a)的端点端点，e(

4、或a)称为顶点u和v的关联边关联边，也称u,v与边e(或a)相关联。前例中，A,B是边e1 的端点，e1 是A,B的关联边n若顶点u和v与同一条边相关联，则称u和v为相邻点相邻点n若两条边ei 和ej 有同一个端点，则称ei 和ej 为相邻相邻边边图的基本概念图的基本概念(4)n若一条边的两个端点是同一个顶点，则称该边为环环n若两个端点之间有多于一条边，则称为重边重边(书上称为多重边)，前例中，A,C之间和B,C之间都有两条边n无环也无重边的图称为简单图简单图n与顶点v相关联的边的数目，称为该顶点的“度度”(书上称为次)，记为d(v)n度数为奇数的顶点称为奇点奇点，度数为偶数的顶点称为偶点偶点

5、n在有向图中，由顶点指向外的弧的数目称为正度正度，记为d+，指向该顶点的弧的数目称为负度负度，记为 dn度数为0的点称为孤立点孤立点，度数为1的点称为悬挂点悬挂点图的基本概念图的基本概念(5)n与悬挂点连接的边称为悬挂边悬挂边n若图中所有的点都是孤立点，则称为空图n定理6.1u所有顶点的度数之和，等于所有边数的两倍u原因：每条边关联两个顶点，计算顶点的度数时，每条边计算了2次n定理6.2u图中奇点的个数总是偶数个u原因：所有顶点的度数之和是偶数，偶点的度数之和也是偶数，因此，奇点的度数之和必为偶数，因此，奇点的个数必是偶数个图的基本概念图的基本概念(6)n点边交错序列v0,e1,v1,e2,v

6、2,vn-1,en,vn 称为链链。其中v0称为路的起点，vn称为路的终点n若v0vn，称为开链开链；反之，称为闭链闭链(对于无向图而言，也称为回路)n若链中所含的边均不相同，称为简单链简单链n若链中所含的顶点均不相同，称为初等链初等链(对于无向图而言，也称为通路)n除起点和终点外均不相同的闭链，称为圈圈(对于无向图而言，也称为初等回路)以上概念(除特别标注的外)对无向图和有向图均适用图的基本概念图的基本概念(7)n在有向图中，点边交错序列v0,e1,v1,e2,v2,vn-1,en,vn(其中ek=(vk-1,vk)称为路路n若v0vn，称为开路开路；反之，称为回路回路(注意和无向图的回路区

7、分开来)n若路中所含的边均不相同，称为简单路简单路n若路中所含的顶点均不相同，称为初等路初等路n除起点和终点外均不相同的回路，称为初等回路初等回路(注意和无向图的初等回路区分开来)本页概念都是针对有向图图的基本概念图的基本概念(8)n若一个图(无向图或有向图)中任意两点之间至少有一条初等链连接，则称该图为连通图连通图，否则称为不连通图n在一个有向图中，若任意两点u和v，u到v和v到u之间都至少有一条初等路连接，则称该图为强连通图强连通图，否则称为非强连通图图的基本概念图的基本概念(9)n子图：子图：设G1=(V1,E1)，G2=(V2,E2)，若V1 V2，E1 E2，则称G1是G2的子图n注

8、：注：生成子图时，可以只选顶点不选与该顶点相关联的边，但不能只选边不选与该边相关联的顶点n如下图，右图是左图的子图图的基本概念图的基本概念(10)n如下图，右图是左图的真子图n真子图：真子图：若V1 V2，E1 E2，称G1是G2的真子图n部分图：部分图：若V1=V2，E1 E2，称G1是G2的部分图图的基本概念图的基本概念(11)n导出子图：导出子图：若V1 V2，E1=(ui,vj)E2|ui V1,vj V1，称G1是G2中由V1导出的导出子图，记作G(V1)n如下图，右图是左图的导出子图图的基本概念图的基本概念(12)n一个没有圈的图称为无圈图或称为林林n一个连通的无圈图称为树树n一个

9、林的每个连通子图都是一个树n定理6.3：关于树的以下描述是等价的u无圈连通图(定义)u无圈图G，q(G)=p(G)-1(定义+对顶点个数用归纳法)u连通图G，q(G)=p(G)-1(定义+对顶点个数用归纳法)u无圈，但增加一条边可以得到唯一的圈(定义+对顶点个数用归纳法)u连通，但去掉一条边就不连通(反证法)u每一对顶点之间有且仅有一条初等链(反证法)图的基本概念图的基本概念(13)n若T是图G的部分图，且T是树，则称T为G的生成树生成树(书上称为部分树)图的存储方式图的存储方式(1)n计算机中存储图一般采用矩阵存储n常用的存储方法有两种u邻接矩阵u关联矩阵图的存储方式图的存储方式(2)n对于

10、无向图，邻接矩阵存储方式如下u若顶点vi 和vj 之间没有边，则aij=aji=0u若顶点vi 和vj 之间存在n条边，则aij=aji=nu注：注：一般 i jv1v2v3v4v5图的存储方式图的存储方式(3)v1v2v3v4v5n对于有向图，邻接矩阵存储方式如下u若顶点vi 和vj 之间没有弧，则aij=0u若顶点vi 和vj 之间存在n条弧(vi,vj)，则aij=nu注：注：允许 i=j图的存储方式图的存储方式(4)n对于无向图，关联矩阵存储方式如下u若顶点vi 不和边ej 相关联，则bij=0u若顶点vi 和边ej 相关联，则bij=1v1v2v3v4v5e1e2e3e4e5e6e7

11、e8e9e9 关联的顶点个数为1，是自环图的存储方式图的存储方式(5)n对于有向图，关联矩阵存储方式如下u若顶点vi 不和弧ej 相关联，则bij=0u若顶点vi 是弧ej 的起点，则bij=1u若顶点vi 是弧ej 的终点，则bij=-1u若顶点vi 既是弧ej 的起点又是弧ej 的终点，则bij=2v1v2v3v4v5e1e2e3e4e5e6e7e8e9简单图的权值矩阵简单图的权值矩阵(1)n对于赋权简单图，权值矩阵存储方式如下u若顶点vi 和vj 之间没有边，则wij=0u若顶点vi 和vj 之间有边(vi,vj)，则wij=相应边的权值u注：注：无向图和有向图均适用，有向图要注意边的方

12、向简单图的权值矩阵简单图的权值矩阵(2)v1v2v3v4v5376245v1v2v3v4v5376245最短路线问题最短路线问题n一般针对赋权连通图(有向图或无向图皆可)，求两点之间所经路线权值之和为最小的路线n求解该问题可以采用上一章介绍的动态规划的方法u该方法适用于无负初等回路(指所有边的权值之和为负值的初等回路)的赋权连通图(有向图或无向图皆可)；若有负初等回路，则不存在最短路线u该方法需要人工划分阶段，适合人工计算n书上介绍的三种算法，不需要明确的划分阶段，较为适合计算机运算狄克斯拉狄克斯拉(Dijkstra)算法算法(1)1)n该算法有两个依据u从v1 到vn 的最短路线也是从vn

13、到v1 的最短路线对于无向图必定成立对于有向图而言，vn 到v1 的最短路线是指将图中弧的方向反过来，但权值不变时的最短路线u以vn 为起点，v1 为终点应用动态规划的最优性原理第一条依据保证了按这种方法求得的结果是从v1 到vn 的最短路线狄克斯拉狄克斯拉(Dijkstra)算法算法(2)2)n算法步骤u已知网络的距离矩阵L=(lij)，lij表示vi到vj的弧上的距离权值u令i=1，S1=v1，S2=v2,v3,vn，令P(v1)=0，T(vj)=（vjS2）u令T(vj)=minT(vj)，P(vi)+lij|vjS2u令vk=minT(vj)|vjS2，P(vk)=T(vk)若vk=v

14、n，则已经找到v1到vn的最短距离P(vk)否则，令i=k，从S2中删去vi，转上一步狄克斯拉狄克斯拉(Dijkstra)算法算法(3)3)n该算法适用于无负初等回路的赋权连通图(有向图或无向图皆可)，但算法本身不能判定图中是否存在负初等回路n因此，该算法一般应用于无负权值的赋权连通有向图或无向图示例示例(6.1-1)sabcdt5839149543n路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试用Dijkstra 算法求s到t的最短路线示例示例(6.1-2)sabcdt初始值T()第1次P()+lijT()第2次P()+lijT()第3次P()+lijT()第4次P()+lijT

15、()第5次P()+lijT()00+50+80+0+0+585+5+35+95+88148+8+48+8128+38+9111711+51612345示例示例(6.1-3)sabcdt5839149543海斯算法海斯算法(1)1)n该算法有两个依据u从v1 到vn 的最短路线也是从vn 到v1 的最短路线对于无向图必定成立对于有向图而言，vn 到v1 的最短路线是指将图中弧的方向反过来，但权值不变时的最短路线u若从vi 到vj 的最短路线经过vk，则vi 到vk、vk 到vj 的都是相应的最优路线第一条依据保证了从vi 到vj 的最短路线也是从vj 到vi 的最短路线则根据动态规划最优性原理，

16、vk 到vj 和vk 到vi都是相应的最优路线，由此得到上面的结论海斯算法海斯算法(2)(2)n算法步骤u已知网络的距离矩阵L=(lij)，lij表示vi到vj的弧上的距离权值u令dij(0)=lij，i=1n，j=1ndij(t)表示从vi到vj的2t步距离u当dij(m-1)已知时，令 dij(m)=mindik(m-1)+dkj(m-1)|k=1nu当对所有的i,j有dij(m)=dij(m-1)时，dij(m)是vi到vj的最短距离。否则，若2m-1n-1，m=m+1，转上一步；若2m-1n-1，说明存在负初等回路，最短路线不存在，算法停止海斯算法海斯算法(3)(3)n该算法可以判断是

17、否存在负初等回路，适用于任意权值的赋权连通有向图或无向图n所得的结果矩阵中包含了图中任意两点之间的最短距离示例示例(6.2-1)sabcdt5839149543n路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试用海斯算法求s到t的最短路线示例示例(6.2-2)示例示例(6.2-3)示例示例(6.2-4)n由于D(3)=D(2)，停止计算ns到t 的最短路线长度为16u由D(2)知s到t 经过cu由D(1)知s到c经过a，c到t经过du则最短路线为s a c d tsabcdt5839149543福德福德(Ford)算法算法(1)(1)n该算法和Dijkstra算法一样有两个依据u从v

18、1 到vn 的最短路线也是从vn 到v1 的最短路线对于无向图必定成立对于有向图而言，vn 到v1 的最短路线是指将图中弧的方向反过来，但权值不变时的最短路线u以vn 为起点，v1 为终点应用动态规划的最优性原理第一条依据保证了按这种方法求得的结果是从v1 到vn 的最短路线福德福德(Ford)算法算法(2)(2)n算法步骤u已知网络的距离矩阵L=(lij)，lij表示vi到vj的弧上的距离权值u令dj(1)=l1j，j=1ndj(t)表示从v1到vj的步数不超过t的最短距离u当dj(k)已知时，令dj(k+1)=mindi(k)+lij|i=1nu当对所有的j有dj(k+1)=dj(k)时，

19、dj(k)是v1到vj的最短距离。否则，若kn-1，k=k+1，转上一步；若kn-1，说明存在负初等回路，最短路线不存在，算法停止福德福德(Ford)算法算法(3)(3)n该算法可以判断是否存在负初等回路，适用于任意权值的赋权连通有向图或无向图n所得的结果中包含了从v1到其他任意点的最短距离示例示例(6.3-1)sabcdt5839149543n路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试用Ford 算法求s 到t的最短路线示例示例(6.3-2)abcdd示例示例(6.3-3)n由于dj(4)=dj(3)(j=s,a,b,c,d,t)，停止计算ns到t 的最短路线长度为16n最短

20、路线为s a c d tsabcdt5839149543最小生成树问题最小生成树问题n一般针对赋权连通图，求该图权值之和为最小的生成树n求解该问题一般有两种方法u破圈法u生长法破圈法求最小生成树破圈法求最小生成树n假设原图为赋权连通图n破圈法依据树的定义给出求最小生成树算法n破圈法步骤如下u在图中找到一个圈，进入下一步；若无圈则停止，此时的图就是原图的最小生成树u查看该圈与其它圈是否有公共边若没有公共边，在该圈中选权值最大的边，去掉该边；对新的图返回上一步若有公共边，将这些有公共边的若干个圈合在一起看作一个回路，在该回路中选权值最大的边，去掉该边；对新的图返回上一步示例示例(6.4-1)335

21、4726432n用破圈法求下图的最小生成树生长法求最小生成树生长法求最小生成树(1)n生长法依据u根据动态规划最优性原理，划分n-1个阶段ux1=S1从图中任选一点vi，令S1=vi，S2=V-S1，k=1uuk 为k 阶段选中的权值最小的边(vi,vj)，viS1，vjS2uxk+1=xk+uk+vjS1=S1+(vi,vj)+vj，S2=S2-vjuxn 状态结束此时，S1 就是要求的最小生成树的点边集合，S2 是空集生长法求最小生成树生长法求最小生成树(2)n假设原图为赋权连通图n生长法步骤如下u从图中任选一点vi，令S1=vi，S2=V-S1u从S1中的各点到S2中各点的边中选择权值最

22、小的边(vi,vj)，viS1，vjS2u令S1=S1+(vi,vj)+vj，S2=S2-vju若S2 是空集，则停止，S1 就是要求的最小生成树的点边集合；否则转第二步示例示例(6.5-1)3354726432n用生长法求下图的最小生成树作业作业(17)n书上218页5-1的(b)u补充：3和8之间权值为13u破圈法或生长法皆可最大流问题最大流问题(1)n一般针对赋权连通有向图，每条弧的权值表示该弧允许流过的最大流量，每个顶点的流入量之和等于流出量之和，求图上两定点之间允许流过的最大流量n最大流-最小割定理u最大流量等于最小割集(容量最小的割集)的容量u注：注：将图G中顶点集合V分为两个集合

23、S1和S2，其中起点vsS1、终点vtS2，且S1S2=V、S1S2=，则把集合C=(vi,vj)|viS1,vjS2 称为图G的一个割集割集割集中弧的权值之和称为该割集的容量割集的容量最大流问题最大流问题(2)n利用最大流-最小割定理，福德和富克逊提出了求解最大流问题的标号法可行流可行流最大流最大流结束结束改变流量改变流量是否最大流问题最大流问题(3)n标号法相关概念u若弧(vi,vj)上的流量xij=bij，则称该弧为饱和弧，否则称为非饱和弧u若弧(vi,vj)上的流量xij=0，则称该弧为零流弧，否则称为非零流弧u在一条从vs 到vt 的点边交错序列中，与vs 到vt 方向一致的弧称为正

24、向弧，与vs 到vt方向相反的弧称为逆向弧u若从vs 到vt 的某个点边交错序列中，正向弧均为非饱和弧，逆向弧均为非零流弧，则称该点边交错序列为一条流量增广链最大流问题最大流问题(4)n流量增广链的作用u它是用来增加正向总流量的使增广链上正向弧的流量增大使增广链上逆向弧的流量减小u若找不到，表示不能再增大正向总流量，即当前的正向总流量就是最大流量最大流问题最大流问题(5)n标号法步骤如下u分配vi 到vj 的初始流xiju寻找增广链，若不存在，则已经最优；否则进入下一步调整。寻找增广链方法如下将vs 标记上(-,)，S1=vs，S2=V-S1若存在以S1中点为起点、以S2中点为终点的非饱和弧(

25、vi,vj)，则为vj 标记上(vi+,zj)，zj=minzi,bij-xij，S1=S1+vj，S2=S2-vj若存在以S2中点为起点、以S1中点为终点的非零流弧(vj,vi)，则为vj 标记上(vi-,zj)，zj=minzi,xji，S1=S1+vj，S2=S2-vj若S1中已包含vt，则已找到一条增广链，否则转向第二步最大流问题最大流问题(6)u调整流量，方法如下设vt 上的标记为(vk+,zt)，则整个增广链上最大的调整量为z=zt由vt 上的标记可以得到增广链上的前一个顶点vk，依次向前可以找到整个增广链在增广链上，正向弧流量增加z，逆向弧流量减少zu返回第二步继续寻找下一个增广

26、链示例示例(6.6-1)(9)(8)(3)(7)(4)(4)(2)(6)(11)711106915543vsvtv2v3v4v5(-,)(vs+,7)(v2-,3)(v3+,1)(v3+,3)(v5+,3)n用标号法求出从vs 到vt 的最大流示例示例(6.6-2)n调整流量，得711106915543vsvtv2v3v4v5(11)(0)(9)(7)(4)(4)(5)(9)(11)(-,)(vs+,4)n找不到增广链，则当前流量20为最优最小费用最小费用-最大流问题最大流问题(1)n一般情况下，最大流量是唯一的，而相应的每条弧上的流量分布却是不唯一的n如果已知流过弧(vi,vj)的单位流量要

27、发生cij 的费用，要求使得总费用为最小的最大流流量分配方案，这种问题称为最小费用-最大流问题n可以使用对偶法解决这个问题最小费用最小费用-最大流问题最大流问题(2)n对偶法原理u对原图求出从vs 到vt 的所有初等路u将这些初等路按照单位流量费用之和从小到大排序，编号1,2,3,mu使第1号初等路上的流量为最大u在余下的允许流量中，使第2号初等路上的流量为最大u在余下的允许流量中，使第3号初等路上的流量为最大uu在余下的允许流量中，使第m号初等路上的流量为最大u此时，图中的流量分布即为最小费用-最大流n在实际使用时，要对原图求出从vs 到vt 的所有初等路有一定的难度，容易遗漏最小费用最小费

28、用-最大流问题最大流问题(3)n因此，对偶法在实际操作时u求出最大流量，以0流为初始可行流u对原图求出从vs 到vt 的单位流量费用之和为最小的初等路u调整使得该初等路上的流量为最大，若当前可行流的流量等于最大流量，则当前可行流就是最小费用-最大流，否则进入下一步u对当前可行流生成扩展费用图。在扩展费用图中，从原图的允许流量中去掉当前可行流的流量，将图中某些弧的单位流量费用调整为(这些弧的允许流量已经减小为0，使得此弧不通)u在该扩展费用图中，求出新的从vs 到vt 的单位流量费用之和为最小的初等路，转向第三步最小费用最小费用-最大流问题最大流问题(4)n对偶法步骤u用标号法求出最大流量u将原

29、图作为初始扩展费用图，以0流作为初始可行流u在扩展费用图上，用Ford 算法求出从vs 到vt 的单位流量费用之和为最小的初等路作为增广链u按前面标号法中调整流量的方法调整流量，得到一个新的可行流u若当前可行流的流量等于最大流量，则当前可行流就是最小费用-最大流，否则进入下一步u对当前可行流生成新的扩展费用图，转向第三步最小费用最小费用-最大流问题最大流问题(5)n扩展费用图的生成u在弧(vi,vj)上若xij=0，则原弧不变若0 xij bij，则把弧(vi,vj)改造成如下的两条弧若xij=bij，则把弧(vi,vj)改造成方向相反的另一条弧vivj(bij-xij,cij)(xij,-c

30、ij)vivj(bij,cij)在生成增广链时用不到反向弧(vj,vi)，这样就去掉了当前可行流的流量同理，使得弧(vi,vj)不通，将其单位流量费用调整为示例示例(6.7-1)n求出从vs 到vt 的最小费用-最大流，图中弧上数字含义为(bij,cij)vsvtv2v4v3v5(15,2)(9,6)(3,3)(5,5)(4,9)(7,8)(6,3)(10,1)(11,3)示例示例(6.7-2)n由示例(6.6)，如下图，已知从vs 到vt 的最大流量为20vsvtv2v4v3v5(15,2)(9,6)(3,3)(5,5)(4,9)(7,8)(6,3)(10,1)(11,3)示例示例(6.7-

31、3)n初始扩展费用图如下所示vsvtv2v4v3v5(15,2)(9,6)(3,3)(5,5)(4,9)(7,8)(6,3)(10,1)(11,3)n求出了增广链示例示例(6.7-4)n初始流量为0，在增广链上调整流量，得vsvtv2v4v3v5(15,2,0)(9,6,6)(3,3,0)(5,5,0)(4,9,0)(7,8,0)(6,3,6)(10,1,6)(11,3,0)n当前可行流流量为620，需要继续调整示例示例(6.7-5)n对当前可行流生成新的扩展费用图为vsvtv2v4v3v5(15,2)(3,6)(3,3)(5,5)(4,9)(7,8)(6,3)(4,1)(11,3)(6,-6

32、)(6,-1)n求出了增广链示例示例(6.7-6)n当前流量为6，在增广链上调整流量，得n当前可行流流量为1020，需要继续调整vsvtv2v4v3v5(15,2,4)(9,6,6)(3,3,0)(5,5,0)(4,9,4)(7,8,0)(6,3,6)(10,1,10)(11,3,0)示例示例(6.7-7)n对当前可行流生成新的扩展费用图为n求出了增广链vsvtv2v4v3v5(11,2)(3,6)(3,3)(5,5)(4,9)(7,8)(6,3)(10,1)(11,3)(6,-6)(4,-2)示例示例(6.7-8)n当前流量为10，在增广链上调整流量，得n当前可行流流量为1720，需要继续调

33、整vsvtv2v4v3v5(15,2,11)(9,6,6)(3,3,0)(5,5,0)(4,9,4)(7,8,7)(6,3,6)(10,1,10)(11,3,7)示例示例(6.7-9)n对当前可行流生成新的扩展费用图为n求出了增广链vsvtv2v4v3v5(4,2)(3,6)(3,3)(5,5)(4,9)(7,8)(6,3)(10,1)(4,3)(6,-6)(11,-2)(7,-3)示例示例(6.7-10)n当前流量为17，在增广链上调整流量，得n当前可行流流量为20，等于最大流量，不需要调整，当前可行流就是最小费用-最大流vsvtv2v4v3v5(15,2,11)(9,6,9)(3,3,0)(5,5,3)(4,9,4)(7,8,7)(6,3,6)(10,1,10)(11,3,10)作业作业(18)n书上220页的5-5u是一个最小费用-最大流问题