第七章图与网络优化.ppt

1、引言,图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。,引言,随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。,引言,十八世纪的哥尼

2、斯堡城中流过一条河（普雷.格尔河），河上有 7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡 7 桥”难题。,引言,引言,图7.1 b,引言,为了寻找答案，1736年欧拉将这个问题抽象一笔画问题。 即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。 欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。,引言,下面我们来看一个案例 国庆大假期间旅

3、游非常火爆，机票早已订购一空。 成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。 旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。 根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：,引言,各办事处已订购机票情况表：,引言,将此问题通过图的模型描述： 下图中，点各城市， 带箭头连线从箭尾城市到箭头城市已订购有机票，带箭头连线旁的数字机票数量。,郑州办事处已订有的到 北京的机票数量。,图的基本概

4、念,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例1:图7.2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。,图的基本概念,图的基本概念,例2:有六支球队进行足球比赛，我们分别用点v1v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图7.3所示的有向图反映出来。,图的基本概念,图的基本概念,图及其分类和术语 图论中我们所关心的仅仅是图中

5、有多少个点，点与点之间有无线来连接， 即我们研究的是某个系统中的元素点， 以及这些元素之间的某种关系连线。,图的基本概念,从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。 一般来说，通常用点表示研究对象用点与点之间的线表示研究对象之间的特定关系。 由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要。 因此，图论中的图与几何图，工程图等本质上是不同的。,图的基本概念,图论中的图是由点和点与点之间的线所组成的。 把点与点之间不带箭头的线叫做边， 带箭头的线叫做弧。 如果一个图是由点和边所

6、构成的，称为无向图，记作G =(V，E)， V ：表示图 G 的点集合，E：表示图G的边集合。 连接点vi,vjV的边记作vi,vj，或者vj,vi。,图的基本概念,如果图是由点和弧所构成的，称为有向图，记作D =(V,A)， V 表示有向图D的点集合， A 表示有向图D的弧集合。 一条方向从vi指向vj的弧，记作(vi,vj)。,图的基本概念,例：图7-7 是一个无向图。在G=(V,E)中，V=v1,v2,v3,v4， E=e1,e2,e3,e4 ,e5,e6,e7。,图的基本概念,图7-8 是一个有向图。,图的基本概念,图的基本概念,无向图G=(V,E)中 端点：若边e=v,uE，则称v,

7、u是e的端点，也称 vi,vj是相邻的。 关连边：v,u是相邻的，称e是点v及点u的关连边。 环：若图G中，某条边的两个端点相同，则称e是环。,图的基本概念,多重边：若两个点之间有多于一条的边，称这些边为多重边。,简单图：一个无环、无多重边的图称为简单图。,多重图：一个无环、但允许有多重边的图称为多重图。,图的基本概念,次：以点v为端点的边的个数称为v的次，记dG(v)或d(v)。,悬挂点：并且称次为1的点为悬挂点。 悬挂边：悬挂点的关联边称为悬挂边。,孤立点：次为0的点称为孤立点。,奇点：次为奇数的点称为奇点。 偶点：次为偶数的点称为偶点。,在环上的端点的次为2。,图的基本概念,定理1 图G

8、=(V,E)中，所有点的次之和等于所有边数的两倍，即,图的基本概念,定理2：任意一个图中，奇点的个数为偶数。 证明：设V1和V2分别是G中奇点和偶点的集合，由定理1，有,图的基本概念,链：图G=(V,E)，一个点、边的交错序列则称为一条连接vi1和vir的链。记为(vi1，vi2， vir)。,圈：在链(vi1，vi2， vir)中，若vi1= vir，则称之为一个圈，记为(vi1，vi2， vir)。,中间点：称点vi2，vi3， vir-1为链的中间点。,图的基本概念,初等链：若链中的点vi1，vi2， vir都是不同的，则称之为初等链。,初等圈：若圈中的点vi1，vi2， vir-1都是

9、不相同的，则称之为初等圈。,简单圈(简单链)：若链中或圈中含有的边均不相同，则称之为简单链或简单圈。,图的基本概念,例：图7-9中 (v1，v2， v3，v4 ， v5， v3， v6，v7)是一条简单链，不是初等链。,图的基本概念,(v1，v2， v3， v6，v7)是一条初等链。 (v1，v2， v3，v4 ， v1)是一个初等圈。,图的基本概念,(v4 ， v1，v2， v3，v5 ， v7，v6， v3，v4 )是简单圈，不是初等圈。,图的基本概念,连通图：在图G=(V,E)中，若任意两个点之间，至少有一条链，则称G是连通图，否则称为不连通图。 连通分图：若图G是不连通图，它的每个连通

