运筹学OR1-Ch9-图与网络课件

1、9-1 图的基本概念 Basic Concepts of Graph9-2 最小树问题 Minimum Spanning Tree Problem9-3 最短路问题 Shortest Path Problem 9-4 最大流问题 Maximum Flow Problem第九章 图与网络Ch9 Graph and NetworkACBDCBA引例：哥尼斯堡七桥问题您能从A、B、C或D任意一点出发走遍7座桥并且每座桥只走一次最后回到原出发点吗？D9-1 图的基本概念Basic Concepts of Graph*Page 2 of 46 图可 定义为点和边的集合，记作 式中是点的集合，是边的集合。

2、注意上面定义的图区别于几何学中的图。在几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连，如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等，把这样的图称为网络图，记作。图和网络分析的方法已广泛应用于物理、化学、控制论、信息论、计算机科学和经济管理等各个领域。9-1 图的基本概念Basic Concepts of Graph*Page 3 of 46 v3e7e4e8e5e6e1e2e3v1v2v4v5例如图91：端点，关联边，相邻 若有边e可表示为e=vi,vj,称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、v

3、j与同一边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。例如图91，v2和v4是边e6的端点，反之边e6是点v2、v4的关联边。点v2、v4相邻；边e6与e5、 e4j相邻。图91e2可记作：9-1 图的基本概念Basic Concepts of Graph*Page 4 of 46 环，多重边，简单图 如果边e的两个端点相重，称该边为环。如图中边e1为环。如果两个点之间多于一条，称为多重边，如图中的e4和e5，对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5 次，奇点，偶点，孤立点 与某一个点vi相关联的边的数目称为点vi的次

4、（也叫做度），记作d(vi)。图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为0的点称作孤立点。图的次 一个图的次等于各点的次之和。9-1 图的基本概念Basic Concepts of Graph*Page 5 of 46 链、路、回路（圈） 图中有些点和边的交替序列对任意vi,t1 和vit(2tk)均相邻，称从v0到vk的链。如果链中所有的顶点v0，v1，vk也不相同，这样的链称初等链（路）。如果链中各边e1,e2,ek互不相同称为简单链。当v0与vk重合时称为回路（圈），如果边不重复称为简单回路（圈）v3e7e4e8e5e6e1e2e3v

5、1v2v4v5图91中， 1=v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v4是一条链，1中因顶点v3重复出现，不能称作路（初等链）。9-1 图的基本概念Basic Concepts of Graph*Page 6 of 46 是一条链也是一条路。是一条回路并且是简单回路。v3e7e4e8e5e6e1e2e3v1v2v4v5连通图若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的。图61是连通图。3=v4,e7,v3,e3,v1,e2,v2,e6,v49-1 图的基本概念Basic Concepts of Graph*Page 7 of 4

6、6 子图、支撑子图图G1=V1、E1和图G2=V2，E2如果 称G1是G2的一个子图。若有 则称 G1是G2的一个支撑子图（部分图），图9-2（a）是图 9-1的一个子图，图9-2（b）是图 8-1的支撑子图，注意支撑子图也是子图,子图不一定是支撑子图。v3e7e6e1e2e3v1v2v4v5e4v3e8e5e6v2v4v5图92(a)v3e7e4e8e5e6e1e2e3v1v2v4v5图92(b)9-1 图的基本概念Basic Concepts of Graph*Page 8 of 46 有向图 如果图的每条边都有一个方向则称为有向图混合图 如何图G中部分边有方向则称为混合图有向图9-1 图

7、的基本概念Basic Concepts of Graph*Page 9 of 46 赋权图设图G（V，E），对G的每一条边(vi,vj)相应的有一条数w (vi,vj) (或记为wij)，wij称为边(vi,vj)的权,赋有权的图G称为赋权图。这里的权数可以是时间、费用、距离等，视不同背景代表不同的含义。910201571419256赋权图9-1 图的基本概念Basic Concepts of Graph*Page 10 of 46 网络图在一个有向赋权图G 中规定了一个起点（发点）和一个终点（收点），其余是中间点，这样的图称为网络。9102015714192561130起点为v1终点为v7的

8、一个网络图9-1 图的基本概念Basic Concepts of Graph*Page 11 of 46 树、支撑树：无圈的连通图称为树； 若G1是G2的一个支撑子图并且是一棵树，则称G1是G2的一棵支撑树。图92(a)、92(b)都不是树。想一想，为什么？图93(a)是一棵树，图93(b)是图91的一棵支撑树。v3e7e4e8e5e6e1e2e3v1v2v4v5v1v1图91图93(a)图93(b)v3e2e3v2v5v3e7e8e6e2v2v4v59-1 图的基本概念Basic Concepts of Graph*Page 12 of 46 【性质1】任何树中必存在次为1的点。【性质2 】

