管理运筹学讲义 第5章 图与网络方法8学时

1,第五章图与网络分析,Subtitle,学习要点,理解图论中结点、边、链、弧、路径的概念了解树的概念、最小树的求解方法及其应用掌握最短路的标号算法及网络选址中的应用理解网络流的概念及其网络瓶颈的识别方法正确理解最小费用流的调整改进思路和方法,2,图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论、信息论、工程技术、交通运输、经济管理、电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。对工程项目和管理的意义随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。,第五章图与网络分析,3,18世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？尽管试验者很多，但是都没有成功。,第五章图与网络分析,4,为了寻找答案，1736年瑞士数学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。他将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。,第五章图与网络分析,5,第五章图与网络分析,第一节图与网络的基本知识第二节树第三节最短路问题第四节网络最大流第五节最小费用流第六节应用举例,图论,6,第一节图与网络的基本知识,一、引言,例5-1:下图间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图,电话线分布图，煤气管道图等等。,郑州,太原,重庆,武汉,南京,徐州,连云港,上海,石家庄,塘沽,青岛,济南,天津,北京,7,例5-2：有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况也可以用图表示出来。,第一节图与网络的基本知识,一、引言,8,例5-3：某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。为了反映这个情况可以用点V1,V2,V8分别代表这八种药品，若药品Vi和药品Vj是不能存放在同一个库房的，则在Vi和Vj之间连一条线。,第一节图与网络的基本知识,一、引言,G=（V，E）,一般地，当用图论研究一个实际问题时，常以顶点（Vertex）表示要研究的对象，以它们之间的连线，表示某种关系，这种连线称为边（Edge），因此，图的表示方法为：,式中是点的集合，是边的集合。,9,v1,v4,v2,v3,e1,e2,e3,e4,e5,e6,v1,v4,v2,v3,e1,e2,e3,e4,e5,e6,v1,v2,v3,v4,e1,e2,e3,e4,e5,e6,图论的图与一般几何图形或代数函数图形是完全不同的。在几何学中，图中点的位置、线的长度和斜率等都十分重要，而图论中只关心图中有多少点以及哪些点之间有线相连，点和线的位置是任意的，强调点与点之间的关联关系，线的曲直、长短与实际无关，不讲究图的比例大小与形状。例5-4：表示苏州v1、杭州v2、上海v3、南京v4仓储网点之间的物流运输线路关系。,第一节图与网络的基本知识,一、引言,10,第一节图与网络的基本知识,二、图与网络的基本概念,1、顶点、边、无向图、有向图,例5-5：,（1）顶点、边:一个图是由点集和V中元素的无序对的一个集合构成的二元组，记为G=(V，E)，其中V中的元素叫做顶点，V表示图G的点集合；E中的元素叫做边，E表示图G的边集合。,11,第一节图与网络的基本知识,二、图与网络的基本概念,1、顶点、边、无向图、有向图,（2）无向图：如果一个图是由点和边所构成的，则称其为无向图，记作G=(V，E)，连接点的边记作vi,vj，或者vj,vi。,（3）有向图：如果一个图是由点和弧所构成的,即每条边都有一个方向，那么称它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。,V=v1,v2,v3,v4,v5,v6，A=(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6),12,第一节图与网络的基本知识,二、图与网络的基本概念,1、顶点、边、无向图、有向图,无向图,混合图：如何图G中部分边有方向则称为混合图,13,第一节图与网络的基本知识,二、图与网络的基本概念,2、端点，关联边，相邻,若有边e可表示为e=vi,vj,称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。,例如右图中，v2和v4是边e6的端点，反之边e6是点v2、v4的关联边。点v2、v4相邻；边e6与e5、e4、e5、e2、e7相邻。,e2可记作：,14,如果边e的两个端点相重(同)，称该边为环,如图-中边e1为环。如果两个点之间多于一条边的，称为多重边，如图中的e4和e5。对无环、无多重边的图称作简单图。含有有多重边的图称为多重图。,第一节图与网络的基本知识,二、图与网络的基本概念,3、环，多重边，简单图、多重图,（a）简单图,（d）多重图,（c）多重图,（b）简单图,15,第一节图与网络的基本知识,二、图与网络的基本概念,4、顶点的次,以点vi为端点的边的条数称为点vi的次也叫做度，记作d(vi)。图中d(v1)，d(v2)=4，d(v3)=5，d(v5)=1。次为奇数的点称作奇点,d(v)=奇数；次为偶数的点称作偶点,d(v)=偶数；次为0的点称作孤立点,d(v)=0；次为1的点称为悬挂点,d(v)=1；悬挂点的边称为悬挂边。空图：E=，无边图,图的次:一个图的次等于各点的次之和。,次的两个定理:定理1:任何图中，顶点次数的总和等于边数的2倍。定理2:任何图中，次为奇数的顶点必为偶数个。,有向图中，以vi为始点的边数称为点vi的出次，用表示；以vi为终点的边数称为点vi的入次，用表示；vi点的出次和入次之和就是该点的次。所有顶点的入次之和等于所有顶点的出次之和。,16,第一节图与网络的基本知识,二、图与网络的基本概念,5、链、路、回路（圈）,图中有些点和边的交替序列排成对任意vi,t-1和vit(2tk)均相邻，称从v0到vk的链。如果链中所有的顶点v0，v1，vk和所有的边不相同，这样的链称初等链。如果链中各边e1,e2,ek互不相同称为简单链。当v0与vk重合时称为此链为圈，如果圈中边不重复,点也不重复者称为初等圈。,17,路,v3,初等链-无重边、无重点,18,回路,v3,初等链-无重边、无重点，起点除外,19,v3,e4,无重边,20,第一节图与网络的基本知识,二、图与网络的基本概念,6、连通图,子图、支撑子图、赋权图、网络,（1）连通图:若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的。,21,第一节图与网络的基本知识,二、图与网络的基本概念,6、连通图,子图、支撑子图、赋权图、网络,(2)子图、支撑子图,图G1=V1、E1和图G2=V2，E2,如果,E1的边仅与V1中的顶点相关联,称G1是G2的一个子图。若有则称G1是G2的一个生成(支撑)子图,图（a）是图的一个子图，图（b）是图的支撑子图，注意支撑子图也是子图,子图不一定是支撑子图。,图(a),图(b),22,V6,(a),(b),(c),子图,支撑或生成子图,第一节图与网络的基本知识,二、图与网络的基本概念,6、连通图,子图、支撑子图、赋权图、网络,(2)子图、支撑子图,23,第一节图与网络的基本知识,二、图与网络的基本概念,6、连通图,子图、支撑子图、赋权图、网络,(3)赋权图,设图G（V，E），对G的每一条边(vi,vj)相应的有一数w(vi,vj)(或记为wij)，wij称为边(vi,vj)的权,赋有权的图G称为赋权图。这里的权数可以是时间、费用、距离等，视不同背景代表不同的含义。,赋权图,24,第一节图与网络的基本知识,二、图与网络的基本概念,6、连通图,子图、支撑子图、赋权图、网络,(4)网络,在一个有向赋权图G中规定了一个起点（发点）和一个终点（收点），其余是中间点，这样的图称为网络。,该图是起点为v1，终点为v7的一个网络图,25,第一节图与网络的基本知识,三、图的矩阵表示,一个图非常直观，但是不容易计算，特别不容易在计算机上进行计算，一个有效的解决办法是将图表示成矩阵形式，通常采用的矩阵是邻接矩阵、权矩阵、关联矩阵、回路矩阵、割集矩阵等。,对于网络（赋权图）G=（V，E），其中边有权，构造矩阵，其中：称矩阵A为网络G的权矩阵。,设图G=（V，E）中顶点的个数为n，构造一个矩阵，其中：即两个顶点之间有边相联时，记为1，否则为0。称矩阵A为网络G的邻接矩阵。,26,第一节图与网络的基本知识,三、图的矩阵表示,例子,27,第一节图与网络的基本知识,三、图的矩阵表示,求权矩阵,28,第一节图与网络的基本知识,三、图的矩阵表示,求邻接矩阵,无向图的邻接矩阵是对称矩阵。,29,第一节图与网络的基本知识,三、图的矩阵表示,也可对有向图求邻接矩阵。,30,G=(V,E),矩阵表示A邻接矩阵B权矩阵,边e=u,v,关联边,多重边平行边,简单图,多重图,01奇数偶数,点边关系,31,第一节图与网络的基本知识,三、欧拉图与中国邮路问题,1、欧拉图,哥尼斯堡七桥问题,哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？,32,第一节图与网络的基本知识,三、欧拉图与中国邮路问题,1、欧拉图,最后，数学家Euler在1736年巧妙地给出了这个问题的答案，并因此奠定了图论的基础，Euler把A、B、C、D四块陆地分别收缩成四个顶点，把桥表示成连接对应顶点之间的边，问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。,33,定理2连通无向图G为欧拉链的充要条件是它恰含两个奇次顶点。（七桥问题证明）,定义1.在连通图G中,若存在经过每条边一次且仅一次的一条道路，则称此条路为欧拉圈或欧拉链。若图G存在一条回路，经过每条边一次且仅一次，则称此回路为欧拉回路。具有欧拉回路的图成为欧拉图。,定理1连通无向图G为欧拉图的充要条件是它的全部顶点都是偶次顶点。（G中无奇次顶点）,第一节图与网络的基本知识,三、欧拉图与中国邮路问题,1、欧拉图,欧拉链,欧拉图,34,第一节图与网络的基本知识,三、欧拉图与中国邮路问题,2、中国邮路问题,定理3使图G成为总权最小的欧拉图的充要条件是：（1）在有奇次顶点的图G中，通过加重复边的方法使图不再包含奇次顶点，但原图的每条边最多只能加一条重复边。（2）在图G的每个回路上，重复边之总权不超过该回路非重复边之总权（或该回路总长的一半）。,35,例：试为图中所示的街道规划最优投递路线。解：可按以上所述步骤进行，最终结果示于图，总权等于52，重复边的长度等于10。,第一节图与网络的基本知识,三、欧拉图与中国邮路问题,2、中国邮路问题,36,第一节图与网络的基本知识,三、欧拉图与中国邮路问题,2、中国邮路问题,37,第二节树,一、树的概念及其性质二、支撑树(生成树)三、最小支撑树问题,38,第二节树,一、树的概念及其性质,在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。例已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。如果用六个点v1v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。由于任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。下图就是一个不含圈的连通图，代表了一个电话线网。,39,第二节树,一、树的概念及其性质,40,第二节树,一、树的概念及其性质,一个无圈的连通图称为树，通常用字母T表示。树中次为1(d(v)=1)的点称为树叶，次大于1(d(v)1)的点称为分支点。,1、定义,2、树的性质,图T=(V,E),|V|=n,|E|=m(1)如果树T的顶点数2，则它至少有两个悬挂点。(2)在一树中，任意两顶点间有一条且仅有一条通路。(3)T连通且有n-1条边。(4)T有n-1条边且无回路。(5)T没有回路，但在T中任两个不相邻的顶点间添上一条边，则恰形成一条回路或圈。(6)T连通，但去掉任一条边后就不连通，即T为连通且边数最少的图。,41,第二节树,二、支撑树,设图K=(V,E1)是图G=(V,E)的一支撑子图，如果图K=(V,E1)是一个树,那么称K是G的一个生成树（支撑树），或简称为图G的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。,42,第二节树,二、支撑树,图1不是树。想一想，为什么？图(a)是一棵树，图(b)是图1的一棵支撑树。,图1,图(a),图(b),43,第二节树,二、支撑树,例:下图是一个有四个顶点（n=4）的连通图，它共有nn-2=42=16个生成树。,44,第二节树,二、支撑树,45,第二节树,二、支撑树,46,定理：一个图G有生成树的充要条件是G是连通图。,第二节树,二、支撑树,证明:必要性显然；充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个支撑树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图G1。若G1不含圈，则G1是G的一个支撑树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一支撑子图G2。依此类推，可以得到图G的一个支撑子图GK，且不含圈，从而GK是一个支撑树。定理充分性的证明，提供了一个寻找连通图支撑树的方法叫做“破圈法”。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。,求支撑树常采用下述两种方法：1、丢边法（破圈法）2、加边法（避圈法）,47,第二节树,二、支撑树,1、破圈法,例：用破圈法求出下图的一个生成树,48,第二节树,二、支撑树,1、破圈法,49,第二节树,二、支撑树,2、避圈法,在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与e1，e2不构成圈的边e3。一般设已有e1，e2，ek，找一条与e1，e2，ek中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。,50,第二节树,二、支撑树,2、避圈法,51,第二节树,二、最小生成树问题,如果图T=(V,E1)是图G的一个生成树，那么称E1上所有边的权的和为生成树T的权，记作S(T)。如果图G的生成树T*的权S(T*)，在G的所有生成树T中的有最小权，即S(T*)=minS(T),那么称T*是G的最小生成树。,求最小树常用的有破圈法和避圈法两个方法：破圈法:从无向网络中任选一个圈，去掉圈中权数最大的边，便破一圈；如果最大权数的边不止一条，则任选其一去掉。如此反复操作，直至网络中不含圈为止。此时的支撑树就是最小树。避圈法：从无向网络中，开始选取权数最小的一条边，再选权数为次小的一条边；如此进行，总从剩余边中选取权数最小者，但前提是与已经选择的边不要构成圈；如果最小权数的边不止一条，则任选一条。,52,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,例:用破圈法求下图所示赋权图的最小树。,第二节树,53,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,第二节树,54,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,第二节树,55,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,第二节树,56,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,第二节树,57,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,第二节树,58,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,第二节树,59,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,第二节树,60,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,第二节树,61,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,第二节树,62,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,总权=1+4+9+3+17+23=57,第二节树,63,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,例:用避圈法求下图所示赋权图的最小树。,第二节树,64,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,第二节树,65,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,第二节树,66,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,第二节树,67,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,第二节树,68,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,第二节树,69,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,总权=1+4+9+3+17+23=57,第二节树,70,例:用避圈法求下图所示赋权图的最小树。图中每边括号内的数字为该边的权。,e1(10),e7(6),e10,(6),e9(10),e17,(9),(7),e14,e3(5),e5(7),e12(9),e11(7),e2(11),e4(4),e15(4),e13(8),e8(5),e6(5),e9(10),第二节树,二、最小生成树问题,71,e1(10),e7(6),e10,(6),e17(10),e16,(6),(7),e14,e3(5),e5(7),e12(9),e11(7),e2(11),e4(4),e15(4),e13(8),e8(5),e6(5),e9(10),第二节树,二、最小生成树问题,72,V1,V2,V3,V4,V5,V6,V7,V8,e4(4),e15(4),e3(5),e6(5),e8(5),e7(6),e10(6),e16(6),e5(7),e11(7),e14(7),e13(8)e12(9),e17(9),e1(10),e9(10),e2(11).m=n-1=8-1=7w(T)=37,第二节树,二、最小生成树问题,73,例6:某工厂内连结六个车间的道路网如图所示，已每条道路的长，要求沿道路架设联接六个车间的电话线网，使电话线的总长最小。解：用避圈法求解。,V1,V2,V3,V5,V6,V4,E15,E26,E31,e45,E57,E63,E74,E84,e9,2,第二节树,二、最小生成树问题,74,第三节最短路径问题,最短路径问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,75,里特城（Littletown）是一个乡村的小镇。它的消防队要为包括许多农场社区在内大片的地区提供服务。在这个地区里有很多道路，从消防站到任何一个社区都有很多条路线。因为时间是一个到达火灾发生点的主要因素，所以消防队队长希望事先能够确定从消防站到每一个农场社区的最短路。,例：里特城的消防队问题,第三节最短路径问题,76,第三节最短路径问题,77,第三节最短路径问题,78,第三节最短路径问题,最短路：OABEFT19英里,79,第三节最短路径问题,一般意义下的最短路问题：设G=(V,E)为连通图，图中边(vi，vj)有权lij（lij=+表示vi，vj之间没有边），vs，vt为图中任意两点，求一条路，使它为从vs到vt的所有路中总权最短。即：最小。,求最短路有三种算法:第一种是求从某一点至其它各点之间最短距离的狄克斯屈拉(Dijkstra)算法；第二种是求网图上任意两点之间最短的矩阵算法;第三种是逐次逼近法。,80,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,1、算法的基本思想,81,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,2、算法步骤,(1)给Vs以P标号，P（Vs)=0，这表示从Vs到Vs的最短距离为0，其余各点均给T标号，T（Vi）=+(i=2,3,n)。(2)若Vi点为刚得到P标号的点，考虑这样的点Vj:(Vi,Vj）属于E，且Vj为T标号。对Vj的T标号进行如下的更改：T(Vj)=minT(Vj),P(vi)+lij(3)比较所有具有T标号的点，把最小者改为P标号，即T(Vk)=minT(Vi),当存在两个以上最小者时，可同时改为P标号。若终点为P标号则计算停止，否则转步骤（2）。,82,例:用Dijkstra算法求下图从v1到v6的最短路。,解（1）首先给v1以P标号，给其余所有点T标号。,（2）,（3）,（4）,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,83,（5）,（6）,（7）,（8）,（9）,（10）,反向追踪得v1到v6的最短路为：,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,84,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,例:求从1到8的最短路径,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,85,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,w1=0,minc12,c14,c16=min0+2,0+1,0+3=min2,1,3=1X=1,4,p4=1,p4=1,p1=0,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,86,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,minc12,c16,c42,c47=min0+2,0+3,1+10,1+2=min2,3,11,3=2X=1,2,4,p2=2,p1=0,p4=1,p2=2,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,87,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,minc16,c23,c25,c47=min0+3,2+6,2+5,1+2=min3,8,7,3=3X=1,2,4,6,p6=3,p2=2,p4=1,p1=0,p6=3,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,88,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,minc23,c25,c47,c67=min2+6,2+5,1+2,3+4=min8,7,3,7=3X=1,2,4,6,7,p7=3,p2=2,p4=1,p1=0,p6=3,p7=3,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,89,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,minc23,c25,c75,c78=min2+6,2+5,3+3,3+8=min8,7,6,11=6X=1,2,4,5,6,7,p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,90,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,minc23,c53,c58,c78=min2+6,6+9,6+4,3+8=min8,15,10,11=8X=1,2,3,4,5,6,7,p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,91,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,minc38,c58,c78=min8+6,6+4,3+7=min14,10,11=10X=1,2,3,4,5,6,7,8,p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,92,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到8的最短路径为1，4，7，5，8，长度为10。,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,第三节最短路径问题,一、狄克斯屈拉(Dijkstra)算法,93,例：求下图v1到v7的最短路长及最短路线,0,8,6,2,2,5,4,4,11,14,7,5,10,7,12,11,v7已标号，计算结束。从v1到v7的最短路长是11,最短路线是：v1v4v6v7,第三节最短路径问题,一、狄克斯屈拉算法,94,例：求下图v1到各点的最短路及最短距离,0,4,5,2,2,3,10,3,9,6,12,6,4,11,6,6,18,8,12,24,8,24,18,所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。,第三节最短路径问题,一、狄克斯屈拉算法,95,Dijkstra最短路算法的特点和适应范围：,每次迭代只有一个节点获得永久标号，若有两个或两个以上节点的临时标号同时最小，可同时永久标号；总是从一个新的永久标号开始新一轮的临时标号；永久标号Pj表示vs到vj的最短路，第k次迭代得到的永久标号，最多有n1次迭代；可以应用于简单有向图和混合图，在临时标号时，所谓相邻必须是箭头指向的节点；若第n1次迭代后仍有节点的标号为，则表明vs到该节点无有向路径；vs到所有点的最短路也是一棵生成树，但不是最小生成树这个算法只设用于全部权为非负情况,如果某边上权为负的,算法失效;当vi与vj两点之间至少有两条边相关联时，留下一条最短边，去掉其它关联边。,第三节最短路径问题,一、狄克斯屈拉算法,96,例：求下图所示网络之顶点1至6的最短路和最短路长。,第三节最短路径问题,一、狄克斯屈拉算法,97,算法的基本思路与步骤：首先设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：开始时，令即用v1到vj的直接距离做初始解。从第二步起，使用递推公式：求，当进行到第t步，若出现则停止计算，即为v1到各点的最短路长。,第三节最短路径问题,二、逐次逼近法（选讲）,98,第三节最短路径问题,二、逐次逼近法（选讲）,例：求图中v1到各点的最短路,99,第三节最短路径问题,三、所有点对间的最短路Floyd算法,为了方便,令图或网络的权矩阵为:,基本步骤：(1)输入权矩阵（）；(2)对n个顶点的图G,该方法迭代n步结束，第k次迭代的矩阵Dk的元素dij(k)按下式选取dij(k)=mindij(k-1),dik(k-1）+dkj(k-1）,其中，i,j=1,2,3,n。但当i=k或j=k时dij(k)=dij(k-1)。(3)（）中的元素就是到的最短路长。,100,第三节最短路径问题,三、所有点对间的最短路Floyd算法,例:求下图所示网络图各点对间的最短路和最短路长。,101,第三节最短路径问题,三、所有点对间的最短路Floyd算法,102,第三节最短路径问题,三、所有点对间的最短路Floyd算法,103,第三节最短路径问题,三、所有点对间的最短路Floyd算法,104,2,3,1,4,743,29,10,例求下图所示网络图各点对间的最短路和最短路长。,第三节最短路径问题,三、所有点对间的最短路Floyd算法,105,例:求5年内，哪些年初购置新设备，使5年内总费用最小。,第三节最短路径问题,四、应用举例,解：（1）分析：可行的购置方案（更新计划）是很多的，如：1）每年购置一台新的，则对应的费用为:11+11+12+12+13+5+5+5+5+5=84;2)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59;(其中维修费用表示的是设备各年使用的费用)显然不同的方案对应不同的费用。,106,（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。求解步骤：1）画赋权有向图：设Vi表示第i年初，(Vi,Vj)表示第i年初购买新设备用到第j年初（j-1年底），而Wij表示相应费用，则5年的一个更新计划相当于从V1到V6的一条路。2）求解（标号法）,第三节最短路径问题,四、应用举例,107,16,16,17,17,18,22,30,41,59,22,30,41,23,31,23,最优更新方案：1.第一年和第三年购置新设备；2.第一年和第四年购置新设备。总费用为53。,第三节最短路径问题,四、应用举例,108,在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。,第四节最大流问题,109,第四节最大流问题,一、相关概念与定理,设一个赋权有向图G=（V,E），在G中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于G中的每一个弧（vi,vj）E,都有一个非负数cij,称为弧的容量。这样的网络G称为一个容量网络，简称网络，记做G=（V，E，C）。网络G上的流，是指定义在弧集合E上的一个函数其中f(vi,vj)=fij,叫做弧(vi，vj)上的流量,即弧(i，j)的实际通过量。,1、容量网络、流量、容量,110,容量：在某时期内弧(i，j)上的最大通过能力,记为C(i，j)或Cij.在上图中，C12=4，C138，C234等，怎样安排运输方案，才能使在某一时期内从v1运到v6的物资最多，这样的问题就是最大流问题，,网络中所有流起源于一个叫做发点的节点（源）；,所有的流终止于一个叫做收点的节点；,其余所有的节点叫做中间点（转运点）；,通过每一条弧的流只允许沿着弧的箭头方向流动；,目标是使得从发点到收点的总流量最大；,第四节最大流问题,一、相关概念与定理,1、容量网络、流量、容量,111,第四节最大流问题,一、相关概念与定理,1、容量网络、流量、容量,网络系统上流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的流入量与流出量的代数和等于零；(3)每一个弧上的流量不能超过它的最大通过能力（即容量）。,112,第四节最大流问题,一、相关概念与定理,2、可行流,称满足下列条件的流为可行流：(1)容量条件：对于每一个弧（vi,vj）E,有0fijcij。(2)平衡条件：对于发点vs，有对于收点vt，有对于中间点，有,则称流量集合fij为网络的一个可行流，简记为f,W称为可行流的流量或值(发点的净输出量或收点的净输入量).,113,第四节最大流问题,一、相关概念与定理,3、饱和和非饱和弧,可行流中fijcij的弧叫做饱和弧，fijcij的弧叫做非饱和弧。fij0的弧为非零流弧，fij0的弧叫做零流弧。,图中为零流弧，其余为非饱和弧。,114,截集:将图G（V，E）的点集分割成两部分,称为一个截集，截集中所有弧的容量之和称为截集的截量。,下图所示的截集为,请看演示,4、截集与截量,第四节最大流问题,一、相关概念与定理,115,4、截集与截量,第四节最大流问题,一、相关概念与定理,又如下图所示的截集为,上图所示的截集为,所有截量中此截量最小且等于最大流量，此截集称为最小截集。,【定理】最大流量等于最小截集的截量(最大流-最小割定理)。,116,链u：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。前向弧u+：与链的方向相同的弧称为前向弧。后向弧u-：与链的方向相反的弧称为后向弧。增广链:设f是一个可行流，如果存在一条从vs到vt的链，满足：(1)所有前向弧上0fij0；（后向弧都是非0流弧）则该链称为增广链,容量,流量,5、链、前向弧、后向弧、增广链,第四节最大流问题,一、相关概念与定理,117,4、链、前向弧、后向弧、增广链,第四节最大流问题,一、相关概念与定理,定理：设网络G的一个可行流f，如果存在一条从vs到vt的增广链，那么就可改进一个值更大的可行流f1，并且val(f1)val(f）。,【证】设valfv,对改进的可行流f1：,定理:可行流是最大流当且仅当不存在发点到收点的增广链.,118,第四节最大流问题,二、最大流的标号算法,先找一个可行流。对于这个可行流，经过标号过程，得到从发点vs到收点vt的增广链；经过调整过程，沿增广链增加可行流的流量，得到新的可行流。重复这一过程，直到可行流无增广链，得到最大流。,1、标号法思想,(1)找出第一个可行流，例如所有弧的流量fij=0(2)用标号的方法找一条增广链a、发点标号（），b、选一已标号的点vi,并且另一端未标号的弧,沿着某条链向收点检查：,2、基本步骤,119,第四节最大流问题,二、最大流的标号算法,2、基本步骤,如果弧的方向向前并且有fij0，则vj标号（fji)当收点不能得到标号(如fij=Cij或fji=0,停止该点标号)时，说明不存在增广链，计算结束。当收点已得到标号时，说明已找到增广链。,(4)调整流量,得到新的可行流，去掉所有标号，从发点重新标号寻找增广链，直到收点不能标号为止。,(3)依据vi的第一个标号反向跟踪得到一条增广链；依据vi的第二个标号求最小值得到调整量。,120,4,2,2,0,2,2,2,2,0,4,6,2,1,7,例：求下图v1到v6的最大流及最大流量,解：1.初始可行流2.标号3.得到增广链,第四节最大流问题,二、最大流的标号算法,121,4,2,1,1,3,2,2,3,0,4,2,2,3,4.求调整量,5.调整可行流去掉所有标号，重新标号，得到增广链,第四节最大流问题,二、最大流的标号算法,122,6,8,4,4,1,2,2,6,7,9,6,4,1,1,3,2,2,3,0,6,求调整量,调整可行流,去掉所有标号，重新标号标号不能继续进行，说明不存在从发点到收点的增广链，得到最大流。,5,最大流量v=6+3=9,1,第四节最大流问题,二、最大流的标号算法,增广链不止一条,则采用标号法计算,不同的增广链条下计算的最大流的结果一致吗?,123,第五节最小费用最大流问题,在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。,一、概念,最小费用流的一般提法：已知容量网络G=(V,E,C),每条边(vi,vj)除了已给出容量cij外，还给出了单位流量的费用dij(0),记G=(V,E,C,d)。求一个可行流f=fij,使得流量W(f)=v,且总费用最小。d(f)=dijfij当要求f是最大流时，此问题即为最小费用最大流问题。,124,第五节最小费用最大流问题,定义:已知网络