10、的部分称为G的一个连通分图(简称分图) 。,图的基本概念,给了一个图G =(V,E)，如果图G=(V,E)，使V=V及EE，则称G是G的一个支撑子图。 例5：若图G如图7-6(a)所示：则图7-6(b)所示是图G的一个子撑子图。,图的基本概念,设一个有向图D=(V,A)，从D中去掉所有弧上的箭头，就得到一个无向图，称之为D的基础图，记为G(D)。 若a=(u,v)是图D的一条弧，称u为a的始点，v为a的终点，称弧a是从u指向v的。,图的基本概念,若(vi1，ai1， vi2，ai2， viK-1，aiK-1， viK)是D中的一条链，并且对t=1,2,k-1，均有ait=(vit,vit+1)

11、，称之为从vi1到viK的一条路。 回路：若路的第一个点和最后一个点相同，则称之为回路。,图的基本概念,初等路：若弧中的点vi1，vi2， vir-1，vir都是不同的，则称之为初等路。 初等回路：若回路中的点vi1，vi2， vir-1都是不相同的，则称之为初等回路。,图的基本概念,例 下图中， (v3，(v3， v2)，v2，( v2， v4)，v4, (v4， v5)，v5，( v5， v3) ，v3)是一条回路。,图的基本概念,(v1，(v1， v2)，v2，( v2， v4)，v4， (v4， v6)，v6，( v6， v7) ，v7)是从v1到v7的路。,第二节 树,一、树及其性质

12、 在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。 例4：已知有六个城市，它们之间 要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,第二节 树,如果用六个点v1v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。 六个城市的一个电话网就作成一个图。由于任意两个城市之间均可以通话，这个图必须是连通图。 并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。 图7-11是一个不含圈的连通图，代表了一个电话线网。,第二节 树,图7-11,第二节 树,定义1 ：一个无圈的连通图叫做树。 树的一

13、些重要性质： 树的性质： 1、如果树的节点个数为p，则边的个数为p-1 2、树中任意两个节点之间只有唯一的一条链 3、在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈。,第二节 树,定理3：设图G=(V,E)是一个树，p(G)2,则G中至少有两个悬挂点。,证明：令p=(v1,v2,vk)是G中含边数最多的一条初等链，因p(G)2，并且G是连通的，故链p中至少有一条边，从而v1与vk是不同的。只需证明v1是悬挂点，即d(v1)=1。,第二节 树,利用反证法，若d(v1)2,则存在边v1,vm,使m2。若点vm不在p上，则（vm,v1,v2,vk）是G中的一条初等链，它含的边数比p多一条，

14、这与p是含边数最多的初等链矛盾。 若点vm在P上，则（v1,v2,vm,v1）是G中的一个圈，这与树的定义矛盾。 于是必有d(v1)=1，即v1是悬挂点。 同理可证，vk也是悬挂点。因而G至少有两个悬挂点。,第二节 树,定理4 图G=（V，E）是一个树的充要条件是G不含圈，并且有且仅有P-1条边。 q(G)=p(G)-1。（边数=点数-1） 证明：必要性 设G 是树，由树的定义，G 不含圈 ， 故只须证明 G 恰有p-1条边。 对点数 p 施行归纳法 ,当 p =1、2 时结论显然成立。设当 pn 时结论成立。设p(G)=n+1。 由定理3，G含有悬挂点，设悬挂点为v1 ， 考虑图G-v1，则

15、p(G-v1)=n ， 由归纳假设，q（G-v1）=n-1， 于是q(G)=q（G-v1）+1=n=p(G)-1,必要性证完。,第二节 树,充分性 只需证明G 是连通图。 反设G不连通，G含s个连通分图G1，G2，, Gs，(s2)， 那么每个 Gi(i=1,2,s)都连通而且不含圈， 所以都是树，设 Gi 有pi个点， 由必要性知 : q（Gi)=p(Gi)-1 ,于是,第二节 树,定理5 图G=（V，E）是一个树的充要条件是G是连通图，q(G)=p(G)-1 证明 必要性 设G是树，根据树的定义，G连通； 由定理4， q(G)=p(G)-1 ，必要性证毕。,第二节 树,充分性 只要证明G

16、不含圈，对图的点数施行归纳。 当 p(G)=1，2时，结论显然成立。 设结论对p(G)=n时成立， 现设p(G)=n+1，先证G必有悬挂点。 若没有悬挂点，因G是连通的，且p(G)2， 故对每个点vi，有d ( vi) 2 ，,第二节 树,这与q(G)=p(G)-1矛盾，故G必有悬挂点。 设v1是G的一个悬挂点，考虑图G-v1 ， 这个图仍是连通的， p(G-v1)=p(G)-1=(n+1)-1=n, q(G-v1)=q(G)-1=p(G)-2=p(G-v1)-1， 由归纳假设，图G- v1 不含圈， G 也不含圈。证毕！,第二节 树,定理 6 图 G 是树 的充要条件为： G 的任意两点之间

17、恰有一条链。 必要性 因G连通，故G的任意两点间必有链；但若两点间有两条链，则G中必含圈，与G为树矛盾。所以G的任意两点间恰有一条链。 充分性 设G中任意两点之间恰有一条链，则G连通。若G中含有圈，则圈上任意两点之间有两条链，与两点间链的唯一性矛盾。即G为连通的无圈图，故为树。证毕。,第二节 树,从以上定理，不难得出以下结论： （1）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。 （2）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。,2.2图的支撑树,定义 2 设图T=（V，E）是图G=（V，E）的支撑子图，若T=（V，E）是树，

