运筹学基础及应用第五版课件

1、运筹学基础及应用第五版,第6章 图与网络分析,Graph and Network Analysis,运筹学基础及应用第五版,图是一种模型，如公路铁路交通图，水或煤气管网图，通讯联络图等。,图是对现实的抽象，用点和线的连接组合表示。,6.1 图的基本概念和模型,图不同于几何图形。,运筹学基础及应用第五版,一、基本概念,1、图(graph)：由V,E构成的有序二元组，用以表示对某些现实对象及其联系的抽象，记作 G=V,E。 其中V称为点集，记做V=v1,v2,vn E称为边集，记做E=e1,e2,em,点(vertex)：表示所研究的对象，用v表示； 边(edge)：表示对象之间的联系，用e表示。

2、,网络图(赋权图)： 点或边具有实际意义(权数)的图，记做N。,零图： 边集为空集的图。,运筹学基础及应用第五版,v1,v2,v3,v4,v5,e1,e2,e3,e4,e5,e6,e7,e8,特别的，若边e的两个端点重合，则称e为环。,若两个端点之间多于一条边，则称为多重边。,2、图的阶：即图中的点数。 例如 右图为一个五阶图,3、若图中边e= vi,vj ,则vi,vj称为e的端点， e称为vi,vj的关联边。 若vi与vj是一条边的两个端点，则称vi与vj相邻； 若边ei与ej有公共的端点，则称ei与ej相邻。,简单图：无环、无多重边的图。,例如：e6= v2,v3,运筹学基础及应用第五版

3、,4、点v的次（或度，degree） 与点v关联的边的条数，记为dG(v)或d(v)。,v1,v2,v3,v4,e1,e2,e3,e4,e5,e6,e7,v5,悬挂点 次为1的点，如 v5,悬挂边 悬挂点的关联边，如 e8,e8,孤立点 次为0的点,偶点 次为偶数的点，如 v2,奇点 次为奇数的点, 如 v5,运筹学基础及应用第五版,5、链：图中保持关联关系的点和边的交替序列，其中点可重复，但边不能重复。,路：点不能重复的链。 圈：起点和终点重合的链。 回路：起点和终点重合的路。 连通图：任意两点之间至少存在一条链的图。 完全图：任意两点之间都有边相连的简单图。 n阶完全图用Kn表示，边数=,

4、注意：完全图是连通图，但连通图不一定是完全图。,运筹学基础及应用第五版,v1,v2,v5,v6,v7,v3,v4,e1,e2,e4,e3,e5,e6,e7,e8,e9,如图(v1,e1,v2,e2,v3,e3,v4,e5,v5,e6,v3,e7,v6,e8,v7)是一条链, 但不是路,(v1,e1,v2,e2,v3,e7,v6,e8,v7)是一条路,(v1,e1,v2,e2,v3,e3,v4,e4,v1)是一个回路,( v4,e4,v1,e1,v2,e2,v3,e6,v5,e9,v7,e8,v6,e7,v3,e3,v4)是一个圈,本图是一个连通图。,运筹学基础及应用第五版,7、已知图G1=V1

5、,E1, G2=V2,E2, 若有V1V2，E1E2，则称G1是G2的一个子图； 若V1=V2，E1E2且 E1E2 ，则称G1是G2的一个部分图。,6、偶图（二分图）：若图G的点集V可以分为两个互不相交的非空子集V1和V2，而且在同一个子集中的点均互不相邻，则图G称为偶图。 完全偶图：V1中的每个点均和V2中的每个点相邻的偶图。 若完全偶图中V1有m个点，V2有n个点，则该图共有mn条边。,注意：部分图是子图，子图不一定是部分图。,运筹学基础及应用第五版,二、应用,例 有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如表中所示，打“”的项目是各运动员报名参加比

6、赛的项目。问：六个项目的比赛顺序应如何安排，才能做到使每名运动员不连续地参加两项比赛？,甲 乙 丙 丁 戊 己,项目,人,ABCDEF,运筹学基础及应用第五版,解：构造一个六阶图如下：,点：表示运动项目。,边：若两个项目之间有同一名运动员报名参加，则对应的两个点之间连一条边。,A,B,C,D,E,F,ACBFED,为满足题目要求，应该选择不相邻的点来安排比赛的顺序：,或DEFBCA,运筹学基础及应用第五版,6.2 树图和图的最小部分树,1、树（tree）：无圈的连通图称为树图，简称为树,用T(V,E)或T表示。,一、树图的概念,运筹学基础及应用第五版,2、树的性质,（1）树中必有悬挂点。,证明