9、具有n个顶点的树的边数恰好为（n1）条 【性质3 】任何具有n个点、(n1)条边的连通图是树图。 9-1 图的基本概念Basic Concepts of Graph*Page 13 of 46 定义：设GV,E是一个无向图，对每一条边eiE有一个长度C(ei) 0,G的任意支撑树T各条边的长度之和称为树T的长度，记为C（T）。长度最小的支撑树称为最小树。求最小树是在一个无向连通图G中求一棵最小支撑树。求最小树问题的应用： 电信网络（计算机网络、电话专用线网络、有线电视网络等 等）的设计 低负荷运输网络的设计，使得网络中提供链接的部分（如铁路、公路等 等）的总成本最小 高压输电线路网络的设计电器

10、设备线路网络（如数字计算机系统）的设计，使得线路总长度最短 连接多个场所的管道网络设计 9-2 最小树问题 Minimum Spanning Tree Problem*Page 14 of 46 求最小树的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。v1v2v3v4v5v6435215v1v2v3v4v5v68437526189-2 最小树问题 Minimum Spanning Tree Problem*Page 15 of 46 v1v2v3v4v5v643521得到最小树：Min C(T)=159-2 最小树问题 Minimum Spanning Tree Proble

11、m*Page 16 of 46 加边法：去掉G中所有边，得到n个孤立点；然后加边；加边的原则：从最短边开始添加，加边的过程中不能形成圈，直到连通（n1条边）。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521Min C(T)=159-2 最小树问题 Minimum Spanning Tree Problem*Page 17 of 46 作业：P283 10.4 10.59-2 最小树问题 Minimum Spanning Tree Problem*Page 18 of 46 最短路问题 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题

12、，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。求最短路有两种算法，一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法；另一种是求网图上任意两点之间最短的矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 .9-3 最短路问题 Shortest Path Problem*Page 19 of 46 渡河问题 一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上

13、来回次数最少？这个问题就可以用求最短路方法解决。设：M人 W狼 S羊 V白菜渡河方案共有10种，构造如下一个图，每条边的距离为1，问题变为求一条从MWSV到的最短路。北岸南岸9-3 最短路问题 Shortest Path Problem*Page 20 of 46 狄克斯屈拉(Dijkstra)标号算法点标号：b(j) 起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+dij，步骤：1.令起点的标号；b(s)0。先求有向图的最短路，设网络图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为（i，j）,距离为dij 2.找出所有vi已标号vj未标号的弧集合 B= （i，j） 如

14、果这样的弧不存在或vt已标号则计算结束；3.计算集合B中弧k(i，j)=b(i)+dij的标号4.选一个点标号返回到第2步。9-3 最短路问题 Shortest Path Problem*Page 21 of 46 【例】求下图v1到v7的最短路长及最短路线86252353421057086225441114751071211v7已标号，计算结束。从v1到v7的最短路长是 11最短路线是： v1 v4 v6 v79-3 最短路问题 Shortest Path Problem*Page 22 of 46 从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号

15、，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj .无向图最短路的求法无向图最短路的求法只将上述步骤2 改动一下即可。点标号：b(i) 起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+dij，步骤：1.令起点的标号；b(s)0。3.计算集合B中边标号：ki，j=b(i)+dij4.选一个点标号: 返回到第2步。 2.找出所有一端vi已标号另一端vj未标号的边集合 B= i，j 如果这样的边不存在或vt已标号则计算结束；9-3 最短路问题 Shortest Path Problem*Page 23 of 46 【例】求下图v1到各点的最短路及最短距离45261

16、78393261216180452231039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。9-3 最短路问题 Shortest Path Problem*Page 24 of 46 有负权的最短路算法假设图中没有负回路。如下图是一条负回路，最短路权无下界。322当vi到vj之间没有弧连接时，令wij列表迭代计算：设vs到vj经过vi到达vj，则vs到vj的最短距离为：迭代：9-3 最短路问题 Shortest Path Problem*Page 25 of 46 【例】求下图v1到v8的最短路长及最短路线9-3 最短路问题

17、 Shortest Path Problem*Page 26 of 46 wijv1v2v3v4v5v6v7v8k=1k=2k=3k=4v1012300v26021v330512v4023v510v61017v710v8350 min5 min271150 min5273156052731569-3 最短路问题 Shortest Path Problem*Page 27 of 46 wijv1v2v3v4v5v6v7v8k=1k=2路线距离v101231-11-11-10v26021-21-3-21-3-25v330511-41-31-32v4021-3-41-3-47v5101-2-51-3