18、则称T为G的支撑树。 例:图7-14 若T=（V，E）是图 G=（V，E）的支撑树， 则T的边数： q(T)= p(T)-1= p(G)-1， G 中不属于T的边数是 q(G)-（p(G)-1）= q(G)-p(G)+1 。,图的支撑树,定理 7 图G有支撑树的充分必要条件是图G是连通图。 必要性显然。 充分性 设G连通。若G不含圈，则G本身是一个树，从而G是它自身的一个支撑树。 若G含圈，从该圈中任意去掉一边，得G的一个支撑子图G1，若G1不含圈，则G1是G的一个支撑树； 若 G1仍含圈，从圈中再任意去掉一条边， 得图G的一个支撑子图G2，如此反复进行，最后必得G的一个支撑子图Gk，它不含圈

19、，于是Gk是G的一个支撑树。证毕！,图的支撑树,寻找连通图的支撑树的方法： 1、 “破圈法” 2、 “避圈法”,图的支撑树,1、 “破圈法”：任取一个圈，从圈中去掉一边，重复这个步骤，直到不含圈为止，即得到一个支撑树。(在破圈法中去掉的边数必是q(G)-p(G)+1条),图的支撑树,2、 “避圈法” 在图中任取一边e1，再取一条与e1不构成圈的边e2，在取一条与e1，e2不构成圈的边e3，重复这个过程；因顶点个数有限，最后必得一支撑树。(在避圈法中取出的边数必是p(G)-1条),三、最小支撑树问题,定义 3 给图G=（V，E）的每一条边Vi，Vj赋予一个实 数Wij, 则称G 为 赋权图。 而

20、Wij称为边 Vi，Vj 的权。 所谓权，是关于边的数量指标，其意义视实际请况而定(如距离、时间、费用等)。 定义 4 如果T=（V，E）是赋权图G 的一个支撑树，称T的所有边的权数之和为支撑树T的权，记为w(T).即：,三、最小支撑树问题,如果图G的支撑树T*的权w(T*)是G的所有支撑树的权中最小的支撑树，则称T*为G的最小支撑树，简称最小树。,最小支撑树问题就是求出给定连通赋权图G的最小支撑树。,三、最小支撑树问题,寻找图的最小树的方法有：“避圈法”和“破圈法” 1、用避圈法寻找最小树，每次添加边时，都选权数最小的边。 2、 用破圈法寻找最小树，每次去掉边时，都选权数最大的边。,三、最小

21、支撑树问题,例8：某工厂内联结六个车间的道路网如图7-17(a)所示。已知每条道路的长，要求沿道路架设联结六个车间的电话线图，使电话线的总长最小。,解：用“避圈法”求解：,三、最小支撑树问题,解：用“破圈法”求解：,避圈法求作最小树： 先写下原图的所有顶点，然后逐步添加权数最小的边，使不与已添加 的边形成圈，直到不能添加为止。在添加的过程中，添加的边逐步形成若干子树，再逐步合并这些子树，最后得到最小树。,1,2,3,4,5,6,7,8,9,10,11,最短路问题,一、问题的提出 例10：已知如图7-12所示的单行线交通图，每条弧旁的数字表示通过这条单行线所需要花费的费用。现在某人要从v1出发，

22、通过这个交通网到v7去，求使总费用最小的旅行路线？,最短路问题,最短路问题：给定一个赋权的有向图，即给了一个有向图D=(V,A)， 对每一个弧a=(ai,vj)，相应地有权w(a)=wij， 又给定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)不一定相等。,最

23、短路算法,在权为非负的有向图中，求最短路的方法是Dijkstra于1959年提出的。,最短路算法,Dijkstra方法的基本思想： 从vs出发，逐步地向外探寻最短路。 执行过程中，与每个点对应，记录下一个数(称为这个点的标号)， 它或者表示从vs到该点最短路的权(称为P标号)， 或者表示从vs到该点最短路的权的上界(称为T标号)，,最短路算法,方法的每一步是去修改T标号， 并把某一个具T标号的点改变为具P标号的点， 从而使具P标号的顶点数多一个， 这样，至多经过P-1步， 就可求出从vs到各点的最短路。 P：某个点的P标号 T：某个点的T标号 Si：第i步时，具有P标号点的集合,最短路算法,为

24、了求出vs到各点的最短路，给每个点v以一个值，算法终止时，若（v）=m，则表示v的前一个点是vm，若（v）=M，则表示不含从vs到v的路。 P（vs）=0， （vs）=0， 对vvs，令T(vi)=+，(vi)=M,最短路算法,例10：求从v1到v8，总费用最小的旅行路线。,算法： 1、始点给予P标号，其他点给予T标号； 2、修改尽可能多T标号； 3、检查所有T 标号，将离始点最近的T标号改为P标号。 4、反复进行 2、3 两步，直到无法进行为止。,0,0,T(v4)=，M,，M,，M,，M,，M,，M,，M,，M,1，V1,3，V1,6，v1,11，v4,5，V3,6，V2,10，V5,9，