7、（反证法）： 设树中任何点的次均不为1. 因为树无孤立点，所以树的点的次2. 不妨设树有n个点，记为v1,v2,vn 因为d(v1)2,不妨设v1与v2,v3相邻。 又因为树没有圈，且d(v2)2,可设v2与v4相邻，, 依次下去，vn必然与前面的某个点相邻，图中有圈，矛盾！,注意：树去掉悬挂点和悬挂边后余下的子图还是树。,运筹学基础及应用第五版,（2）n阶树必有n-1条边。,证明（归纳法）： 当n=2时，显然； 设n=k-1时结论成立。 当n=k时，树至少有一个悬挂点。 去掉该悬挂点和悬挂边，得到一个k-1阶的树，它有k-2条边，则原k阶树有k-1条边。 即n=k时结论也成立。 综上，n阶树

8、有n-1条边。,运筹学基础及应用第五版,（3）任何有n个点、n-1条边的连通图是树。,证明（反证法）： 假设n个点，n-1条边的连通图中有圈，则在该圈中去掉一条边得到的子图仍连通，若子图仍有圈，则继续在相应圈中去掉一条边，直到得到无圈的连通图，即为树。但是该树有n个点，边数少于n-1,矛盾！,注意： 树是边数最多的无圈图。, 树是边数最少的连通图。,在树中不相邻的两个点之间添上一条边，则恰得到一个圈。,从树中去掉一条边，则余下的图不连通。,运筹学基础及应用第五版,3、图的最小部分树,（1）部分树：若G1是G2的一个部分图，且G1为树，则称G1是G2的一个部分树（或支撑树）。,G2：,A,B,C

9、,D,5,4,7,3,6,5,5,7,6,G1：,A,C,B,D,注意： 图G有部分树的必要条件是G是连通图。 部分树不是唯一的。,运筹学基础及应用第五版,（2）最小部分树（或最小支撑树）,图G为网络图，若T是部分树中权和最小者，则称T是G的最小部分树(或称最小支撑树).,运筹学基础及应用第五版,二、最小部分树的求法,1、原理 （1）图中与点v关联的最短边（即权最小的边）一定包含在最小部分树中。 （2）将图中的点分成两个互不相交的非空子集，则两个子集之间连线的最短边一定包含在最小部分树中。,运筹学基础及应用第五版,S,A,B,C,D,E,T,2,5,2,4,1,4,3,1,7,5,5,7,即求

10、图中的最小部分树,例：要在下图所示的各个位置之间建立起通信网络，试确定使总距离最小的方案。,运筹学基础及应用第五版,2、求法,方法一： 避圈法 将图中所有的点分V为V两部分，V最小部分树中的点的集合 V非最小部分树中的点的集合, 任取一点vi，令viV，其他点在V中 在V与V相连的边中取一条最短的边(vi,vj)， 加粗(vi,vj)，令vjV，并在V中去掉vj 重复 ，至所有的点均在V之内。,“取小边”,运筹学基础及应用第五版,避圈法另一种做法：,1. 在所有各边中找到边权最小的一条，将其作为最小部分树中的第一边；在剩余的边中，仍然找到边权最小的作为最小部分树的第二条边；,2. 在剩余的边中

11、，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则在最小部分树中添加该边，如果形成了圈，则不再考虑该边；,3. 重复进行第二步，直到找到第 n-1 条边为止。（因为有 n 个顶点的树中一定有 n-1 条边）,运筹学基础及应用第五版,例：分别用两种避圈法构造下图的最小部分树。,第一种解法：,1. 在点集中任选一点，不妨取 S，令 V=S,2. 找到和 S 相邻的边中，权值最小的 S , A 。,运筹学基础及应用第五版,3. V=S , A,4. 重复第2，3步，找到下一个点。,运筹学基础及应用第五版,第二种做法求解过程：,运筹学基础及应用第五版,方法二：破圈法求解步骤：,1. 从图 N

