第八讲图与网络优化.ppt

1,2019年6月17日,运筹学（operations research, OR）,第八讲 图与网络优化,商学院电子商务系,2,2019年6月17日,第八讲 图与网络优化,一. 图与树 二. 最短路问题 三. 最大流问题,3,2019年6月17日,一、图与树,第八讲 图与网络优化,人们为反映一些对象之间关系时，常会用示意图。,图的相关概念,铁路交通图,比赛情况图,药品存放图,4,2019年6月17日,一、图与树,第八讲 图与网络优化,图是由一些点及一些点之间的连线(不带箭头或带箭头)组成的图形。,图的相关概念,两点之间不带箭头的连线称为边，带箭头的连线称为弧。,如果一个图G由点及边所构成，则称之为无向图(也简称为图)，记为G=（V，E），式中V，E分别是G的点集合和边集合。一条连结点Vi，Vj的边记为Vi，Vj(或 Vj，Vi) 。,如果一个图D由点及弧所构成，则称为有向图，记为D=(V，A)，式中V，A分别表示D的点集合和弧集合。一条方向是从vi指向vj的弧，记为(vi,vj).,5,2019年6月17日,一、图与树,第八讲 图与网络优化,点的集合：,无向图例子,边的集合：,6,2019年6月17日,一、图与树,第八讲 图与网络优化,有向图例子,7,2019年6月17日,一、图与树,第八讲 图与网络优化,图的相关概念,图G或D中的点数记为p(G)或p(D)，边(弧)数记为q(G)(q(D)，分别简记为p，q。,若边e =u，vE，则称u，v是e的端点，也称u，v是相邻的。称e是点u(及点v)的关连边。,若图G中，某个边e的两个端点相同，则称e是环(如前图中的e7)。,若两个点之间有多于一条的边，称这些边为多重边(如前图中的e1,e2)。,8,2019年6月17日,一、图与树,第八讲 图与网络优化,图的相关概念,一个无环，无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。,以点v为端点的边的个数称为v的次，记为dG(v)或d(v)。次为奇数的点，称之为奇点；次为偶数的点，称之为偶点。,称次为1的点为悬挂点，悬挂点的关连边称为悬挂边，次为零的点称为孤立点。,9,2019年6月17日,一、图与树,第八讲 图与网络优化,图的相关概念,证明：显然，在计算各点的次时，每条边被它的端点各用了一次。,定理1 图G=(V，E)中，所有点的次之和是边数的两倍，即：,10,2019年6月17日,一、图与树,第八讲 图与网络优化,图的相关概念,定理2 任一个图中，奇点的个数为偶数。,证明:设V1和V2分别是G中奇点和偶点的集合，由定理1，有：,因 是偶数， 也是偶数，故 必定也是偶数，从而V1的点数是偶数。,11,2019年6月17日,一、图与树,第八讲 图与网络优化,图的相关概念,12,2019年6月17日,一、图与树,第八讲 图与网络优化,图的相关概念,链 中，若 ，则称之为一个圈，记为 。,若链 中，点 都是不同的，则称之为初等链；若圈 中， 都是不同的，则称之为初等圈。,若链(圈)中含的边均不相同，则称之为简单圈。以后说到链(圈)，除非特别交代，均指初等链(圈)。,13,2019年6月17日,一、图与树,第八讲 图与网络优化,例子,是一条简单链，但不是初等链， 是一条初等链。,是一个初等圈， 是简单圈，但不是初等圈。,14,2019年6月17日,一、图与树,第八讲 图与网络优化,连通图,图G中，若任何两点之间至少有一条链，则称G是连通图，否则称为不连通图。,若G是不连通图，它的每个连通的部分称为G的一个连通分图(也简称分图)。,思考：右图是连通图吗？,15,2019年6月17日,一、图与树,第八讲 图与网络优化,支撑子图,给了一个图G=(V，E)，如果G=(V，E)，使V=V及EE ，则称G是G的一个支撑子图。,设vV(G)，用Gv表示从图G中去掉点v及v的关联边后得到的一个图。,16,2019年6月17日,一、图与树,第八讲 图与网络优化,和有向图有关的概念和术语,设给定一个有向图，D=(V，A)，从D中去掉所有弧上的箭头，就得到一个无向图，称之为D的基础图，记之为G(D)。,给定D中的一条弧a=(u，v)，称u为a的始点，v为a的终点，称弧a是从u指向v的。,设 是D中的一个点弧交错序列，如果这个序列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。类似定义圈和初等链(圈)。,如果 是D中的一条链，并且对t=1，2，k-1，均有 ，称之为从 的一条路。若路的第一个点和最后一点相同，则称之为回路。类似定义初等路(回路)。,17,2019年6月17日,一、图与树,第八讲 图与网络优化,例子,是一个回路；,是从v1到v6的路；,是一条链，但不是路。,注：对无向图，链与路(圈与回路)两个概念是一致的。,18,2019年6月17日,一、图与树,第八讲 图与网络优化,树,树：一类极其简单然而却很有用的图。,树的定义： 一个无圈的连通图称为树。,19,2019年6月17日,一、图与树,第八讲 图与网络优化,树的性质,定理3 设图G=(V，E)是一个树，p(G)2，则G中至少有两个悬挂点。,证明:令 是G中含边数最多的一条初等链，因p(G)2，并且G是连通的，故链P中至少有一条边，从而v1与vk是不同的。 现在来证明：v1是悬挂点，即d(v1)=1。 用反证法，如果d(v1)2，则存在边 且m2。若点vm不在P上，那么 是G中的一条初等链，它含的边数比P多一条，这与P是含边数最多的初等链矛盾。若点vm在P上，那么 是G中的一个圈，这与树的定义矛盾。于是必有d(v1)=1，即v1是悬挂点。同理可证vk也是悬挂点，因而G至少有两个悬挂点。,20,2019年6月17日,一、图与树,第八讲 图与网络优化,树的性质,定理4 图G=(V，E)是一个树的充分必要条件是G不含圈，且恰有p1条边。,证明：必要性。设G是一个树，根据定义，G不含圈，故只要证明G恰有p 1条边。对点数p施行数学归纳法。p=1，2时，结论显然成立。假设对点数pn时，结论成立。设树G含n+1个点。由定理3，G含悬挂点，设v1是G的一个悬挂点，考虑图G v1，易见p(G v1)=n，q(G v1)=q(G) 1。因G v1是n个点的树，由归纳假设，q(G v1)=n 1，于是q(G)=q(G v1)+1=(n1)+1=n=p(G) 1。,21,2019年6月17日,一、图与树,第八讲 图与网络优化,树的性质,定理4 图G=(V，E)是一个树的充分必要条件是G不含圈，且恰有p1条边。,证明：充分性 。只要证明G是连通的。用反证法，设G是不连通的，G含s个连通分图G1，G2，Gs(s2)。因每个Gi(i=1，2，s)是连通的，并且不含圈，故每个Gi是树。设Gi有pi个点，则由必要性，Gi有pi 1条边，于是 这与q(G)=p(G) 1的假设矛盾。,22,2019年6月17日,一、图与树,第八讲 图与网络优化,树的性质,定理5 图G是树的充分必要条件是任意两个顶点之间恰有一条链。,证明 必要性。 因G是连通的，故任两个点之间至少有一条链。但如果某两个点之间有两条链的话，那么图G中含有圈，这与树的定义矛盾，从而任两个点之间恰有一条链。 充分性：设图G中任两个点之间恰有一条链，那么易见G是连通的。如果G中含有圈，那么这个圈上的两个顶点之间有两条链，这与假设矛盾，故G不含圈，于是G是树。,23,2019年6月17日,一、图与树,第八讲 图与网络优化,树的性质,由定理5，很容易推出如下结论：,(1) 从一个树中去掉任意一条边，则余下的图是不连通的。由此可知，在点集合相同的所有图中，树是含边数最少的连通图。,(2) 在树中不相邻的两个点间添上一条边，则恰好得到一个圈。进一步地说，如果再从这个圈上任意去掉一条边，可以得到一个树。,24,2019年6月17日,一、图与树,第八讲 图与网络优化,树的性质,定义 设图T=(V，E)是图G=(V，E)的支撑子图，如果图T=(V，E)是一个树，则称T是G的一个支撑树。,若T=(V，E)是G=(V，E)的一个支撑树，则显然，树T中边的个数是p(G) 1，G中不属于树T的边数是q(G) p(G)+1。,25,2019年6月17日,一、图与树,第八讲 图与网络优化,树的性质,定理6 图G有支撑树的充分必要条件是图G是连通的。,证明：必要性是显然的。 充分性。设图G是连通图，如果G不含圈，那么G本身是一个树，从而G是它自身的一个支撑树。现设G含圈，任取一个圈，从圈中任意地去掉一条边，得到图G的一个支撑子图G1。如果G1不含圈，那么G1是G的一个支撑树(因为易见G1是连通的)；如果G1仍含圈，那么从G1中任取一个圈，从圈中再任意去掉一条边，得到图G的一个支撑子图G2，如此重复，最终可以得到G的一个支撑子图Gk，它不含圈，于是Gk是G的一个支撑树。,思考：该定理的充分性证明有什么作用？,26,2019年6月17日,一、图与树,第八讲 图与网络优化,最小支撑树问题,这里所说的“权”，是指与边有关的数量指标。根据实际问题的需要，可以赋予它不同的含义，如表示距离、时间、费用等。,赋权图被广泛应用于工程技术及科学生产管理等领域的最优化问题。最小支撑树问题就是赋权图上的最优化问题之一。,定义 给图G=(V，E)，对G中的每一条边 ，相应地有一个数wij，则称这样的图G为赋权图，wij称为边 上的权。,27,2019年6月17日,一、图与树,第八讲 图与网络优化,最小支撑树问题,设有一个连通图G=(V，E)，每一边e= ，有一个非负权：w(e)=wij (wij0),定义 如果T=(V，E)是G的一个支撑树，称E中所有边的权之和为支撑树T的权，记为w(T)。即：,如果支撑树T* 的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树(简称最小树)。即,28,2019年6月17日,一、图与树,第八讲 图与网络优化,最小支撑树问题,1. 避圈法：从图中任取一点 令 ，图中其余的点都在 中；从 与 的连线中找出最小边，这条边一定在最小支撑树内，不停重复，一直到图中所有点均包含在V中为止。,2. 破圈法：任取一个圈，从圈中去掉一条权最大的边(如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小树。,下面介绍两个求解最小支撑树的方法。,29,2019年6月17日,例： 如图S,A,B,C,D,E,T代表村镇,村镇之间的连线上赋予了权值(可代表距离,费用,流量等)现沿图中连线架设电线,使各村镇全部通电,问如何架设使电线总长最短.(该图称为赋权图或无向网络).,第八讲 图与网络优化,30,2019年6月17日,最小支撑树总长=2+2+1+3+1+5=14,第八讲 图与网络优化,31,2019年6月17日,电线总长=2+2+1+3+1+5=14,32,2019年6月17日,二、最短路问题,第八讲 图与网络优化,引例,已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从v1出发，通过这个交通网到v8去，求总费用最小的旅行路线。,33,2019年6月17日,二、最短路问题,第八讲 图与网络优化,引例,结论1：由上例可见，从v1到v8的旅行路线有很多；,结论2：不同的路线所需总费用是不同的；,结论3：用图的语言来描述，从v1到v8的一条旅行路线就是图中从v1到v8的一条路；一条旅行路线的总费用就是相应的从v1到v8的路中所有弧旁数字之和。,34,2019年6月17日,二、最短路问题,第八讲 图与网络优化,一般意义的最短路问题,给定一个赋权有向图，即给了一个有向图D=(V，A)，对每一个弧a=(vi，vj)，相应地赋予了权数；又给定D中的两个顶点vs，vt。设P是D中从vs到vt的一条路，定义路P的权是P中所有弧的权之和，记为w(P)。最短路问题就是要在所有从vs到vt的路中，求一条权最小的路，即求一条从vs到vt的路P0，使：,上式中对D中所有从vs到vt的路P取最小，称P0是从vs到vt的最短路。路P0的权称为从vs到vt的距离，记为d(vs，vt)。显然，d(vs，vt)与d(vt，vs)不一定相等。,35,2019年6月17日,二、最短路问题,第八讲 图与网络优化,最短路算法,Dijkstra算法的基本思想：从vs出发，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)，或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p1步，就可以求出从vs到各点的最短路。,36,2019年6月17日,二、最短路问题,第八讲 图与网络优化,Dijkstra算法,P，T分别表示某个点的P标号、T标号，,为了在求出从vs到各点的距离的同时，也求出从vs到各点的最短路，给每个点v以一个值。算法终止时，如果(v)=vm，表示在从vs到v的最短路上，v的前一个点是vm；(v)=0表示v=vs。,37,2019年6月17日,二、最短路问题,第八讲 图与网络优化,例题,用Dijkstra方法求前例中从v1 到各个顶点的最短路？,标P(v1)=0。其余点标T(vi)= +，i2，3，9；,T(v2)min + ，066，(v2)=v1；,T(v3)min + ，033，(v3)=v1；,T(v4)min + ，011，(v4)=v1；,将具有最小T标号的v4点的标号改为P标号：P(v4)1；,T(v6)min + ，11011，(v6)=v4；,将具有最小T标号的v3点的标号改为P标号：P(v3)3；,T(v2)min 6 ，325，(v2)=v3；,将具有最小T标号的v2点的标号改为P标号：P(v2)5；,38,2019年6月17日,例题,用Dijkstra方法求前例中从v1 到各个顶点的最短路？,T(v5)min + ，516，(v5)=v2；,将具有最小T标号的v5点的标号改为P标号：P(v5)6；,T(v6)min 11 ，6410，(v6)=v5；,T(v7)min + ，639，(v7)=v5；,T(v8)min + ，6612，(v8)=v5；,将具有最小T标号的v7点的标号改为P标号：P(v7)9；,T(v8)min 12 ，9412，(v8)=v5；,将具有最小T标号v6点的标号改为P标号：P(v6)11；,将具有最小T标号v8点的标号改为P标号：P(v8)12；,39,2019年6月17日,二、最短路问题,第八讲 图与网络优化,Dijkstra算法缺陷,Dijkstra算法只适用于所有wij0的情形，当赋权有向图中存在负权时，则算法失效。例如在下图所示的赋权有向图中，如果用Dijkstra方法，可得出从v1到v2的最短路的权是1，但这显然是不对的，因为从v1到v2的最短路是(v1，v3，v2)，权是-1。,40,2019年6月17日,二、最短路问题,第八讲 图与网络优化,练习题,41,2019年6月17日,二、最短路问题,第八讲 图与网络优化,Dijkstra算法另一种写法,T（）,0 ,P（）+wij,T（）,P（）+wij,T（）,P（）+wij,T（）,P（）+wij,T（）,0+6,0+ 3,0+ 1,0+ ,0+ ,0+ ,0+ ,0+ ,1,3,6,1+10,1+,1+,1+,1+,1+,1+,6,3,11,3+2,3+,3+,3+,3+,3+,5,11,5+1,5+,5+,5+,5+,6,11,42,2019年6月17日,二、最短路问题,第八讲 图与网络优化,Dijkstra算法另一种写法,T（）,11 ,P（）+wij,T（）,P（）+wij,T（）,P（）+wij,T（）,P（）+wij,T（）,6,6+4,6+3,6+6,6+,10,9,12,9+4,9+ ,9+ ,10,10+ ,10+ ,12,43,2019年6月17日,二、最短路问题,第八讲 图与网络优化,迭代算法,迭代算法是当赋权有向图中存在具负权弧时，求最短路的方法。,为方便起见，不妨设从任一点vi到任一个点vj都有一条弧(如果在D中， ，则添加弧(vi，vj)。令wij=+)。,显然，从vs到vj的最短路总是从vs出发，沿着一条路到某个点vi，再沿(vi，vj)到vj的(这里vi可以是vs本身)，明显可知，从vs到vi的这条路必定是从vs到vi的最短路，所以d(vs，vj)必满足如下方程：,44,2019年6月17日,二、最短路问题,第八讲 图与网络优化,迭代算法,为了求得这个方程的解d(vs，v1)，d(vs，v2)，d(vs，vp)，可用如下递推公式： 开始时，令： ,(j=1，2，p) 对t=2,3, ，j=1，2，p 若进行到某一步，例如第k步时，对所有j=1，2，p，有： 则 ，即为vs到各点的最短路的权。,45,2019年6月17日,二、最短路问题,第八讲 图与网络优化,迭代算法,例题,求右图所示赋权有向图中从v1到各点的最短路。,46,2019年6月17日,二、最短路问题,第八讲 图与网络优化,迭代算法,例题,0,-1,-2,3,0,-5,-2,-7,1,-1,5,0,-5,-2,-7,-3,-1,-5,0,-5,-2,-7,-3,-1,-5,6,6,47,2019年6月17日,第八讲 图与网络优化,三、最大流问题,流(Flow)就是将目标由一个地点运送到另一个地点.如:公路中的交通流,控制系统中的信息流,供水系统中的水流,金融系统中的现金流,邮政系统中的信件流,等等.它们的共同问题是,希望经过输送系统,将目标从一个地点运送到另一个地点的运输量最大,或者将一定数量的目标在该系统中从一个地点输送到另一个地点的费用最小.这就是网络中的最大流问题和最小费用最大流问题.,48,2019年6月17日,容量网络是指对网络上的每一条弧,都给出 一个最大的通过能力,称为该弧的容量,记为 或简记为 ,这样的网络称为容量网络. 在容量网络中规定一个发点(源点)s和一个收点(汇点)t,其余的点称为中间点. 网络的最大流是指:网络中从发点到收点之间允许通过的最大流量.,第八讲 图与网络优化,1、最大流问题相关概念,49,2019年6月17日,第八讲 图与网络优化,我们只研究一个发点和一个收点的情况.对于多个发点和多个收点的情况可将若干个发点合并为一个新的发点对于收点也如此处理.,50,2019年6月17日,流（flow）是指加在网络上的一组负载.对加在弧 上的流,记为 或简记为 , 当 时称为零流.,可行流（feasible flow）：在容量网络上满足下列三个条件的一组流称为可行流： 容量限制条件:对所有的弧有 (2) 中间点平衡条件: (3) 若以v(f)表示网络中从s到t的净输出量,则有,流和可行流:,51,2019年6月17日,第八讲 图与网络优化,任何容量网络上一定存在可行流,因为零流就是可行流.,所谓求网络最大流,就是指在满足容量限制条件和中间点平衡条件下,使v(f)值达到最大.,52,2019年6月17日,增广链:如果在网络的发点和收点之间能找出一条链,在这条链上所有的指向为st的弧(称为前向弧,记为 ),存在f0,这样的链称为增广链.,为加在弧上的负载, 是弧上的容量.,第八讲 图与网络优化,53,2019年6月17日,当有增广链时,找出,再令,显然 仍是一个可行流,与原来的可行流 比较发现,网络中从st的流量增大了一个 值( 0).,因此,只有当网络中找不到增广链时,st的流才不可能进一步增大.,第八讲 图与网络优化,54,2019年6月17日,在下图中,弧旁的数据格式为：,截集：将容量网络中的发点和收点分割开,使s到t的流中断的一个弧集合.,截集和截量,55,2019年6月17日,截集的截量:截集的弧集合中各弧的容量之和,用 表示,显然,56,2019年6月17日,最大流量最小截集定理：任一网络D中， 从 到 的最大流的流量等于分 离 和 的最小截集的容量。,第八讲 图与网络优化,57,2019年6月17日,求网络最大流的标号法,该算法是由Ford和Fulkerson于1956年提出,故称Ford-Fulkerson标号法。算法的实质是：判断网络中是否存在增广链,并将其找出来.,算法步骤: 1、首先给发点s标号,记为 ,括号中第一个数字是使这个点得到标号的前一个点的代号,第二个数字表示从上一个标号点到这一标号点的流量的最大允许调整值;,第八讲 图与网络优化,58,2019年6月17日,2、找出与已标号点相邻的所有未标号点., 考虑从标号点i出发的弧(i,j),如有 则不给j点标号;若有 则对j点标号,记为 其中i表示j点的标号是从i点延伸过来的, 考虑所有指向i的弧(j,i),如有 对j点不标号,若 有 则对j点标号,记为,求网络最大流的标号法Ford-Fulkerson标号法,第八讲 图与网络优化,2、找出与已标号点相邻的所有未标号点.,求网络最大流的标号法Ford-Fulkerson标号法,59,2019年6月17日, 标号过程中断,t点得不到标号,说明网络中不存在增广链,网络中给定的流就是最大流.计算结束; t点得到标号,这时反向追踪,在网络中找到一条从s到t 的由标号点和相应的弧连结而成的增广链.,3、重复步骤2,可能出现两种结局:,求网络最大流的标号法Ford-Fulkerson标号法,第八讲 图与网络优化,60,2019年6月17日,5、抹去网络图中的所有标号,重复第1到第4步,一直到在网络中找不到任何增广链,即出现第3步的结局(1)为止,这时网络中的流量为网络的最大流.,4、修改流量:设在网络中原有的流量为f，并且以为调整量，则：,第八讲 图与网络优化,求网络最大流的标号法Ford-Fulkerson标号法,61,2019年6月17日,例题：用标号法求下面网络从s到t的最大流量,并找出该网络的最小截集的容量.,第八讲 图与网络优化,62,2019年6月17日,因为t点得到标号,用反向追踪法可找出从s到t的一条增广链,用红线标出;,修改增广链上的流量: 其余弧上的流量不变,于是得到网络上的一个新可行流,重复上述的标号过程,转下一步;,第八讲 图与网络优化,63,2019年6月17日,标号中断,t点得不到标号,网络中没有增广链,该网络的可行流就是最大流,最大流量为,第八讲 图与网络优化,64,2019年6月17日,下面求该网络的最小截集:,第八讲 图与网络优化,65,2019年6月17日,