25、V5,12，V5,算法： 1、始点给予P标号，其他点给予T标号； 2、修改尽可能多T标号； 3、检查所有T 标号，将离始点最近的T 标号改为P标号。 4、反复进行 2、3 两步，直到无法进行为止。,P标号 永久标号,T标号 临时标号,本点号： 1 2 3 4 5 6 7 8 9 紧前点： 1 3 1 1 2 5 5 5 路 长： 0 5 3 1 6 10 9 12 ,Permanent,temporary,P(v1)=0,(v1)=0, T(vi)=+，(vi)=M(i=2,3,9),(v4)=1,最短路问题,v1,v2,v3,v4,v5,v6,v7,v8,v9,6,1,3,6,2,2,1,4

26、,4,2,6,2,3,3,10,10,0,0,1，V1,3，V1,5，V3,6，V2,9，V5,10，V5,12，V5,前页的算法也可简化如下：,本点号： 1 2 3 4 5 6 7 8 9 紧前点： 1 3 1 1 2 5 5 5 路 长： 0 5 3 1 6 10 9 12 ,v1,v2,v3,v4,v5,v6,v7,v8,v9,6,1,3,6,2,2,1,4,4,2,6,2,3,3,10,0,0,1，V1,3，V1,5，V3,6，V2,8，V5,10，V5,9，V5,11，V9,本点号： 1 2 3 4 5 6 7 8 9 紧前点： 1 3 1 1 2 5 5 9 5 路 长： 0 5

27、3 1 6 10 9 11 8,权数非负的无向 网络最短路问题,最短路算法,Dijkstra算法仅适合于所有的权wij=0的情形。如果当赋权有向图中存在有负权时，则该算法失效。 例如图7-20中，根据Dijkstra算法，可以得出从v1到v2最短路权是1，但是这显然不对，因为从v1到v2的最短路是（v1,v3,v2）,权是-1。,最短路算法,在赋权有向图中，存在负权时，寻求最短路的方法: 首先，设从任一点vi到任一点vj都有一条弧，如果在图 D 中，（vi,vj）不属于A,则添加弧(vi,vj),并且令wij=+。,最短路算法,显然，从vs到vj的最短路是从vs点出发，沿着这条路到某个点vi，

28、再沿弧(vi,vj)到点vj。从vs到vi的这条路必定是从vs到vi的最短路。 否则从vs到vj的这条路将不是最短路。 于是， 从vs到vj的距离d(vs,vj)满足以下条件，,最短路算法,这个关系式的解d(vs,v1)d(vs,vp)。 可利用如下的递推公式求解 开始时，,则d(k)(vs,vj),j=1p,就是从vs到各点vj的最短路径的权。,当计算到第K步时,对一切的j=1p,有,例12,例12 : 在如图7-21所示的赋权有向图中求从v1到各点的最短路。,图7.21,例12,解:利用上述递推公式， 将求解结果列出，如表7-1所示。 可以看出，当t=4时，有 d(t)(vs,vj)=d(

29、t-1)(vs,vj) j=18。 因此，表中的最后一列，就是从v1到v1,v2,.,v8的最短路权。,例12,为了求出从v1到各个点的最短路，一般采用反向追踪的方法：如果已知d(vi,vj),那么寻求一个点vk,使得d(vs,vk)+wkj=d(vs,vj),然后记录下(vk,vj).在看d(vs,vk),寻求一个点vi,使得d(vs,vi)+wij=d(vs,vk)依次类推，一直到达为止。这样，从vs到vj的最短路是（vs,vi,vk,vj）,例12,在本例中，有表7-1知，d(v1,v8)=6,由于)d(v1,v6)+w68=(-1)+7记录下v6。由于d(v1,v3)+w36=d(v1

30、,v6),j记录下v3。由于d(v1,v1)+w13=d(v1,v3),于是，从v1到v8的最短路是(v1,v3,v6,v8)。,最短路算法,结论 设C是赋权函数有向图D中的一个回路。 如果回路C的权w(C)是负数，那么称C是D中的一个负回路。,最短路算法,可以证明以下的结论： 1.如果赋权有向图D不含有负回路，那么从vs到任一点的最短路至多包含P-2个中间点，并且必可取为初等路。 2.如果赋权有向图D不含有负回路，那么上述递推算法至多经过P-1次迭代必收敛，可以求出从vs到各个点的最短路权。 3.如果上述算法经过P-1次迭代，还存在在着某个j，使得d(p)(vs,vj)d(p-1)(vs,v

31、j),那么D中含有负回路。这时，不存在从vs到vj的路（权无界）。,三、应用实例,例：设备更新问题 企业使用一台设备，每年年初需要决定继续使用或是更新，各年的购置费与使用不同年数设备的维修费见下二表；试制定5年内总费用最低的维修更新计划。,弧(vi .vj)表示 第 i 年年初购买 使用到第 j 年 年初为止,(v1,v3,v6) 或(v1,v4,v6) 值为53,三、应用实例,三、应用实例,例11：企业使用一台设备，每年年初需要决定继续使用或是更新，各年的购置费与使用不同年数设备的维修费见下二表；试制定5年内总费用最低的维修更新计划。 表7-1 单位：万元,还已知使用不同时间的设备所需要的维

