1、图论模型,图论模型,图论基本概念 最短路径算法 最小生成树算法 遍历性问题 二分图与匹配,2,网络流问题 关键路径问题 系统监控模型 着色模型,1、图论的基本概念,问题1(哥尼斯堡七桥问题):能否从任一陆地出发通过每座桥恰好一次而回到出发点？,3,4,欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地.,5,问题2(哈密顿环球旅行问题):十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？,欧拉问题是“边遍历”，哈密尔顿问题是“点遍历”,6,问题3(四色问题):对任何一张地图进行着色，两个
2、共同边界的国家染不同的颜色，则只需要四种颜色就够了.,问题4(关键路径问题):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, 都要包括许多工序.这些工序相互约束,只有在某些工序完成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目, 影响工程进度的要害工序是哪几个？,图的定义,图论中的“图”并不是通常意义下的几何图形或物体的形状图, 而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.,定义1 一个有序二
3、元组(V, E ) 称为一个图, 记为G = (V, E ), 其中, V称为G的顶点集, V, 其元素称为顶点或结点, 简称点; E称为G的边集, 其元素称为边, 它联结V 中的两个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边. 如果V = v1, v2, , vn是有限非空点集, 则称G为有限图或n阶图.,8,如果E的每一条边都是无向边, 则称G为无向图(如图1); 如果E的每一条边都是有向边, 则称G为有向图(如图2); 否则, 称G为混合图.,图1 图2,并且常记:,V = v1, v2, , vn, |V | = n ; E = e1, e2, , em(ek
4、=vivj ) , |E | = m.,称点vi , vj为边vivj的端点. 在有向图中, 称点vi , vj分别为边vivj的始点和终点. 该图称为(n,m)图,9,对于一个图G = (V, E ), 人们常用图形来表示它, 称其为图解. 凡是有向边, 在图解上都用箭头标明其方向.,例如, 设V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 则G = (V, E ) 是一个有4个顶点和6条边的图, G的图解如下图所示.,10,一个图会有许多外形不同的图解, 下面两个图表示同一个图G = (V, E )的图
5、解.这两个图互为同构图,今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图.,11,有边联结的两个点称为相邻的点, 有一个公共端点的边称为相邻边. 边和它的端点称为互相关联. 常用d(v)表示图G中与顶点v关联的边的数目, d(v)称为顶点v的度数. 对于有向图,还有出度和入度之分. 用N(v)表示图G中所有与顶点v相邻的顶点的集合.,d(v1)= d(v3)= d(v4)=4, d(v2)=2,dout(v1)= dout (v3)= dout (v4)=2, dout(v2)=1 din(v1)= din(v3)= din(v4)=2, din(v2)=1,12,握手
6、定理,握手定理：无向图中，所有结点的度数之和等于2m。右图：推论1：无向图中必有偶数个度数为奇数的结点。 推论2：有向图中所有结点的出度之和等于入度之和。,d(v1)= d(v3)= d(v4)=4, d(v2)=2,我们今后只讨论有限简单图：,(1) 顶点个数是有限的;(2) 任意一条边有且只有两个不同的点与它相互关联;(3) 若是无向图, 则任意两个顶点最多只有一条边与之相联结;(4) 若是有向图, 则任意两个顶点最多只有两条边与之相联结. 当两个顶点有两条边与之相联结时，这两条边的方向相反.如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.,14,定义2 若将图G的每
7、一条边e都对应一个实数F (e), 则称F (e)为该边的权, 并称图G为赋权图(网络), 记为G = (V, E , F ).,定义3 任意两点均有通路的图称为连通图.定义4 连通而无圈的图称为树, 常用T表示树.,常用的图,给定图G= 和 G = 是两个图，如果有 V V 和 E E,则称图G是图 G 的子图。若V =V 称图G是图 G 的生成子图； 若将图G的每一条边e都对应一个实数F(e)，则称F(e)为该边的权，并称图G为赋权图(网络), 记为G = 。 任意两点均有通路的图称为连通图。 连通而无圈的图称为树，常用T=表示树。 若图G是图 G 的生成子图，且G又是一棵树，则称G是图G
8、 的生成树。,例 Ramsey问题,问题：任何6个人的聚会，其中总会有3个互相认识或3人互相不认识。 图论模型：用红、蓝两种颜色对6个顶点的完全图K6的边进行任意着色，则不论如何着色必然都存在一个红色的K3或一个蓝色的K3 。对应关系：每个人即为一个结点；人与人之间的关系即为一条边,例 Ramsey问题,图论证明： 用红、蓝两种颜色对K6的边进行着色， K6的任意一个顶点均有5条边与之相连接，这5条边必有3条边的颜色是相同的，不妨设为蓝色（如图） 与这3条边相关联的另外3个节点之间的3条边，若都为红色，则形成红色的K3； 若另外3个节点之间的3条边有一条为蓝色，则与上面的蓝色边形成蓝色的K3；
9、 因此必然存在一个红色的K3或一个蓝色的K3 。,例 Ramsey问题,Ramsey数：R（3,3）=6；R（3,4）=9；。,18,例 过河问题,问题：一摆渡人欲将一只狼、一头羊、一篮菜从河西渡过河到河东。由于船小，一次只能带一物过河，并且狼与羊，羊与菜不能独处，给出渡河方法。 这里显然不能用一个节点表示一个物体。一个物体可能在河东，也可能在河西，也可能在船上，状态表示不清楚。 另外，问题也可以分成几个小问题，如：问题是否能解？有几种不同的解法？最快的解决方案是什么？,例 过河问题,解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1，否则取0)，共有24 =16 种
10、状态。在河东岸的状态类似记作。 由题设，状态(0,1,1,0)，(0,0,1,1)，(0,1,1,1)是不允许的； 其对应状态：(1,0,0,1)， (1,1,0,0)，(1,0,0,0)也是不允许的。 以可允许的10个状态向量作为顶点，将可能互相转移的状态用边连接起来构成一个图。 利用图论的相关知识即可回答原问题。,例 过河问题,(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0) (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1),(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,
11、0,0,1) (0,0,0,0) (1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1) 河西=(人,狼,羊,菜) 河东=(人,狼,羊,菜),将10个顶点分别记为A1, A2, , A10 ,从图中易得到两条路： A1 A6 A3 A7 A2 A8 A5 A10; A1 A6 A3 A9 A4 A8 A5 A10.,问题的转换： 过河问题是否能解？ 即：图中A1到A10是否连通？ 有几种不同的解法？ 即： A1到A10之间有多少条不同的路径？ 最快的解决方案是什么？ 即： A1到A10最短路径有哪些？,图的矩阵表示, 邻接矩阵：邻接矩阵表示了点与点之
12、间的邻接关系.一个n阶图G的邻接矩阵A = (aij )nn , 其中,22,23,无向图G的邻接矩阵A是一个对称矩阵., 权矩阵 一个n阶赋权图G = (V, E, F)的权矩阵A = (aij ) nn , 其中,有限简单图基本上可用权矩阵来表示.,24,无向图G的权矩阵A是一个对称矩阵.,25, 关联矩阵：一个有m条边的n阶有向图G的关联矩阵A = (aij )nm , 其中,若vi是ej的始点; 若vi是ej的终点; 若vi与ej不关联.,有向图的关联矩阵每列的元素中有且仅有一个1,有且仅有一个 - 1.,26,一个有m条边的n阶无向图G的关联矩阵A = (aij )nm , 其中,若
13、vi与ej关联; 若vi与ej不关联.,无向图的关联矩阵每列的元素中有且仅有两个1.,2、最短路径算法,定义1 设P(u, v) 是赋权图G = (V, E , F) 中从点u到v的路径, 用E(P) 表示路径P(u, v)中全部边的集合, 记,则称F (P)为路径P(u, v) 的权或长度(距离).,定义2 若P0 (u, v) 是G 中连接u, v的路径, 且对任意在G 中连接u, v的路径P (u, v)都有 F (P0)F(P), 则称P0 (u, v) 是G 中连接u, v的最短路.,28,重要性质：,若v0 v1 vm 是图G中从v0到vm的最短路, 则1km, v0v1 vk 必
14、为G中从v0到vk的最短路.,即：最短路是一条路，且最短路的任一段也是最短路.求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.下面分别介绍两种算法的基本过程.,Dijkstra算法,指标（a为起点） 设T为V的子集，P=V-T且aT，对所有tT， 设 l(t)表示从a到t的所有通路中距离最短的一条的长度， 且这条路径中不包含T中其他的结点，则称l(t)为t关于 集合P的指标，若不存在这样的路径，这记l(t)= 注：l(t)不一定是从a到t的最短路径，因为最短路径中可能包含T中其他的
15、节点。 定理1 若t是T中关于P由最小指标的结点，则l(t)是a和t之间的最短距离。 定理2 设 T为V的子集，P=V-T，设 (1)对P中的任一点p,存在一条从a到p的最短路径,这条路径仅有P中的点构成, (2)对于每一点t,它关于P的指标为l(t),令x为最小指标所在的点, 即: (3)令P=P Ux,T=T-x,l(t)表示T中结点t关于P的指标,则,29,Dijkstra算法（求a点到其他点的最短路径）,1、初始化，P=a，T=V-a，对每个结点t计算指标 l(t)=w(a,t) 2、设x为T中关于P有最小指标的点, 即:l(x)=min(l(t) (tT), 3、若T=,则算法结束;
16、 否则,令P=P Ux,T=T-x 按照公式l(t)=minl(t),l(x)+w(x,t), 计算T中每一个结点t关于P的指标. 4、P代替P,T代替T,重复步骤2,3 （ 其中：w(x,y)为图的权矩阵）,30,改进Dijkstra算法（求a点到其他点的最短路径）,1、初始化，P=a，T=V-a，对每个结点t计算指标 l(t)=w(a,t) ,pro(t)=a; 2、设x为T中关于P有最小指标的点, 即:l(x)=min(l(t) (tT); 3、若T=,则算法结束; 否则,令P=P Ux,T=T-x 按照公式l(t)=minl(t),l(x)+w(x,t), 计算T中每一个结点t关于P的
17、指标. 若 l(x)+w(x,t) l(t), pro(t)=x; 4、P代替P,T代替T,重复步骤2,3 （ 其中：w(x,y)为图的权矩阵）,31,例 求下图中A点到其他点的最短路.,32,Floyd算法（求任意两点的最短路径）,设A = (aij )nn为赋权图G = (V, E, F)的权矩阵, dij表示从vi到vj点的距离, rij表示从vi到vj点的最短路中前一个点的编号. 赋初值. 对所有i, j, dij = aij, rij = j. k = 1. 转向. 更新dij , rij . 对所有i, j, 若dik + dk jdij , 则令dij = dik + dkj ,
18、 rij = k, 转向; 终止判断. 若k = n终止; 否则令k = k + 1, 转向.最短路线可由rij得到.,例 求下图中任意两点间的最短路.,34,例 设备更新问题,某企业每年年初,都要作出决定,如果继续使用旧设备,要付维修费；若购买一台新设备,要付购买费.试制定一个5年更新计划,使总支出最少.已知设备在每年年初的购买费分别为11,11, 12,12,13. 使用不同时间设备所需的维修费分别为5,6,8,11,18.解 设bi 表示设备在第i 年年初的购买费,ci 表示设备使用i 年后的维修费, V=v1, v2, , v6,点vi表示第i 年年初购进一台新设备,虚设一个点v6表示
19、第5年年底. E =vivj | 1ij6,每条边vivj表一台设备，从第i年年初购买使用到第j年年初报废.,36,这样上述设备更新问题就变为：在有向赋权图G = (V, E, F )(图解如下)中求v1到v6的最短路问题.,37,由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5 ,v1到v6 ,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2 ,v2v3 ,v3v4 ,v4v5 ,v5v6 五条连线后得到,从上图中容易得到v1到v6只有两条路：,v1v3v6和v1v4v6.,而这两条路都是v1到v6的最短路.,3、最小生成树,由树的定义不难知道, 任
20、意一个连通的(n,m)图G适当去掉m - n +1条边后, 都可以变成树, 这棵树称为图G的生成树.,设T是图G的一棵生成树, 用F(T)表示树T中所有边的权数之和, F(T)称为树T的权.一个连通图G的生成树一般不止一棵, 图G的所有生成树中权数最小的生成树称为图G的最小生成树-Minimum-cost Spanning Tree (MST).求最小生成树问题有很广泛的实际应用. 例如, 把n个乡镇用高压电缆连接起来建立一个电网, 使所用的电缆长度之和最短, 即费用最小, 就是一个求最小生成树问题.,Kruskal算法,39,从未选入树中的边中选取权重最小的且不构成回路的边加入到树中.（判断
21、回路比较麻烦）,算法过程： 1.将各边按权值从小到大进行排序 2.找出权值最小且不与已加入最小生成树集合的边构成回路的边。若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。 3.递归重复步骤1，直到找出n-1条边为止，得到最小生成树。,时间复杂度只和边有关，可以证明其时间复杂度为O(mlogm),求最小生成树,40,Prim算法,41,把结点分成两个集合，已加入树中的(P)和未加入树中的(Q)，然后每次选择一个点在P中一个点在Q中的权重最小的边，加入树中，并把相应点加入P中。,类似地,可定义连通图G 的最大生成树.,算法过程：1：初始化：任取一个节点u加入生
22、成树,P=u0, Q=V-u0, 生成树的边集TE=。2：在所有uP,vQ的边(u,v) （称为可选边集）中，找一条权重最小的边(u1,v1)，将此边加进集合TE中，并将v加入P中。同时对与v关联的边，若另一个端点已经在P中，则从可选边集中删除，否则加入可选边集。3：如果P=V，则算法结束；否则重复步骤2。我们可以算出当U=V时，步骤2共执行了n1次，TE中也增加了n1条边，这n1条边就是需要求出的最小生成树的边。,例 选址问题,现准备在 n 个居民点v1, v2, , vn中设置一银行.问设在哪个点,可使最大服务距离最小? 若设置两个银行,问设在哪两个点?模型假设 假设各个居民点都有条件设置
23、银行,并有路相连,且路长已知.模型建立与求解 用Floyd算法求出任意两个居民点vi , vj 之间的最短距离,并用dij 表示., 设置一个银行,银行设在 vi 点的最大服务距离为,43,求k,使,即若设置一个银行,则银行设在 vk 点,可使最大服务距离最小. 设置两个银行,假设银行设在vs , vt 点使最大服务距离最小.,记,则s,t 满足：,进一步,若设置多个银行呢？,4、遍历性问题,一、欧拉图 G=(V,E)为一连通无向图 经过G中每条边至少一次的回路称为巡回； 经过G中每条边正好一次的巡回称为欧拉巡回； 存在欧拉巡回的图称为欧拉图。 二、中国邮递员问题（CPPchinese pos
24、tman problem） 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？ 这一问题是我国管梅谷教授1962年首先提出，国际上称之为中国邮递员问题。,44,解法： 若本身就是欧拉图，则直接可以找到一条欧拉巡回就是本问题的解。 若不是欧拉图，必定有偶数个奇度数结点，在这些奇度数点之间添加一些边，使之变成欧拉图，再找出一个欧拉巡回。 具体解法：Fleury算法+Edmonds最小对集算法,45,三、哈密尔顿图 G=(V,E)为一连通无向图 经过G中每点一次且正好一次的路径称为哈密尔顿路径； 经过G中每点一次且正好一
25、次的回路称为哈密尔顿回路； 存在哈密尔顿回路的图称为哈密尔顿图。 四、旅行商问题（TSPTraveling Salesman Problem） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线？ 即：从驻地出发，经过每个城市恰好一次，最后返回驻地（最小哈密尔顿回路） 对于n个节点的旅行商问题，n个节点的任意一个全排列都是问题的一个可能解（假设任意两个点之间都有边）。G个节点的全排列有(n-1)!个，因此间题归结为在(n-1)!个回路中选取最小回路。 TSP问题的解法属于NP完全问题，一般只研究其近似解法,46,最邻近算法 (1) 选取任意一个点作为起始点,找出与该点相关
26、联的权重最小的边,形成一条初始路径. (2) 找出与最新加入到路径中的点相关联的权重最小的边加入到路径中,且要求不再路径中产生回路. (3) 重复(2)直到所有的结点都加入到路径中. (4) 将起点和最后加入的结点之间的边加入到路径中,形成Hamilton回路. 其他数值算法： 人工神经元方法， 遗传算法等等,47,5、二分图与匹配,定义1 设X,Y 都是非空有限集,且XY = , E xy|xX,yY, 称G =(X, Y, E)为二部图.二部图可认为是有限简单无向图.如果X中的每个点都与Y中的每个点邻接,则称G =(X, Y, E)为完备二部图.若F：ER +,则称G =(X, Y, E,
27、 F )为二部赋权图.二部赋权图的权矩阵一般记作 A=(aij )|X|Y | , 其中aij = F (xi yj ).,49,定义2 设G =(X, Y, E)为二部图,且M E.若M中任意两条边在G中均不邻接,则称M是二部图G的一个匹配.,定义3 设M是二部图G的一个匹配,如果G的每一个点都是M中边的顶点,则称M是二部图G的完美匹配；如果G中没有另外的匹配M0 ,使|M0|M|,则称M是二部图G的最大匹配.在二部赋权图G =(X, Y, E, F )中,权数最大的最大匹配M称为二部赋权图G的最佳匹配.显然,每个完美匹配都是最大匹配,反之不一定成立.,工作安排问题之一,50,给n个工作人员
28、x1, x2, , xn安排n项工作y1, y2, , yn. n个工作人员中每个人能胜任一项或几项工作, 但并不是所有工作人员都能从事任何一项工作. 比如x1能做y1, y2工作, x2能做y2, y3, y4工作等. 这样便提出一个问题, 对所有的工作人员能不能都分配一件他所能胜任的工作？,我们构造一个二部图G = ( X, Y, E ), 这里X = x1, x2, , xn,Y = y1, y2, , yn, 并且当且仅当工作人员xi胜任工作yj时, xi与yj才相邻. 于是, 问题转化为求二部图的一个完美匹配. 因为 |X|=|Y|, 所以完美匹配即为最大匹配.,51,求二部图G =
29、 ( X, Y, E )的最大匹配算法(匈牙利算法,交替链算法)迭代步骤:,从G的任意匹配M开始. 将X中M的所有非饱和点都给以标号0和标记*, 转向.M的非饱和点即非M的某条边的顶点. 若X中所有有标号的点都已去掉了标记*, 则M是G的最大匹配. 否则任取X中一个既有标号又有标记*的点xi , 去掉xi的标记*, 转向. 找出在G中所有与xi邻接的点yj , 若所有这样的yj都已有标号, 则转向, 否则转向.,52, 对与xi邻接且尚未给标号的yj都给定标号i.,若所有的 yj 都是M的饱和点,则转向,否则逆向返回. 即由其中M的任一个非饱和点 yj 的标号i 找到xi ,再由 xi 的标号
30、k 找到 yk ,最后由 yt 的标号s找到标号为0的xs时结束,获得M-增广路xs yt xi yj , 记P =xs yt , , xi yj ,重新记M为MP,转向.不必理会M-增广路的定义.MP = MP MP, 是对称差. 将yj在M中与之邻接的点xk ,给以标号 j 和标记*, 转向.,例 求下图所示二部图G的最大匹配,53,解 取初始匹配M0 =x2 y2 , x3 y3 , x5 y5 (上图粗线所示). 给X中M0的两个非饱和点x1,x4都给以标号0和标记* (如下图所示)., 去掉x1的标记*, 将与x1邻接的两个点y2, y3都给以标号1. 因为y2, y3都是M0的两个
31、饱和点,所以将它们在M0中邻接的两个点x2, x3都给以相应的标号和标记* (如下图所示).,54, 去掉x2的标记*, 将与x2邻接且尚未给标号的三个点y1, y4, y5都给以标号2 (如下图所示)., 因为y1是M0的非饱和点, 所以顺着标号逆向返回依次得到x2, y2, 直到x1为0为止.于是得到M0的增广路x1 y2x2 y1, 记P = x1 y2 , y2x2 , x2 y1. 取M1 = M0P = x1 y2 , x2 y1 , x3 y3 , x5 y5, 则M1是比M多一边的匹配(如下图所示).,55, 再给X中M1的非饱和点x4给以标号0和标记*, 然后去掉x4的标记*
32、, 将与x4邻接的两个点y2, y3都给以标号4.,因为y2, y3都是M1的两个饱和点, 所以将它们在M1中邻接的两个点x1, x3都给以相应的标号和标记* (如下图所示)., 去掉x1的标记*, 因为与x1邻接的两个点y2, y3都有标号4, 所以去掉x3的标记*.,而与x3邻接的两个点y2, y3也都有标号4, 此时X中所有有标号的点都已去掉了标记*(如下图所示), 因此M1是G的最大匹配.,G不存在饱和X的每个点的匹配, 当然也不存在完美匹配.,工作安排问题之二,56,给n个工作人员x1, x2, , xn安排n项工作y1, y2, , yn. 如果每个工作人员工作效率不同, 要求工作
33、分配的同时考虑总效率最高.,我们构造一个二部赋权图G = ( X, Y, E , F ), 这里X = x1, x2, , xn,Y = y1, y2, , yn, F(xi yj )为工作人员xi胜任工作yj时的工作效率.则问题转化为：求二部赋权图G的最佳匹配.在求G 的最佳匹配时, 总可以假设G为完备二部赋权图.若xi与yj不相邻, 可令F(xi yj )=0. 同样地, 还可虚设点x或y,使|X|=|Y|.如此就将G 转化为完备二部赋权图,而且不会影响结果.,57,定义 设G =(X, Y, E, F)为完备的二部赋权图, 若L：X Y R + 满足： xX, yY, L(x) + L(
34、y)F(xy), 则称L为G的一个可行点标记, 记相应的生成子图为GL =(X, Y, EL , F),这里 EL =xyE|L(x) + L (y) = F (xy).,求完备二部赋权图G = (X, Y, E, F )的最佳匹配算法迭代步骤：设G =(X, Y, E, F)为完备的二部赋权图,L是其一个初始可行点标记,通常取L(x) = max F (x y) | yY, xX,L(y) = 0, yY.,58,M是GL的一个匹配., 若X的每个点都是饱和的,则M是最佳匹配.否则取M的非饱和点uX,令S =u, T =,转向. 记NL(S)=v|uS,uvGL. 若NL(S)= T, 则G
35、L没有完美匹配, 转向. 否则转向. 调整标记, 计算 aL=minL(x) + L (y) - F (xy)|xS, yYT.由此得新的可行点标记,令L = H, GL = GH , 重新给出GL的一个匹配M, 转向., 取yNL (S)T , 若y是M的饱和点, 转向. 否则, 转向., 设x yM, 则令S = S x , T = T y , 转向., 在GL中的u - y路是M- 增广路, 设为P, 并令 M = MP, 转向.,6、网络流问题,59,定义1 设G =(V, E )为有向图,在V中指定一点称为发点(记为vs ),和另一点称为收点(记为vt ), 其余点叫做中间点. 对每
36、一条边vivjE,对应一个非负实数Cij ,称为它的容量. 这样的G称为容量网络,简称网络,记作G = (V, E, C ).,定义2 网络G = (V, E, C )中任一条边vivj有流量 fij ,称集合 f = fij为网络G上的一个流.满足下述条件的流 f 称为可行流： (限制条件)对每一边vivj ,有0 fij Cij ; (平衡条件)对于中间点vk有fik =fkj , 即中间点vk的输入量 = 输出量.,60,如果 f 是可行流,则对收、发点vt、vs有 fsi =fjt =Wf , 即从vs点发出的物质总量 = vt点输入的量. Wf 称为网络流 f 的总流量.,上述概念可
37、以这样来理解,如G是一个运输网络,则发点vs表示发送站,收点vt表示接收站,中间点vk表示中间转运站,可行流 fij 表示某条运输线上通过的运输量,容量Cij表示某条运输线能承担的最大运输量,Wf 表示运输总量.可行流总是存在的.比如所有边的流量 fij = 0就是一个可行流(称为零流).,61,所谓最大流问题就是在容量网络中,寻找流量最大的可行流.,实际问题中,一个网络会出现下面两种情况： 发点和收点都不止一个.解决的方法是再虚设一个发点vs和一个收点vt ,发点vs到所有原发点边的容量都设为无穷大, 所有原收点到收点vt 边的容量都设为无穷大. 网络中除了边有容量外,点也有容量.解决的方法
38、是将所有有容量的点分成两个点,如点v有容量Cv ,将点v分成两个点v和v“,令 C(vv“ ) = Cv .,最小费用流问题,62,这里我们要进一步探讨不仅要使网上的流达到最大,或者达到要求的预定值,而且还要使运输流的费用是最小的,这就是最小费用流问题.,最小费用流问题的一般提法：已知网络G = (V, E, C ),每条边vivjE 除了已给容量Cij外,还给出了单位流量的费用bij(0).所谓最小费用流问题就是求一个总流量已知的可行流 f = f ij 使得总费用,最小.,63,特别地,当要求 f 为最大流时, 即为最小费用最大流问题.,设网络G = (V, E, C), 取初始可行流 f
39、 为零流, 求解最小费用流问题的迭代步骤： 构造有向赋权图Gf =(V, Ef , F),对于任意的vivjE,Ef ,F 的定义如下：当 f ij = 0时,vivjEf ,F(vivj )= bij ;当 f ij = Cij时,vjviEf ,F(vjvi )= - bij ;当0 f ijCij时,vivjEf ,F(vivj )= bij ,vjviEf , F(vjvi ) = - bij .然后转向.,64, 求出含有负权的有向赋权图Gf =(V, Ef , F)中发点vs到收点vt的最短路 ,若最短路 存在转向; 否则f是所求的最小费用最大流,停止., 增流.,vivj与相同,
40、 vivj与相反.,令 = min ij|vivj , 重新定义流 f = f ij为,其它情况不变.,如果Wf 大于或等于预定的流量值,则适当减少 值,使Wf 等于预定的流量值,那么 f 是所求的最小费用流, 停止; 否则转向.,65,下面介绍求解有向赋权图G = (V, E, F )中含有负权的最短路的Ford算法.,设边的权vivj为wij , v1到vi的路长记为 (i ). Ford算法的迭代步骤： 赋初值 (1)=0, (i )=,i = 2, 3, , n . 更新 (i ),i = 2, 3, , n . (i )= min (i ),min ( j ) + wji | ji
41、. 若所有的 (i )都无变化,停止;否则转向.在算法的每一步, (i )都是从v1到vi的最短路长度的上界. 若不存在负长回路,则从v1到vi的最短路长度是 (i )的下界,经过n - 1次迭代后 (i )将保持不变. 若在第n次迭代后 (i )仍在变化时, 说明存在负长回路.,7、关键路径问题（拓扑排序）,66,一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, 都要包括许多工序.这些工序相互约束,只有在某些工序完成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫
42、切希望了解最少需要多少时间才能够完成整个工程项目, 影响工程进度的要害工序是哪几个？,PT(Potentialtask graph)图,67,在PT(Potentialtask graph)图中,用结点表示工序,如果工序 i 完成之后工序 j 才能启动,则图中有一条有向边(i , j ),其长度wi 表示工序 i 所需的时间.,这种图必定不存在有向回路,否则某些工序将在自身完成之后才能开始,这显然不符合实际情况.在PT图中增加两个虚拟结点v0和vn ,使所有仅为始点的结点都直接与v0联结,v0为新增边的始点,这些新增边的权都设为0; 使所有仅为终点的结点都直接与vn联结,vn为新增边的终点.
43、这样得到的图G仍然不存在有向回路.,68,例 一项工程由13道工序组成, 所需时间(单位：天)及先行工序如下表所示(P172). 工序序号 A B C D E F G H I 所需时间 2 6 3 2 4 3 8 4 2 先行工序 A A B C,D D D D G,H 工序序号 J K L M 所需时间 3 8 5 6 先行工序 G H,E J K,试问这项工程至少需要多少天才能完成? 那些工程不能延误? 那些工程可以延误? 最多可延误多少天?,69,先作出该工程的PT图.由于除了工序A外，均有先行工序,因此不必虚设虚拟结点v0.,在PT图中,容易看出各工序先后完成的顺序及时间.,虚拟结点,
44、70,这项工程至少需要多少天才能完成?,就是要求A到N的最长路,此路径称为关键路径.,那些工程不能延误? 那些工程可以延误? 最多可延误多少天?关键路径上的那些工程不能延误.,关键路径(最长路径)算法,71,定理 若有向图G中不存在有向回路,则可以将G 的结点重新编号为u1, u2, , un,使得对任意的边ui ujE(G),都有i j .,各工序最早启动时间算法步骤： 根据定理对结点重新编号为u1, u2, , un . 赋初值 (u1)= 0. 依次更新 (uj ),j = 2, 3, , n . (uj )= max(ui )+ (ui ,uj )|uiujE(G). 结束. 其中(u
45、j )表示工序 uj 最早启动时间,而(un)即(vn)是整个工程完工所需的最短时间.,72,此例不必重新编号，只要按字母顺序即可.,(A)=0, (B)=(C)=2, (D)=8, (E)=max2+3,8+2=10,(F)=(G)=(H)=(D)+2=10, (I)=max(G)+8,(H)+4=18,(J)=(G)+8=18,(K)=max(E)+4,(H)+4=14,(L)=(J)+3=21, (M)=(K)+8=22,(N)=max(F)+3,(I)+2,(L)+5,(M)+6=28.,关键路径?,73,通过以上计算表明：,这项工程至少需要28天才能完成. 关键路径(最长路径): A
46、BDEKMN ABDHKMN,工序A,B,D,E,H,K,M不能延误,否则将影响工程的完成.,但是对于不在关键路径上的工序, 是否允许延误？如果允许, 最多能够延误多长时间呢？各工序允许延误时间t(uj )等于各工序最晚启动时间(uj )减去各工序最早启动时间(uj ). 即 t(uj )=(uj )-(uj ).,74,最晚启动时间算法步骤(已知结点重新编号)：, 赋初值 (un )=(un). 更新 (uj ),j = n - 1, n - 2, , 1. (uj )= min(ui )- (ui ,uj )|uiujE(G). 结束.,顺便提一句,根据工序uj允许延误时间t(uj )是否
47、为0,可判断该工序是否在关键路径上.,75,(N)=28, (M)=28-6=22, (L)=28-5=23,(K)=(M)-8=14,(J)=(L)-3=20,(I)=28-2=26,(H)=min(K)-4,(I)-4=10, (G)=min(J)-8,(I)-8=12,(F)=28-3=25, (E)=(K)-4=10,(D)=min(E)-2,(F)-2,(G)-2,(H)-2=8, (C)=(E)-3=7,(B)=(D)-6=2,(A)=0.,76,各工序允许延误时间如下：,t(A)=t(B)=t(D)=t(E)=t(H)=t(K)=t(M)=0, t(C)=5,t(F)=15,t(
48、G)=2,t(I)=8,t(J)=2, t(L)=2.,PERT图,77,在PERT(Programme evaluation and review technique)图中, 采用有向边表示工序, 其权值表示该工序所需时间. 如果工序ei完成后ej才能开始, 则令vk 是ei的终点, ej 的始点. 根据这种约定, 前例的PERT图如下：,对于PERT图,一些算法与PT图类似.,78,PT图要比PERT图好一些. PT图的结点数基本上是固定的,这是最重要的一点,容易编程计算.,另外PT图比PERT图更加灵活,它能适应一些额外的约束. 例如下图中, 表示工序vi完成一半之后vj就可以开始., 表示工序vi完成后经过t 时刻vj才开始.,