12、 中任取一回路，去掉这个回路中边权最大的边，得到原图的一个子图 N1。,2. 从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；,3. 重复第 2 步，直到图中不再含有回路为止。,用破圈法求解上例：,1. 任意找到一回路，不妨取 DETD，去掉边权最大的边T , E;,运筹学基础及应用第五版,2. 从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；依次类推。,运筹学基础及应用第五版,破圈法的另一种解法：,1. 从剩余图中找到边权最大的一条边，如果将其删除后图仍然是连通的，则删除此边，否则不再考虑此边；,2. 重复上述步骤，直到剩余边数为 n-1 为止

13、。,用此法求解上述问题：,运筹学基础及应用第五版,注意：,1. 一个图的最小部分树不唯一，该题中用几种解法得到的结果都是相同的，是特殊情况；,2. 不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。,运筹学基础及应用第五版,6.3 最短路问题,1、最短路问题 从已知的网络图中找出两点之间距离最短（即权和最小）的路。,2、相关记号 （1）dij表示图中两个相邻点i和j之间的距离（即权）。 易见 dii=0 约定：当i和j不相邻时，dij=,（2）Lij表示图中点i和j之间的最短距离（即最小权和）。 易见 Lii=0,运筹学基础及

14、应用第五版,即在已知的网络图中，从给定点s出发，要到达目的地t。问：选择怎样的行走路线，可使总行程最短？,3、狄克斯屈拉（Dijkstra）标号算法,（1）适用范围 用于求某两个点之间的最短距离。,（2）原理 最短路上任何片段是最短路。,v1 v2 v3 v4,v5,（3）思想 按离出发点s的距离由近至远逐步标出最短距离Lsi以及最佳行进路线。,运筹学基础及应用第五版,S,A,B,C,D,E,T,2,5,2,4,1,4,3,1,7,5,5,7,例 求图中S到T的最短路及最短距离。,运筹学基础及应用第五版,（4）步骤 在网络图中求s到t的最短路。,第一步 从s出发，将Lss=0标记在s旁边的方框

15、内（表示点s已标记）； 第二步 找出与s相邻且距离最小的点，设为r，计算Lsr=Lss+dsr，并将结果标记在r旁边的方框内（表示点r已标记），同时标记边sr； 第三步 从已标记的点出发，找出这些点的所有未标记邻点，分别计算已标记点的方框数与其邻点的距离之和，利用“叠加最小”的原则确定下一个被标记点，设为p，并将最小的和标记在p旁边的方框内（表示点p已标记）,同时标记相应边； 第四步 重复第三步，直到t得到标记为止。,运筹学基础及应用第五版,S,A,B,C,D,E,T,2,5,2,4,1,4,3,1,7,5,5,7,0,2,4,4,7,8,9,14,13,5,9,4,最短路：S AB E D

16、T 最短距离：LST=13,例 求图中S到T的最短路及最短距离。,运筹学基础及应用第五版,V1,V2,V3,V4,V5,V6,V7,5,2,2,7,6,7,4,2,1,3,6,例 求图中v1到v7的最短路。,0,5,2,7,7,6,10,运筹学基础及应用第五版,例 求图中任意两点之间的最短距离。,V1,V2,V3,V4,V6,V7,5,2,2,7,6,7,4,2,1,3,6,运筹学基础及应用第五版,4、矩阵算法 求任意两点间最短距离的方法, 构造任意两点间直接到达的最短距离矩阵 记做D(0)= dij(0) 其中dij(0)=dij,注意：D(0)是一个对称矩阵，且对角线上的元素全是0.,D（

17、0）=,运筹学基础及应用第五版,其中 dij（1）= min dir（0）+ drj（0）,i,r,j,dir（0）,drj（0）,r, 构造任意两点间直接到达、或者最多经过1个中间点到达的最短距离矩阵D（1）= dij（1）,即dij(1)为D(0)中第i行和第j列对应元素之和的最小值,D（1）=,运筹学基础及应用第五版,其中 dij（2）= min dir（1）+ drj（1）,i,r,j,dir（1）,drj（1）,r, 构造任意两点间最多可经过3个中间点到达的最短距离矩阵 D（2）= dij（2）,即dij(2)为D(1)中第i行和第j行对应元素之和的最小值,D（2）=,运筹学基础及应