32、修费用如表7-2所示： 表7-2 单位：万元,三、应用实例,弧(vi ,vj)表示第 i 年年初购买使用到第j年年初为止,第四节 网络最大流问题,在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。,第四节 网络最大流问题,7-23是联结某产品产地vs和销地vt的交通图， 弧(vi,vj)代表从vi到vj的运输线， 产品经过交通图从v1输送到v6， 制定一个运输方案，使从v1运到v6的产品的数量最多。,第四节 网络最大流问题,图7-24,

33、每条弧旁的数字表示每条运输线上的运输量。 这个方案使8个单位的产品从v1运到v6。 从vs运到vt的最大输送量是多少？,一、基本概念与基本原理,一、网络与流 定义6 有向图D=(V,A),在V中指定了一点，称为发点(记为vs),另一点称为收点(记为vt),其余的点称为中间点。,一、网络与流,对于每一个弧(vi,vj)A，对应有一个c(vi,vj)0(简写为cij)，称为弧的容量。 称这样的有向图D叫做一个网络，记作D=(V,A,C)。 网络上的流，是指定义在弧集合A上的一个函数f=f(vi,vj), 并称f (vi,vj)为弧(vi,vj)的流量，有时简记作fij。,一、网络与流,弧上的运输量

34、就是弧上的流量。如f12=5， f24=2 f13=3， f34=1,二、可行流与最大流,运输问题对流的两个要求 1、每个弧上的流量不能超过该弧的最大通过能力（弧的容量）。 2、中间点的流量为0。,二、可行流与最大流,因为对于每个点，运出这点的产品总量与运进这点的产品总量之差，是这点的净输出量，简称为是这一点的流量； 由于中间点只起转运作用，所以中间点的流量必为0。 发点的净输出量和收点的净输入量必相等，也是这个方案的总输出量。,二、可行流与最大流,定义7 满足下述条件的流f称为可行流： (1)容量限制条件：对每一弧(vi,vj) A 0fijcij 2）平衡条件： 对于中间点：流出量=流入量

35、，即对于每一个i (is,t)，有,二、可行流与最大流,对于收点 ，记,可行流的流量（发点的净输出量或收点的净输入量）,对于发点vs ，记,二、可行流与最大流,V(f):可行流的流量,即发点的净输出量（或收点的净输入量）。 可行流总是存在的。 例如令所有弧上的流量fij=0，就得到一个可行流（称为零流），其流量v(f) =0。,二、可行流与最大流,最大流问题就是求一个流fij ，使其流量 v(f)达到最大，并且满足:,二、可行流与最大流,最大流问题是一个特殊的线性规划问题。 即求一组fij ，在满足条件和下使v(f)达到极大。 我们将会看到利用图的特点，解决这个问题的方法较直线性规划的一般方法

36、要简便和直观的多。,三、增广链,若给定一个可行流f=fij， 把网络中使fij=cij的弧称为饱和弧， 使fij0的称为非零流弧。,三、增广链,若是网络中联结发点vs和收点vt的一条链， 定义链的方向是从vs 到vt ，则链上的弧被分为两类： 一类是：弧的方向与链的方向一致，我们称此类弧为前向弧，所有前向弧的集合记为+ 。 另一类是：弧的方向与链的方向相反，我们称此类弧为后向弧，所有后向弧的集合记为-。,三、增广链,三、增广链,增广链:设f是一个可行流， 是从vs到vt的一条链，若 满足下列条件：则称是关于f的一条增广链。 (1)在弧(vi,vj)+上，0fijcij，即+中的每一条弧都是非饱

37、和弧； (2)在弧(vi,vj)- 上， 0fijcij即-中的每一条弧都是非零流弧。,链=(vs,v2,v3,v1,v4,vt)是一条增广链。 因为+上的弧均非饱和，如(vs,v2)+,fs2=10。显然这样的增广链不止一条。,三、增广链,如果一个网络上有增广链，则前向弧上的流量可适当增大，后向弧上的流量可适当减小， 从而可使网络上的流量有所增大， 即凡有增广链的网络流皆非最大流。 这对求解网络最大流问题，是非常关键的。,4.截集与截量,定义9 设一个网络D=（V，A，C）。 如果点集V被分为两个非空集合 ， 发点vsV1,收点 , 那么将弧集 叫做是（分离vs和vt的）截集。,4.截集与截