18、-2-53v610171-3-61-3-61v7101-4-71-3-4-75v83501-3-6-869-3 最短路问题 Shortest Path Problem*Page 28 of 46 *任意两点间最短距离的矩阵算法邻接矩阵法*（选讲）【例】在下图中用矩阵计算法求各点之间的最短距离 【解】定义dij为图中两相邻点的距离，若i与j不相邻，令dij=。则527276243169-3 最短路问题 Shortest Path Problem*Page 29 of 46 步骤:1. 令C1 = C 表示一步步长各顶点之间的距离；9-3 最短路问题 Shortest Path Problem2。

19、Ck =CCk-1 表示k步步长内各顶点之间的距离；其中：3.当Ck+1 = Ck 时，Ck 就是任意两顶点之间的最短距离。*Page 30 of 46 应用（教材P270例4）年份12345购置费1111121213维修费5681118161617171822304159223141233123最优更新方案：1.第一年和第三年购置新设备；2.第一年和第四年购置新设备。总费用为53。9-3 最短路问题 Shortest Path Problem*Page 31 of 46 作业：教材P284 10.6 10.7 10.9 10.8* 10.10*1.理解点标号和弧（边）标号的含义2.掌握一个点

20、到其它任意点最短路的求法3.掌握无向图的最短路的求法9-3 最短路问题 Shortest Path Problem*Page 32 of 46 基本概念4844122679容量：在某时期内弧(i，j)上的最大通过能力。记为C (i，j)或Cij 在上图中，C12=4，C138，C234等，怎样安排运输方案，才能使在某一时期内从v1运到v6的物资最多，这样的问题就是最大流问题，网络中所有流起源于一个叫做发点的节点（源） 所有的流终止于一个叫做收点的节点其余所有的节点叫做中间点（转运点） 通过每一条弧的流只允许沿着弧的箭头方向流动目标是使得从发点到收点的总流量最大9-4 最大流问题Maximum

21、Flow Problem*Page 33 of 46 流量：弧(i，j)的实际通过量，记为f (i，j)或f ij可行流：如果f ij满足： 1.对于所有弧(i，j)有0f ijCij 2.对于发点vs有：3.对于收点vt有：则称流量集合f ij为网络的一个可行流，简记为 f , v称为可行流的流量或值，记为v(f).以下假设网络是一个简单连通图。4.对于中间点vm有：9-4 最大流问题Maximum Flow Problem*Page 34 of 46 链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。前向弧：与连的方向相同的弧称为前向弧。后向弧：与

22、连的方向相反的弧称为后向弧。增广链 设 f 是一个可行流，如果存在一条从vs到vt的链，满足：1.所有前向弧上fij0则该链称为增广链前向弧后向弧8446952346容量流量想一想，这是一条增广链吗？9-4 最大流问题Maximum Flow Problem*Page 35 of 46 【定理】设网络G的一个可行流f，如果存在一条从vs到vt的增广链，那么就可改进一个值更大的可行流f1，并且val f1val f【证】设val fv对改进的可行流f1 ：9-4 最大流问题Maximum Flow Problem*Page 36 of 46 最大流的标号算法步骤 1. 找出第一个可行流，例如所有

23、弧的流量fij =0 2. 用标号的方法找一条增广链 A1：发点标号（）， A2：选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查： 如果弧的方向向前并且有fij0，则vj标号（fji)当收点不能得到标号时，说明不存在增广链，计算结束。当收点已得到标号时，说明已找到增广链。【定理】可行流是最大流当且仅当不存在发点到收点的增广链9-4 最大流问题Maximum Flow Problem*Page 37 of 46 4. 调整流量 得到新的可行流，去掉所有标号，从发点重新标号寻找增广链，直到收点不能标号为止。3. 依据vi 的第一个标号反向跟踪得到一条增广链； 依据vi 的第二个标号

24、求最小值得到调整量9-4 最大流问题Maximum Flow Problem*Page 38 of 46 684412267942202222046217【例】求下图v1 到v6 的最大流及最大流量【解】1. 通过观察得到初始可行流2.标号3. 得到增广链9-4 最大流问题Maximum Flow Problem*Page 39 of 46 68441226794211322304223 得到增广链 4.求调整量 5.调整可行流 去掉所有标号，重新标号 6844122679422022220462179-4 最大流问题Maximum Flow Problem*Page 40 of 46 68441226796411322306 求调整量 调整可行流 去掉所有标号，重新标号5标号不能继续进行，说