18、用第五版,其中 dij（3）= min dir（2）+ drj（2） ,i,r,j,dir（2）,drj（2）,r, 构造任意两点间最多可经过7个中间点到达的最短距离矩阵 D（3）= dij（3）,即dij(3)为D(2)中第i行和第j行对应元素之和的最小值,D（3）=,= D（2）,故D(2)中的元素就是图中相应两点之间的最短距离。,运筹学基础及应用第五版,说明： 一般的对于D（k）= dij（k）， 其中 dij（k）= min dir（k-1）+ drj（k-1） ，(k=0,1,2,3,) 最多可经过2k-1个中间点,收敛条件： 当 D（k+1）= D（k）时，计算结束； 设网络图有p

19、个点，即最多有p-2个中间点， 则 2k-1-1 p-2 2k-1 k-1log2 (p-1) k klog2(p-1)+1， 即计算到 k= lg(p-1)/lg2 +1 时，计算结束。,运筹学基础及应用第五版,运筹学基础及应用第五版,例：下图中v1v7表示7个村子，需要联合建立一所小学，已知各村小学生的人数分别为v130人， v240人，v325人，v420人，v550人，v660人， v760人。问：学校应建在哪一个村子，可使学生总行程最少？,V1,V2,V3,V4,V6,V7,5,2,2,7,6,7,4,2,1,3,6,V5,运筹学基础及应用第五版,解：用矩阵算法得到任意两个村子之间的