38、量,4.截集与截量,如果网络上的一个可行流f*和网络中的一个截集 ， 若满足条件 , 则f*一定是D上的最大流， 而 一定是D的所有的截集中，容量最小的一个，即最小截集。,4.截集与截量,定理8 网络中的一个可行流f*是最大流的充分必要条件是，不存在关于f*的增广链。,证 先证必要性。用反证法。 若f*是最大流，假设D中存在着关于f*的增广链，令,4.截集与截量,4.截集与截量,再证充分性：即证明设D中不存在关于f*的增广链，f*是最大流。 用下面的方法定义V1*：令 vsV1*， 若viV1*，且有f*ij0，则令vjV1* 。 因为不存在着关于f*的增广链，故,4.截集与截量,于是得到一个

39、截集 。显然有,所以 ，于是f*必是最大流。 定理得证。 由上述证明中可见，若f*是最大流，则网络必定存在一个截集 ，使,前向弧,后向弧,4.截集与截量,定理9：（最大流量最小截量定理） 对于任意给定的网络D=(V,A,C)，从出发点vs到收点vt的最大流的流量必等于分离vs和vt的最小截集的容量。,vs,vt,v1,v3,v2,v4,( 3,3 ),( 4,2 ),( 5,1 ),( 2,2 ),( 1,1 ),( 1,1 ),( 5,3 ),( 3,1 ),( 3,1 ),( c ij,fij ),截集为： （Vs ，V2）,(V1,V3)。 割容量为：3+2=5,截集为： （V2 ，V4

40、）,(V1,V3)。 割容量为：4+2=6,截集为： （V4 ，Vt）,(V1,V3)。 割容量为：5+2=7,网络最大流的流量=容量最小的割容量,例7.11,若V1=vs，截集（vs，v1），（vs，v2） 容量cs1+cs2=4+2=6,4.截集与截量,定理8提供了一个寻求网络系统最大流的方法：如果网络D中有一个可行流f，只要判断网络是否存在关于可行流f的增广链 。 如果没有增广链，那么f一定是最大流。 如有增广链，那么可以按照定理8，不断改进和增大可行流f的流量， 最终可以得到网络中的一个最大流。,4.2寻求最大流的标号法,从网络中的一个可行流f出发（如果网络中没有给定f，可以设f是零流

