运筹学第8章163页.ppt

运筹学课件,第八章图与网络分析制作：北京理工大学吴祈宗等,2,第八章图与网络分析,图的基本概念与基本定理树和最小支撑树最短路问题网络系统最大流问题网络系统的最小费用最大流问题中国邮递员问题,本章内容重点,引言,图论应用非常广泛：控制论，信息论，工程技术，交通运输，经济管理，电子计算机等领域；科学研究，市场和社会生活中的许多问题，可以用图论的理论和方法来加以解决。例如，通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局。,4,引言,将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的优化问题。图论越来越受到工程技术人员和经营管理人员的重视。,5,引言,1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图8-1a所示。,引言,A,B,图8-1a）,C,D,引言,当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图8-1b所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。,8,引言,图8-1b）,A,C,D,B,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例8.1:图8-2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。,1.图的基本概念与基本定理,10,1.图的基本概念与基本定理,太原,重庆,武汉,南京,徐州,连云港,上海,郑州,石家庄,塘沽,青岛,济南,天津,北京,图8-2,11,例8.2:有六支球队进行足球比赛，我们分别用点v1v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图8-3所示的有向图反映出来。,1.图的基本概念与基本定理,12,1.图的基本概念与基本定理,v3,v1,v2,v4,v6,v5,图8-3,图论中常用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象、用点与点之间的线表示研究对象之间的特定关系。在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要。因此，图论中的图与几何图，工程图等本质上是不同的。,1.图的基本概念与基本定理,通常把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。如果一个图是由点和边所构成的，那么，称为为无向图，记作G=(V，E)，其中V表示图G的点集合，E表示图G的边集合。连接点vi,vjV的边记作vi,vj，或者vj,vi。如果一个图是由点和弧所构成的，那么称为它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。,例如.图8-4是一个无向图G=（V，E）其中V=v1,v2,v3,v4E=v1,v2,v2,v1,v2,v3,v3,v4,v1,v4,v2,v4,v3,v3,1.图的基本概念与基本定理,v3,v2,v1,v4,图8-4,16,图8-5是一个有向图D=（V，A）其中V=v1,v2,v3,v4,v5,v6,v7A=(v1,v2),(v1,v3),(v3,v2),(v3,v4),(v2,v4),(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7),1.图的基本概念与基本定理,v7,v5,v3,v4,v2,v1,v6,图8-5,一些常用的名词：无向图G或有向图D节点数记作P(G)或P(D),简记作P,边数或者弧数记作q(G)或者q(D),简记作q。如果边vi,vjE,那么称vi,vj是边的端点，或者vi,vj是相邻的。如果一个图G中，一条边的两个端点是相同的,那么称为这条边是环。,1.图的基本概念与基本定理,1.图的基本概念与基本定理,如果两个端点之间有两个端点之间有两条以上的边，那么称为它们为多重边。一个无环，无多重边的图为简单图。一个无环，有多重边的图称为多重图。,v3,v2,v1,v4,图8-4,环,以点v为端点的边的个数称为点v的度，记作d(v)。如上图中d(v1)=3,d(v2)=4,d(v3)=4,d(v4)=3。度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。,1.图的基本概念与基本定理,20,端点的度d(v)：点v作为边端点的个数；奇点：d(v)=奇数；偶点：d(v)=偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E=，无边图,1.图的基本概念与基本定理,定理8.1所有顶点次数之和等于所有边数的2倍。定理8.2在任一图中，奇点的个数必为偶数。,1.图的基本概念与基本定理,22,图的连通性：链：由两两相邻的点及其相关联的边构成的点边序列;如:v0,e1,v1,e2,v2,e3,v3,vn-1,en,vn;v0，vn分别为链的起点和终点；简单链：链中所含的边均不相同；初等链：链中所含的点均不相同,也称通路；,1.图的基本概念与基本定理,23,回路：若v0vn分称该链为开链，否则称为闭链或回路；圈：除起点和终点外链中所含的点均不相同的闭链；连通图：图中任意两点之间均至少有一条通路，否则称作不连通图。,1.图的基本概念与基本定理,24,G1,1.图的基本概念与基本定理,G1=V1,E1,子图：设G1=V1,E1,G2=V2,E2子图定义：如果V2V1,E2E1称G2是G1的子图；真子图：如果V2V1,E2E1称G2是G1的真子图；部分图（支撑子图）：如果V2=V1,E2E1称G2是G1的部分图；导出子图：若V2V1,E2=vi,vj:vi,vjV2,称G2是G1中由V2导出的导出子图。,1.图的基本概念与基本定理,26,G2真子图,G2真子图,1.图的基本概念与基本定理,G2=V2,E2子图、真子图,27,G3子图部分图（支撑子图）,1.图的基本概念与基本定理,部分图：V3=V1,E3E1称G3是G1的部分图；,28,G4导出子图,G4导出子图,1.图的基本概念与基本定理,导出子图：V4V1,E4=vi,vjvi,vjV4,称G4是G1中由V4导出的导出子图。,有向图：关联边有方向弧：有向图的边a=(u,v),起点u,终点v;路：若有从u到v不考虑方向的链,且各方向一致,则称之为从u到v的路；初等路:各顶点都不相同的路；初等回路:u=v的初等路;连通图：若不考虑方向是无向连通图;强连通图：任两点有路;,1.图的基本概念与基本定理,30,2.树和最小支撑树,一、树及其性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。例8.3：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,2.树和最小支撑树,如果用六个点v1，v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。由于任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图8-8是一个不含圈的连通图，代表了一个电话线网。,32,2.树和最小支撑树,图8-8,v6,v3,v4,v2,v5,v1,2.树和最小支撑树,定义8.1无圈的连通图叫做树。性质：定理8.3设图G=(V，E)是一个树P(G)2，那么图G中至少有两个悬挂点。定理8.4图G=（V，E）是一个树的充要条件是G不含圈，并且有且仅有P-1条边。,34,2.树和最小支撑树,定理8.5图G=（V，E）是一个树的充要条件是G是连通图，并且有且仅有P-1条边。定理8.6图G是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。,35,2.树和最小支撑树,从以上定理，不难得出以下结论：（1）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。（2）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。,2.树和最小支撑树,二.支撑树定义8.2设图K=(V,E)是图G=(V,E)的一支撑子图,如果图K=(V,E)是一个树,那么称K是G的一个支撑树。图8.10b是图8-10a的一个支撑树。,v6,v5,v2,v3,v4,v1,v6,v5,v2,v3,v4,v1,图8-10,a）,b）,2.树和最小支撑树,显然,如果图K=(V,E)是图G=(V,E)的一个支撑树,那么K的边数是p(G)-1；G中不属于支撑树K的边构成K的余树，其边数是q(G)-p(G)+1。定理8.7一个图G有支撑树的充要条件是G是连通图。,38,T支撑树（部分图）,1.图的基本概念与基本定理,39,T的余树（部分图）,1.图的基本概念与基本定理,证明:必要性显然；充分性:设图G是连通的，若G不含圈，则G是一个树，从而G是自身的一个支撑树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图G1。若G1不含圈，则G1是G的一个支撑树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一支撑子图G2。依此类推，可以得到图G的一个支撑子图GK，且不含圈，从而GK是一个支撑树。,41,2.树和最小支撑树,以上充分性的证明，提供了一个寻找连通图支撑树的方法叫做“破圈法”。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。,42,2.树和最小支撑树,例8.4:用破圈法求出下图的一个支撑树。,V5,V4,V2,V3,V1,e6,e5,e4,e3,e2,e1,e7,e8,43,取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4v5,v3）中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7，这样，剩下的图不含圈，于是得到一个支撑树，如图所示。,v2,e1,e2,e5,e8,v1,v3,v4,44,2.树和最小支撑树,三、最小支撑树问题定义8.3如果图G=（V，E），对于G中的每一条vi,vj，相应地有一个数wij，那么称这样的图G为赋权图，wij称为边vi,vj的权。这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。,2.树和最小支撑树,定义8.4如果图T=（V，E）是图G的一个支撑树，那么称E上所有边的权之和为支撑树T的权，记作S(T)。如果图G的支撑树T*的权S(T*)，在G的所有支撑树T中的权最小，即S(T*)=minS(T)，那么称T*是G的最小支撑树。,46,2.树和最小支撑树,常用的有破圈法和生长法（避圈法）两个方法：（1）在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；（1）去掉该圈中权数最大的边；反复重复（1）（2）两步，直到最短树。,1.破圈法,47,2.树和最小支撑树,例8.5某六个城市之间的道路网如图8-13a所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。,2.树和最小支撑树,v6,v5,v2,v3,v4,图8-13a,v1,6,2,7,5,3,5,4,4,v3,v2,v1,v4,v6,v5,5,1,3,1,4,2,图8-13b,顺序：浅兰，黄，粉红，白,2.树和最小支撑树,解：如图8-13a，用破圈法求解最小支撑树。（1）圈v1,v2,v3,v1，删圈中权最大边v1,v3；（2）圈v3,v5,v2,v3，去掉边v2,v5；（3）圈v3,v5,v4,v2,v3，去掉边v3,v5；（4）圈v5,v6,v4,v5，这里有两条权最大的边v5,v6和v4,v6。任意删一条，如v5,v6。这时得到一个不含圈的图，即是最小支撑树。如图8-13b所示。,50,2.树和最小支撑树,从网络图中依次寻找权数较小的边，寻找过程中，节点不得重复，即不得构成圈。注意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最短树或证明网络不存在最短树。,2.成长法(避圈法),2.树和最小支撑树,用“生长法”求解例8.5解：考虑赋权图8-13a，任取一点，如从v1取权较小的边（v1,v2）；从v2取权较小的边（v2,v3）；从v3取权较小的边（v3,v4）；同理依次取（v4,v5），（v4,v6）。这时得到了如图8-13b所示的最小支撑树。,2.树和最小支撑树,v6,v5,v2,v3,v4,图8-13a,v1,6,2,7,5,3,5,4,4,v3,v2,v1,v4,v6,v5,5,1,3,1,4,2,图8-13b,顺序：黄，粉红，白，绿，浅兰,53,作业：,用破圈法和生长法两种方法求解习题1,54,3.最短路径问题,一.引言最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。,55,3.最短路径问题例8.6:如图8-14所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线路。,图8-14,v1,1,56,3.最短路径问题,从v1到v8的路线是很多的。比如从v1出发，经过v2,v5到达v8或者从v1出发，经过v4，v6，v7到达v8等等。但不同的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是6+1+6=13单位，按照第二个路线，总长度是1+10+2+4=17单位。,一般意义下的最短路问题：设赋权有向图D=（V，A），对每个弧a=（vi,vj），相应地有权wij。vs,vt是D中的两个顶点，P是D中从vs到vt的任意一条路，定义路的权是P中所有弧权的和，记作S(p)。最短路问题就是求S(P0)=minS(p)。P0叫做从vs到vs的最短路。P0的权S(P0)叫做从vs到vt的距离，记作d（vs，vt）。由于D是有向图，很明显d（vs，vt）与d（vt，vs）一般不相等。,58,3.最短路径问题,二、Dijkstra（狄克斯拉方法）算法下面介绍在一个赋权有向图中寻求最短路的方法Dijkstra算法，它是在1959年提出来的。目前公认，在所有的权wij0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。,Dijkstra算法的基本思想,从vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的标号,分为两类：P标号：表示从vs到该点的最短路权T标号：表示从vs到该点最短路权的上界。算法的每一步是去修改T标号，把某一个具有T标号的点改变为具有P标号的点，使图D中具有P标号的顶点多一个。这样，至多经过P-1步，就可求出从vs到各点vj的最短路。,说明：在例8.6中,S=1。因为wij0，d(v1,v1)=0。这时，v1是具有P标号的点。再看从v1出发的三条弧(v1,v2)，(v1,v3)和(v1,v4)。如果从v1出发沿(v1,v2)到达v2，这时的路程是d(v1,v1)+w12=6单位；如果从v1出发，沿(v1,v3)到达v3，则是d(v1,v1)+w13=3单位；同理，如果从v1出发沿(v1,v4)到达v4，是d（v1,v1）+w14=1单位。,说明（续）,因此，从v1出发到达v4的最短路必是（v1,v4），d（v1,v4）=1。这是因为从v1到达v4的任一条路，假如不是（v1,v4），则必先沿（v1,v2）到达v2，或者沿（v1,v3）到达v3，而这时的路程已是6或者3单位。由于wij0，因此不论他如何再从v2或者v3到达v4，所经过的总路程都不会比1少，于是就有d（v1,v4）=1。于是V4变成具有P标号的点。,例8.6说明：,从v1出发的三条弧(v1,v2)，(v1,v3)和(v1,v4)，mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14=d（v1,v4）=1。,P(V1),1,再看从v1和v4指向其余点的弧：从V1出发，分别沿(v1,v2),(v1,v3)到达v2，v3，经过的路程是6或者3单位；从v4出发沿(v4,v6)到达v6，经过的路程是d(v1,v4)+w46=1+10=11单位。而mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46=d（v1,v1）+w13=3单位。根据同样的理由，可以断定，从v1到达v3的最短路是（v1,v3），d（v1,v3）=3。这样，又使点v3变为具有P标号的点，不断重复以上过程，就可以求出从vs到达任一点vj的最短路。,例8.6说明（续）：,再看从v1和v4指向其余点的弧,mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46=d（v1,v1）+w13=3。,P(V1),P(V3),1,3.最短路径问题,在下述的Dijkstra算法中，以P，T分别表示某一个点的P标号，T标号。Si表示在第i步时，具有P标号点的集合，为了在算出从vs到各点的距离的同时，也找出从vs到各点的最短路，于是，给每一个点v一个值。当算法结束时，如果(v)=m，则表示在从vs到v的最短路上，v的前一个点是vm。如果(v)=M，则表示在图D中不含有从vs到达v的路。(v)=0，表示v=vs。,Dijkstra算法的步骤如下：,开始（i=0）令S0=vs，P（vs）=0，(vs)=0，对每一个vvs，令T（v）=+，(v)=M，令k=s；（1）如果Si=V，则算法结束，对每一个vSi，d（vs,v）=P（v）。否则转入（2）；（2）考察每一个使(vk,vj)A，且vjSi的点vj，如果T(vj)P(vk)+wkj，则把T(vj)改变为P(vk)+wkj，把(vj)改变为k，否则转入（3）；,67,3.最短路径问题,（3）令T(vji)=minT(vj)vjSi，如果T(vji)+，则把vji的T标号改变为P标号P(vji)=T(vji)，令Si+1=Sivji，k=ji，把i换成i+1，转入（1）；否则结束。这时，对vSi，d(vs,v)=P(v)；对vSi，d(vs,v)=T(v)。,3.最短路径问题,用Dijkstra算法求解例8.6。vs为起点:开始,s=1,i=0;S0=v1,P(v1)=0,(v1)=0,T(vi)=+,(vi)=M,i=2,3,9,k=1。(2)(v1,v2)A，v2S0，P(v1)+w12w32+P(v3)，将T(v2)改变为P(v3)+w32=5,(v2)改变为3。（3）在所有的T标号中，T(v2)=5最小，于是令P(v2)=5，S3=v1,v4,v3，k=2。i=3：（2）将T(v5)改变为P(v2)+w25=6，(v5)改变为2。（3）在所有的T标号中，T(v5)=6最小，于是令P(v5)=6，S4=v1,v4,v3，k=5。,3.最短路径问题,（2）将T(v6)，T(v7)，T(v8)分别改变为10,9，12，将(v0)，(v7)，(v8)改变为5。（3）在所有的T标号中，T(v7)=9最小，于是令P(v7)=9，S5=v1,v4,v3,v2,v5,v7，v=7。i=5：（2）（v7,v8）A，v8S5，但是T(v8)w78+P(v7)，故T(v8)不变。（3）在所有的T标号中，T(v6)=10最小，于是,令P(v6)=10，S6=v1,v4,v3,v2,v5,v7,v6，k=6。,3.最短路径问题,i=6：（2）从v6出发没有弧指向不属于S6的点，因此转入（3）。（3）在所有的T标号中，T(v8)=12最小，令P(v8)=12，S7=v1,v4,v3,v2,v5,v7,v6,v8，k=8。i=7：仅有T标号的点为v9，T（v9）=+，算法结束。此时，把P标号和值标在图中，如图8-15所示,例题求解图示（1）,图8-15,T(V6)=+,T(V7)=+,(V1)=0,P(V1)=0,P(V4)=1,(V4)=1,(V6)=M,(V5)=M,T(V2)=6,T(V5)=+,T(V8)=+,(V7)=M,(V2)=1,(V8)=M,T(V9)=+,(V9)=M,T(V3)=3,(V3)=1,1,i=0S1=S0v4=v1,v4,v1,v3,例题求解图示（2）,图8-15,T(V6)=11,T(V7)=+,(V1)=0,P(V1)=0,P(V4)=1,(V4)=1,(V6)=4,(V5)=M,T(V2)=6,T(V5)=+,T(V8)=+,(V7)=M,(V2)=1,(V8)=M,T(V9)=+,(V9)=M,P(V3)=3,(V3)=1,1,i=1S2=S1v3=v1,v4,v3,v1,v3,例题求解图示（3）,图8-15,T(V6)=11,T(V7)=+,(V1)=0,P(V1)=0,P(V4)=1,(V4)=1,(V6)=4,(V5)=M,P(V2)=5,T(V5)=+,T(V8)=+,(V7)=M,(V2)=3,(V8)=M,T(V9)=+,(V9)=M,P(V3)=3,(V3)=1,1,i=2S3=S2v2=v1,v4,v3,v2,v1,v3,例题求解图示（4）,图8-15,T(V6)=11,T(V7)=+,(V1)=0,P(V1)=0,P(V4)=1,(V4)=1,(V6)=4,(V5)=2,P(V2)=5,P(V5)=6,T(V8)=+,(V7)=M,(V2)=3,(V8)=M,T(V9)=+,(V9)=M,P(V3)=3,(V3)=1,1,i=3S4=S3v5=v1,v4,v3,v2,v5,v1,v3,例题求解图示（5）,图8-15,T(V6)=10,P(V7)=9,(V1)=0,P(V1)=0,P(V4)=1,(V4)=1,(V6)=5,(V5)=2,P(V2)=5,P(V5)=6,T(V8)=12,(V7)=5,(V2)=3,(V8)=5,T(V9)=+,(V9)=M,P(V3)=3,(V3)=1,1,i=4S5=S4v7=v1,v4,v3,v2,v5,v7,v1,v3,例题求解图示（6）,图8-15,P(V6)=10,P(V7)=9,(V1)=0,P(V1)=0,P(V4)=1,(V4)=1,(V6)=5,(V5)=2,P(V2)=5,P(V5)=6,T(V8)=12,(V7)=5,(V2)=3,(V8)=5,T(V9)=+,(V9)=M,P(V3)=3,(V3)=1,1,i=5S6=S5v6=v1,v4,v3,v2,v5,v7,v6,v1,v3,例题求解图示（7）,图8-15,P(V6)=10,P(V7)=9,(V1)=0,P(V1)=0,P(V4)=1,(V4)=1,(V6)=5,(V5)=2,P(V2)=5,P(V5)=6,P(V8)=12,(V7)=5,(V2)=3,(V8)=5,T(V9)=+,(V9)=M,P(V3)=3,(V3)=1,1,i=6S7=S6v8=v1,v4,v3,v2,v5,v7,v6,v8,v1,v3,例题求解图示（8）,图8-15,P(V6)=10,P(V7)=9,(V1)=0,P(V1)=0,P(V4)=1,(V4)=1,(V6)=5,(V5)=2,P(V2)=5,P(V5)=6,P(V8)=12,(V7)=5,(V2)=3,(V8)=5,T(V9)=+,(V9)=M,P(V3)=3,(V3)=1,1,最短路：V1-(V4)V3-V2-V5-(V6,V7)V8,v1,v3,81,3.最短路径问题,图8-15中，从v1到v8的最短路：因为(v8)=5，故最短路经过点v5；又因为(v5)=2，故最短路经过点v2；依次类推，(v2)=3，(v3)=1于是，最短路经过点v3，v1。这样，从v1到v8的最短路是（v1，v3，v2，v5，v8）。同理，可以求出从v1到任一点vi的最短路，显然不存在从v1到v9的最短路。,3.最短路径问题,对于一个赋权(无向)图G=(V，E)，因为边vi,vj可以看作2条弧（vi,vj）和(vj,vi)，并且具有相同的权wij。这样，在一个赋权（无向）图中，如果有所有的权wij0，只要将Dijkstra算法中的“(2)看作每一个使(vk,vj)A，且vjSj的点vj”改变为“(2)看作每一个使vk,vjE，且vjSj的点vj”而其他的条件不变，同样可以求出从vs到各点的最短路（对于无向图叫做最短链）。,83,3.最短路径问题,习题:将例8-6中所示的赋权有向图的箭头去掉，然后求出无向图中从vs到各点的最短路。,84,作业：,P2202,略去证明,证明Dijkstra算法。只须证明vSi,P(v)是从vs到v的最短路权，即P(v)=d(vs.v)。证:用数学归纳法。当i=0时，结论显然成立。假设i=n时，结论成立。看i=n+1的情形，由于Sn+1=Snvjn,所以只要证明P(vjn)=d(vs,vj)。,根据算法，vjm是具有最小T标号的点，即Tn(vjn)=minTn(vj)，其中vjSm.这里，用Tn()表示当i=n时，执行步骤（3）时点的T标号。设H是图D中任意一条从vs到vjn的路。因为vsSn,而vjnSn,所以从vs出发，沿H必存在一条弧，其始点属于Sn，而终点不属于Sn。令（vr,vl）是第一条这样的弧，于是H=(vsvr,vlvjn),s(H)=S(vs,vr)+wrl+S(vlvjn)。,3.最短路径问题,由归纳假设，P(vr)是从vs到vr的最短路权，于是，有S(H)P(vr)+wrl+S(vlvjn)。根据算法中的T标号修改规则，因为vrSn,vlSn,故P(vr)+wrlTn(vl),而Tn(vl)Tn(vjn)，且S(vlvjn)0，所以S(H)Tn(vjn)+S(vl,vjn)Tn(vjn)。这样，就证明了Tn(vjn)是从vs到vjn的最短权。根据算法，P(vjn)=Tn(vjn),于是就有P(vjn)=d(vs,vjn)。,Dijkstra算法仅适合于所有的权wij0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。例如图8-16中，根据Dijkstra算法，可以得出从v1到v2最短路权是2，但是这显然不对，因为从v1到v2的最短路是（v1,v3,v2）,权是-1。,v1,v3,v2,2,2,-3,图8-16,3.最短路径问题,Ford(福德)算法:当赋权有向图存在负权弧时，求最短路的方法:首先，设从任一点vi到任一点vj都有一条弧，如果在图D中，（vi,vj）不属于A,则添加弧(vi,vj),并且令wij=+.,从vs到vj的最短路是从vs点出发，沿着这条路到某个点vi，再沿弧(vi,vj)到点vj。显然，从vs到vi的这条路必定是从vs到vi的最短路。否则从vs到vj的这条路将不是最短路。于是，从vs到vj的距离d(vs,vj)满足以下条件d(vs,vj)=mind(vs,vi)+wij,ii=1,p,p=p(D),3.最短路径问题,这个关系式的解d(vs,v1)d(vs,vp).可利用如下的递推公式求解d(1)(vs,vj)=wsj,j=1,p.d(t)(vs,vj)=mind(t-1)(vs,vi)+wij,t=2,3i当计算到第k步时,对一切的j=1,p,有d(k)(vs,vj)=d(k-1)(vs,vj)则d(k)(vs,vj),j=1,p,就是从vs到各点vj的最短路径的权。,92,设C是赋权函数有向图D中的一个回路。如果回路C的权S（C）是负数那么称C是D中的一个负回路。可以证明以下的结论：（1）如果赋权有向图D不含有负回路，那么从vs到任一点的最短路至多包含P-2个中间点，并且必可取为初等路。,此方法有如下结论,93,（2）如果赋权有向图D不含有负回路，那么上述递推算法至多经过P-1次迭代必收敛，可以求出从vs到各个点的最短路权。（3）如果上述算法经过P-1次迭代，还存在在着某个j，使得d(p)(vs,vj)d(p-1)(vs,vj)，那么D中含有负回路。这时，不存在从vs到vj的路（权无界）。,94,3.最短路径问题,例8.7:在如图8-17所示的赋权有向图中求从v1到各点的最短路。解:利用上述递推公式，将求解结果列出如表8-18所示。可以看出，当t=4时，有d(t)(vs,vj)=d(t-1)(vs,vj)j=1,8因此，表中的最后一列，就是从v1到v1,v2,v8的最短路权。,95,3.最短路径问题,图8-17,1,1,1,1,1,1,2,3,3,5,5,2,2,3,6,7,8,wij,d(t)(vs,vj),3.最短路径问题,为了求出从v1到各个点的最短路，一般采用反向追踪的方法：如果已知d(vs,vj),那么寻求一个点vk,使得d(vs,vk)+wkj=d(vs,vj),然后记录下(vk,vj).在看d(vs,vk),寻求一个点vi,使得d(vs,vi)+wik=d(vs,vk)依次类推，一直到达vs为止。这样，从vs到vj的最短路是（vs,vi,vk,vj）.,98,在例中，由上表知，d(v1,v8)=6,由于d(v1,v6)+w68=(-1)+7记录下v6;由于d(v1,v3)+w36=d(v1,v6),j记录下v3;由于d(v1,v1)+w13=d(v1,v3),于是，从v1到v8的最短路是(v1,v3,v6,v8),99,作业：,用Ford(福德)算法求解习题-2,4.网络系统的最大流问题,一引言在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。,4.网络系统的最大流问题,图8-18,vt,v3,v2,v1,v4,vs,17,3,5,10,8,6,11,4,5,3,Cij,图8-18是一个网络。弧旁边的权就是对应的容量（最大通过能力）。要求指定一个运输方案，使得从vs到vt的货运量最大，这是寻求网络系统的最大流问题。,102,4.网络系统的最大流问题,二、基本概念定义8.5设赋权有向图D=(V,A),在V中指定一个发点vs和一个收点vt,其他的点叫做中间点。对于D中的每一个弧(vi,vj)A,都有一个权cij叫做弧的容量。我们把这样的图D叫做一个网络系统，简称网络，记做D=（V，A，C）。,103,网络D上的流,指定义在弧集合A上的一个函数f=f(vi,vj)=fij;f(vi,vj)=fij叫做弧在(vi,vj)上的流量。,4.网络系统的最大流问题,v3,v2,v1,v4,vs,（2）,（3）,（2）,（5）,（3）,（3）,（6）,（1）,（1）,（2）,fij,图8-19表示了网络上的一个流（运输方案）弧上的流量fij就是运输量例如fs1=5,fs2=3,f13=2等等。,vt,图8-19,105,4.网络系统的最大流问题,网络系统上流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的流入量与流出量的代数和等于零；(3)每一个弧上的流量不能超过它的最大通过能力（即容量）。,4.网络系统的最大流问题,定义8.6网络上的一个流f叫做可行流，如果f满足以下条件：（1）容量条件：对于每一个弧(vi,vj)A,有0fijcij；（2）平衡条件：对于发点vs，有fsj-fjs=v(f)对于收点vt，有ftj-fjt=-v(f)对于中间点，有fij-fji=0其中发点的总流量（或收点的总流量）v(f)叫做这个可行流的流量。,107,4.网络系统的最大流问题,任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量v(f)达到最大值。,108,饱和弧与零流弧,设流f=fij是网络D上的一个可行流。我们把D中fij=cij的弧叫做饱和弧，fij0的弧为非零流弧，fij=0的弧叫做零流弧。,4.网络系统的最大流问题,设是网络D中连接发点s和收点vt的一条链。定义链的方向是从vs到vt，于是链上的弧被分为两类：一是弧的方向与链的方向相同，叫做前向弧，前向弧的集合记做+。二是弧的方向与链的方向相反，叫做后向弧，后向弧的集合记做-。,在下图（8-18与8-19合并图）中，(v4,v3)是饱和弧，其它弧均是非饱和弧、非零流弧。,如图在链（vs,v1,v2,v3,v4,vt)中=(v4,v3)；+=(vs,v1),(v1,v2),(v2,v3),(v4,vt)。,v3,v2,v1,v4,vs,（17,2）,（3,3）,（5,2）,（10,5）,（8,3）,（6,3）,（11,6）,（4,1）,（5,1）,（3,2）,fij,vt,4.网络系统的最大流问题,定义：如果链满足以下条件：1在弧(vi,vj)+上，有0fijcij,即+中的每一条弧是非饱和弧。2在弧(vi,vj)-上，有00。取,117,定理8.8实际上提供了一个寻求网络系统最大流的方法：,如果网络D中有一个可行流f，只要判断网络是否存在关于可行流f的增广链。如果没有增广链，那么f一定是最大流。如有增广链，那么可以按照前面说明，不断改进和增大可行流f的流量，最终可以得到网络中的一个最大流。,三、标号法,用给顶点标号的方法来定义V1*。在标号过程中，有标号的顶点是V1*中的点，没有标号的点不是V1*中的点。如果vt有了标号，则表示存在一条关于f的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f增广链。这样，就得到了网络中的一个最大流和最小截集。,4.网络系统的最大流问题,1标号过程在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种）。或者是未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的。以便找出增广链。第二个标号是为了用来确定增广链上的调整量。,4.网络系统的最大流问题,标号过程开始，先给vs标号(0,+)。这时，vs是标号未检查的点，其他都是未标号点。一般地，取一个标号未检查点vi，对一切未标号点vj：1）如果在弧(vi,vj)上，fij0,那么给vj标号(-vi,l(vj)，其中l(vj)=minl(vi),fij。这时，vj成为标号未检查点。于是vi成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广链，转入下一步调整过程。,122,2.调整过程首先按照vt和其他的点的第一个标号，反向追踪，找出增广链。例如，令vt的第一个标号是vk，则弧（vk,vt）在上。再看vk的第一个标号，若是vi，则弧(vi,vk)都在上。依次类推，直到vs为止。这时，所找出的弧就成为网络D的一条增广链。取调整量=l(vt),即vt的第二个标号，,4.网络系统的最大流问题,123,fij+，当(vi,vj)+令fij=fij-，当(vi,vj)-其他不变再去掉所有的标号，对新的可行流f=fij,重新进行标号过程，直到找到网络D的最大流为止。,4.网络系统的最大流问题,124,4.网络系统的最大流问题,V4,V1,V2,V3,Vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,1）,（2,2）,（5,3）,（1,1）,（1,1）,(Cij,fij),Vt,图8-21,例8.8:求图8-21的网络最大流，弧旁的权数表示（cij,fij）。用标号法解解:1.标号过程。（1）首先给vs标号（0，+）（2）看vs:在弧(vs,v2)上,fs2=cs3=3,不具备标号条件。在弧(vs,v1)上,fs1=10,故给v2标号（-v1,l(v2)）,其中l(v2)=minl(v1),f21=min4,1=1.（4）看v2:在弧（v2,v4）上，f24=30,故给v3标号（-v2，l(v3),其中l(v3)=minl(v2),f32=min1,1=1。,（5）在v3,v4中任意选一个，比如v3,在弧(v3,vt)上，f3t=1c3t=2,故给vt标号(v3,l(vt),其中l(vt)=minl(v3),(c3t-f3t)=min1,1=1.因为vt被标上号，根据标号法，转入调整过程。,4.网络系统的最大流问题,128,4.网络系统的最大流问题,V4,V1,V2,V3,Vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,1）,（2,2）,（5,3）,（1,1）,（1,1）,(Cij,fij),Vt,(V2,1),(0，+),(-V1,1),(Vs,4),(-V2,1),图8-22,(V3,1),2.调整过程从vt开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从vs到vt的增广链，如图8-22中双箭线所示。显然,+=(vs,v1),(v3,vt),-=(v2,v1),(v3,v2)取=1，在上调整f，得到fs1+=1+1=2在+上f3t+=1+1=2在+上f*=f21-=1-1=0在-上f32-=1-1=0在-上其他的不变,4.网络系统的最大流问题,130,调整后的可行流f*，如图8.23所示，再对这个可行流从新进行标号过程，寻找增广链。首先给vs标号（0，+），看vs,给v1标号（vs,3）。看v1,在弧（v1,v3）上，f13=c13,弧（v2,v1）上，f21=0,均不符合条件。因此标号过程无法进行下去，不存在从vS到vt的增广链，算法结束。,4.网络系统的最大流问题,131,4.网络系统的最大流问题,这时，网络中的可行流f*即是最大流，最大流的流量v(f*)=fs1+fs2=5.同时，也找出D的最小截集（V1，V1），其中V1是标号的集合，V1是未标号的集合。,4.网络系统的最大流问题,V4,V1,V2,V3,Vs,（2,2）,（3,0）,（4,3）,（3,3）,（5,2）,（2,2）,（5,3）,（1,0）,Vt,(0,+),(Vs,3),图8-23,(Cij,fij),（1,0）,133,图8-21的另一最大流,V4,V1,V2,V3,Vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,1）,（2,2）,（5,3）,（1,1）,（1,1）,(Cij,fij),Vt,(V2,1),(0，+),(-V1,1),(Vs,4),(-V2,1),(V4,2),图8-21的另一最大流(续),V4,V1,V2,V3,Vs,（2,1）,（3,0）,（4,4）,（3,3）,（5,2）,（2,2）,（5,4）,（1,0）,（1,1）,(Cij,fij),Vt,(0，+),(Vs,3),135,作业：,习题3,136,在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。,5.网络系统的最小费用最大流问题,设一个网络D=(V1，A，C)，对于每一个弧(vi,vj)A,给定一个单位流量的费用bij0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，并且流的总费用b(f)=bijfij达到最小。（vi,vj）A,5.网络系统的最小费用最大流问题,在一个网络D中，当沿可行流f的一条增广链，以调整量=1改进f，得到的新可行流f的流量，有v(f)=v(f)+1，此时总费用b(f)比b(f)增加了b(f)-b(f)=bij(fij-fij)-bij(fij-fij)=bij-bij+-+-将bij-bij叫做这条增广链的费用。,5.网络系统的最小费用最大流问题,139,5.网络系统的最小费用最大流问题,如果可行流在流量为v(f)的所有可行流中的费用最小，并且是关于f的所有增广链中的费用最小的增广链。那么沿增广链调整可行流f，得到的新可行流f，也是流量为v(f)的所有可行流中的最小费用流。依次类推，当f是最大流时，就是所要求的最小费用最大流。,显然，零流f=0是流量为0的最小费用流。一般地，寻求最小费用流，从零流f=0开始。问题是：如果已知f是流量为v(f)的最小费用流，那么就要去寻找关于f的最小费用增广链。,5.网络系统的最小费用最大流问题,141,重新构造一个赋权有向图M(f)，其顶点是原网络D的顶点，而将D中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义M(f)中弧的权wij为：,142,并且将权为+的弧从M(f)中略去。即当0fijcij时，成为2条方