20、最短距离如下：,先将每一行的元素乘以该村子的学生人数，得到小学建在相应村子时，该村学生上学时单程所走的路程。 再将每一列的元素累加，得到小学建在相应村子时，七个村子的学生上学时单程所走的总路程。,运筹学基础及应用第五版,故小学应该建在v6村。,运筹学基础及应用第五版,v1,S,v2,v3,v4,T,6.4 网络的最大流,v1,S,v2,v3,v4,T,运筹学基础及应用第五版,一、基本概念和基本结论,2、图的分类 （1）无向图（简称图）记做G=(V,E)，V、E分别为点集和边集。 （2）有向图 记做D=(V,A），V、A分别为点集和弧集。 注意：以下讨论的是有向图。,3、弧的容量（简称容量）：弧

21、(vi,vj)上可通过负载的最大能力。用c(vi,vj)或cij表示。,1、图中两点vi与vj之间的连线有两种情况 （1）边（edge）:未规定方向的连线，记做vi,vj ,其中vi,vj称为端点 （2）弧（arc）:规定方向的连线，记做(vi,vj)，其中vi称为起点，vj称为终点,运筹学基础及应用第五版,4、容量网络（简称网络）：每条弧都有容量的网络。,8,v1,S,v2,v3,v4,T,7,9,9,2,6,5,10,5,例如：,5、容量网络中点的分类,发点（源点）：用S表示，“只出不入” 收点（汇点）：用T表示，“只入不出” 中间点：“有入有出”,注意：任意容量网络总可以转换为只有一个发

22、点和一个收点的情况。,运筹学基础及应用第五版,6、流（flow）：加在网络中弧(vi,vj)上的一组负载量，用f(vi,vj)或fij表示。,8(8),v1,s,v2,v3,v4,t,7(5),9(4),9(9),2(0),6(1),5(5),10(8),5(4),其中cij (fij),该流为可行流,运筹学基础及应用第五版,10、网络的最大流：即使V(f)达到最大的可行流。,8、 零流：加在每条弧上的流量全为0。 易见：零流一定是可行流。 每个容量网络都有可行流。,9、 总流量：从发点s到收点t的流量,记做V( f ),7、可行流(记做f )：能够在网络中通过的流，必须满足以下两个条件： 容

23、量限制条件：对所有弧，0 fijcij 中间点平衡条件： 对任何一个中间点，流入量=流出量,运筹学基础及应用第五版,12、割的容量：割集中各弧的容量之和。,13、最小割：所有割集中容量之和最小的一个割集。,11、割集（简称割）：一组弧的集合，割断这些弧能使从s到t的流中断。,定理：网络的最大流量等于它的最小割集的容量。,8(8),v1,s,v2,v3,v4,t,7(5),9(4),9(9),2(0),6(1),5(5),10(8),5(4),例如：割集=(v1,v3),(v2,v4),割的容量=9+9=18,运筹学基础及应用第五版,14、前向弧（或正向弧）：在从发点s到收点t的一条链中，指向为

24、s到t的弧称为前向弧，记做 +。,16、增广链：对于从s到t的一条链，如果在前向弧上满足流量小于容量，即fij0（即后向弧不为0），则称这样的链为增广链。,15、后向弧（或逆向弧）：在从发点s到收点t的一条链中，指向为t到s的弧称为后向弧，记做 -。,s,t,6(4),5(3),4(4),8(7),+,+,+,-,这是一条增广链,定理：当网络中不存在增广链时，网络达到最大流状态。,运筹学基础及应用第五版,二、网络最大流的求法 标号算法(Ford-Fulkerson标号算法),1、基本思想： 寻找增广链； 若无增广链，则已经得到最大流和最小割，结束； 若有增广链，则改善流量分布，再重复寻找，直到

25、不存在增广链为止。,2、点v的标号 v( x,(v) 其中x是使v得到标号的已标号点， (v)是从x到v的流量的最大可调值。,标号算法下规定:前向弧是已标号点指向未标号点的弧,后向弧是未标号点指向已标号点的弧.,运筹学基础及应用第五版,3、步骤：, 对发点s标号：s（0，+）,从已标号点i出发，看与其相邻的未标号点j之间的弧， 对前向弧+ 若满足 fijcij，则对点j标号（i, (j)）， 其中 (j)=min (i) ，cij - fij 对后向弧- 若满足fji0，则对点j标号（ i,(j)）， 其中 (j)=min (i) ，fji （注：若有多个可标号点，可任选。） 若出现其他情况，

26、则点j不标号。,前向弧不饱和，要标号,后向弧不为0，要标号,运筹学基础及应用第五版,当t得到标号时，从t开始沿已标号点用反向追踪法得到增广链，利用(t)调整流量： 对前向弧+，新流量f ij = fij + (t) 对后向弧-，新流量f ij = fij - (t) 其余弧上的流量不变。, 去掉所有标号，重复。,若标号中断，即t没有得到标号，则该流为所求的网络最大流（此时最小割集为已标号点与未标号点之间的前向弧），结束；否则重复，继续标号，直到收点t得到标号，转。,运筹学基础及应用第五版,8(8),v1,s,v2,v3,v4,t,7(5),9(4),9(9),2(0),6(1),5(5),10

27、(8),(0,+),(s,2),(v2,2),(v1,2),(v3,1),(v4,1),5(4),cij,fij,例 求网络的最大流。,最大可调量为1,7(6),5(3),9(5),6(0),10(9),运筹学基础及应用第五版,8(8),v1,s,v2,v3,v4,t,7(6),9(5),9(9),2(0),6(0),5(5),10(9),5(3),(0,+),(s,1),(v2,1),(v1,1),最大流 V（f）=14,最小割集：(v3, t), (v2, v4)割集容量之和=14,标号中断！,运筹学基础及应用第五版,例 某河流中有4座岛屿B、C、D、E与河岸A、F之间有数座桥相连，问至少

28、需要炸毁几座桥，才可以中断两岸的交通联系？,A,B,C,D,E,F,运筹学基础及应用第五版,A,B,C,F,E,D,2,2,2,1,3,1,1,1,1,解：建立6阶容量网络， 弧上的容量表示相应位置的桥数：,运筹学基础及应用第五版,A,B,C,F,E,D,2(1),2(0),2(1),1(0),3(1),1(1),1(1),1(1),1(1),A,B,C,F,E,D,2(1),2(1),2(1),1(1),3(2),1(1),1(0),1(1),1(1),任取一个可行流：,用标号算法找到最大流：,最大流V(f)=3， 最小割=（A,E），（D,E），（D,F） 故至少要炸毁3座桥。,(0, +),(A, 1),(A, 1),(B, 1),运筹学基础及应用第五版,A,B,C,D,E,F,运筹学基础及应用第五版,6.5 中国邮路问题,问题：一名邮递员从邮局出发，试选择一条最短的投递路线？,v1,v2,v3,v4,v5,v6,v8,v7,v9,v10,v11,v12,v13,邮局,4,4,4,5,5,1,2,4,1,2,5,4,4,7,4,2,2