41、）， 运用标号法，经过标号过程和调整过程， 可以得到网络中的一个最大流。,4.2寻求最大流的标号法,1.标号过程 在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点， 每个标号点的标号包含两部分： 第一个标号表明它的标号是从哪一点得到的，以便找出增广链； 第二个标号是为确定增广链的调整量用的。,4.2寻求最大流的标号法,标号过程开始，总先给vs标上(0,+)， 这时vs是标号而未检查的点，其余都是未标号点。 一般地，取一个标号而未检查的点vi，对一切未标号点vj： (1) 在弧 (vi，vj)上，fijcij，则给vj标号(vi，l(vj) 。这里1(vj)=mi

42、n1(vi)，cij-fij 。这时点vj成为标号而未检查的点。,4.2寻求最大流的标号法,(2)若在弧(vj，vi)上，fji0，则给vj标号(-vi，1(vj) 。这里1(vj)=min1(vi)，fji 。这时点vj成为标号而未检查的点。 于是vi成为标号而已检查过的点，重复上述步骤，一旦vt 被标上号，表明得到一条从vs到vt的增广链 ，转入调整过程。 若所有标号都是已检查过，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。,4.2寻求最大流的标号法,2.调整过程 首先按vt及其它点的第一个标号，利用“反向追踪”的办法，找出增广链。 1、设vt的第一个标号为vk（或-vk

43、），则弧 (vk，vt)（或相应地(vt，vk) ）是上的弧。 2、检查vk的第一个标号，若为vi （或-vi ），则找出 (vi,vk)（或相应地 (vk,vi) ）。 3、再检查 vk 的第一个标号，依此下去，直到vs为止。这时被找出的弧就构成了增广链。,4.2寻求最大流的标号法,令调整量是1(vt)，即 vt的第二个标号。 去掉所有的标号，对新的可行流 f=fij，重新进入标号过程。,4.2寻求最大流的标号法,(Cij,fij),求图7-25的网络最大流，弧旁的权数表示（cij,fij）。,4.2寻求最大流的标号法,解.用标号法。 1.标号过程。 （1）首先给vs标号（0，+） （2）检

44、查vs:在弧(vs,v2)上,fs2=cs3=3,不具备标号条件。 在弧(vs，v1)上，fs1=1cs1=5, 故给v1标号(vs， l(v1), 其中l(v1)=minl(vs),(cs1-fs1)=min+,5-1=4。,4.2寻求最大流的标号法,（3）检查v1:在弧（v1,v3）上,f13=c13=2,不具备标号条件。 在弧(v2,v1)上,f21=10, 故给v2标号（-v1, l(v2)）, 其中l(v2)=minl(v1),f21=min4,1=1.,4.2寻求最大流的标号法,（4）检查v2:在弧（v2,v4）上，f24=30, 故给v3标号（-v2，l(v3), 其中l(v3)

45、=minl(v2),f32=min1,1=1。,4.2寻求最大流的标号法,（5）在v3,v4中任意选一个，比如v3,在弧（v3,vt）上，f3t=1c3t=2, 故给vt标号(v3,l(vt), 其中l(vt)=minl(v3),(c3t-f3t)=min1,1=1。 因为vt被标上号，根据标号法，转入调整过程。,4.2寻求最大流的标号法,2.调整过程 从vt开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从vs到vt的增广链，如图7-26中双箭线所示。 不难看出, +=(vs,v1),(v3,vt), -=(v2,v1),(v3,v2),4.2寻求最大流的标号法,（调整量 是l(vt

46、)） 取=1，在上调整f，得到 fs1+=1+1=2 在+上 f3t+=1+1=2 在+上 f*= f21-=1-1=0 在-上 f32-=1-1=0 在-上 其他的不变,4.2寻求最大流的标号法,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),图7-26,4.2寻求最大流的标号法,调整后的可行流f*，如图7-27所示，再对这个可行流重新进行标号过程，寻找增广链。,图7-27,4.2寻求最大流的标号法

47、,首先给vs标号（0，+）， 检查vs,给v1标号（vs,3）。 检查v1,在弧（v1,v3）上，f13=c13,弧（v2,v1）上，f21=0,均不符合条件。 因此标号过程无法进行下去，不存在从VS到Vt的增广链，算法结束。,4.2寻求最大流的标号法,4.2寻求最大流的标号法,由上述可见，用标号法找增广链以求最大流的结果，同时也得到一个最小截集。 最小截集的容量的大小影响总的运输量的提高。 因此，为提高总的运输量，必须首先考虑增大最小截集中各弧的容量，提高它们的通过能力。反之，一旦最小截集中弧的通过能力降低，必然会使得运输量减少。,举例,举例 用标号法求如图所示网络最大流。弧旁的数是(cij

48、，fij)。,(0,+),(vs，3),(v2，3),(v3，1),举例,解 :对图中各顶点进行标号。 1、首先给vs 标(0,+) 2、检察vs，在弧(vs，v1)上,fs1=cs1=3，不满足标号条件。 弧(vs,v2)上，fs1=1,cs2=4，fs2cs2， 则v2的标号为(vs，1(v2)， 其中， 1(v2)=min1(vs)，(cs2-fs2)=min+,4-1=3。 3、检察v2，在弧(v2，v3)上,f23=2，c23=5， f23c23， 则v3的标号为(v2，1(v3)， 其中， 1(v3)=min1(v2)，(c23-f23)=min3,5-2=3。,举例,4、检察v3

49、，在弧(v3，v4)上,f34=0，c34=2， f34c34， 则v4的标号为(v3，1(v4)， 其中， 1(v4)=min1(v3)，(c34-f34)=min3,2-0=2。 5、在弧(v3，vt)上,f3t=1，c3t=2， f3tc3t， 则vt的标号为(v3，1(vt)， 其中， 1(vt)=min1(v3)，(c3t-f3t)=min3,2-1=1。 因vt有了标号，故转入调整过程。,举例,按点的第一个标号找到一条增广链。,(0,+),(vs,3),(v2,3),(v3,1),(v3,2),举例,按点的第一个标号找到一条增广链， 由图可知：+=(vs,v2), (v2,v3),

50、 (v3,vt) 令调整量是1(vt)，即vt的第二个标号。即=1。在上调整f。 +上：fs2+ =1+1=2 f23+ =3+1=4 f3t+ =1+1=2 其余的fij不变。,举例,调整后的可行流，对这个可行流进入标号过程，寻找增广链。,举例,（一）标号过程。 1、首先给vs 标(0,+)，检察vs，给v2标以(vs，2)。 2、检查v2，弧(v2，v3)上,f23=3，c23=5， f23c23， 则v3的标号为(v2，1(v3)， 其中， 1(v3)=min1(v2)，(c23-f23)=min2,5-3=2。 3、检查v3，在弧(v3，v4)上,f34=0，c34=2， f34c34

51、， 则v4的标号为(v3，1(v4)， 其中， 1(v4)=min1(v3)，(c34-f34)=min2,2-0=2。,举例,4、检查v4，在弧(v4，vt)上, f4t=3，c4t=5， f4tc4t， 则vt的标号为(v4，1(vt)，其中， 1(vt)=min1(v4)，(c4t-f4t)=min2,5-3=2。 因vt有了标号，故转入调整过程。,举例,按点的第一个标号又找到一条增广链。,(0,+),(vs,2),(v2,2),(v4,2),(v3,2),(-v1,1),举例,按点的第一个标号找到一条增广链， 由图可知：+=(vs,v2), (v2,v3), (v3,v4) , (v4

52、,vt) 令调整量是1(vt)，即 vt的第二个标号。 按=2在上调整f。 +上：fs2+ =2+2=4 f23+ =3+2=5 f34+ =0+2=2 f4t+ =3+2=5 其余的fij不变。,举例,调整后的可行流，对这个可行流进入标号过程，寻找增广链。,再次给vs标(0,+)，检查vs，弧 (vs，v1)上。fs1=cs1=3,弧 (vs，v2)上，fs2=cs2=4，均不符合条件，标号过程无法继续下去，算法结束。 这时的可行流即为所求的最大流， 最大流量为v(f)=fs1+fs2=f3t+f4t=7。,举例,举例,与此同时可找到一个最小截集 。V1为标号点集合， 为未标号点集合，弧集合

53、 即为最小截集或最小割。 上例中，V1=vs， =v1,v2,v3,v4,vt， 于是 =(vs,v1), (vs,v2)是最小截集，它的容量必也是7。,第五节 最小费用最大流问题,给网络D=（V，A，C），每一个弧(vi,vj)A， 容量为cij，单位容量的费用b ij ( v i ， v j)0（简记为bij）， 最小费用最大流问题就是要求一个最大流f，使总的输送费用,第五节 最小费用最大流问题,从上节可知，寻求最大流的方法是从某个可行流出发，找到关于这个流的一条增广链，沿着调整f，再寻找新的可行流的增广链，如此反复直至最大流。若要寻找最小费用最大流，可考虑： 当沿着一条关于可行流f的增广

54、链，以=1调整f，得到新的可行流f时， b(f)比b(f)增加多少？,第五节 最小费用最大流问题,第五节 最小费用最大流问题,可以证明，若f是流量为v(f)的所有可行流中费用最小的，而是关于f的所有增广链中费用最小的增广链， 则沿去调整f，得到的可行流f，就是流量为v(f)的所有可行流中的最小费用流。 这样，当f是最大流时，它也就是我们所要求的最小费用最大流。,第五节 最小费用最大流问题,由于bij0，所以f=0必是流量为0的最小费用流。 从f=0开始，寻求关于f的最小费用增广链。 为此，构造一个赋权有向图W(f)， 它的顶点是原网络D的顶点，而把D中的每一条弧(vi,vj)变成两个相反方向的

55、弧(vi,vj) 和(vj,vi) ，定义W(f)中弧的权wij为：,第五节 最小费用最大流问题,并且将权为+的弧从w(f)中略去。 即当 0 fij cij 时，成为2条方向相反，权绝对值相等的弧,否则不变。,第五节 最小费用最大流问题,在网络D中寻求关于f的最小费用增广链就等价于在赋权有向图W(f)中， 寻求从vs到vt的最短路。,第五节 最小费用最大流问题,调整量为：,得到新的可行流f(k)，再对f(k)重复上述步骤。,第五节 最小费用最大流问题,例15:求图7-28 所示网络中的最小费用最大流，弧旁的权是（bij,cij）。,第五节 最小费用最大流问题,算法： 取f(0)=0，一般若在

56、第k-1步得到最小费用流f(k-1)， 则构造赋权有向图W(f(k-1)， 在W(f(k-1)中，寻求从vs到vt的最短路。 若不存在最短路 (即最短路权是+) ， 则f(k-1)就是最小费用最大流； 若存在最短路 ， 则在原网络D中得到相应的增广链 ， 在增广链 上对f(k-1)进行调整。,4,vs,vt,v1,v2,v3,4,1,2,3,1,6,2,vs,vt,v1,v2,v3,按最短路根据弧的容量调整运量得流量图下图.,W(f (0),0,0,0,0,vs,vt,v1,v2,v3,(a ),( b ),f (1),v(f (1 )=5,1,-2,3,1,6,2,vs,vt,v1,v2,v

57、3,-1,-1,W(f (1),(c ),作相应赋权有向图并求出最短路,以0流 f(0)=0为初始流构造赋权有向图并算得最短路如右,0,0,0,5,5,5,(4,10),(1,8),(2,5),(3,10),(1 ,7),(6,2),(2,4),(bij,cij),（运价，容量）,1,4,0,5,5,0,5,0,0,vs,vt,v1,v2,v3,( b ),f (1),v(f (1 )=5,1,3,1,6,2,vs,vt,v1,v2,v3,-1,W(f (1),(c ),作相应赋权有向图并求出最短路,0,5,5,0,5,0,0,vs,vt,v1,v2,v3,( d ),4,3,-1,6,2,v

58、s,vt,v1,v2,v3,-1,W(f (2),(e ),-4,沿最短路调整,得左下图,作相应赋权有向图并求出最短路,bi j ,若 f i j c i j ，,+,若 f i j =c i j .,- b j i ,若 f i j 0,+, 若 f i j = 0,w i j =,w j i =,-1,2,7,-2,-2,1,2,5,5,0,7,0,0,vs,vt,v1,vs,v2,v3,( d ),4,3,-1,6,2,vs,vt,v1,v2,v3,-1,W(f (2),(e ),-4,作相应赋权有向图并求出最短路,4,-2,3,-1,6,2,vs,vt,v2,v3,-1,W(f (3),(g ),-4,-2,-3,2,5,5,0,7,0,0,vs,vt,v1,v2,v3,( f ),f ( 3),v(f ( 3 ) )=10,作相应赋权有向图并求出最短路,沿最