数模培训图论模型

1、数模培训图论模型1.图论基本概念2.最短路径算法3.最小生成树算法4.遍历性问题5.二分图与匹配6.网络流问题7.关键路径问题8.系统监控模型9.着色模型2/28/20222ABCD哥尼斯堡七桥示意图哥尼斯堡七桥示意图问题问题1(1(哥尼斯堡七桥哥尼斯堡七桥问题问题):): 能否从任一陆地出发通过每座桥恰好一次而回能否从任一陆地出发通过每座桥恰好一次而回到出发点？到出发点？2/28/20223ABDC七桥问题模拟图七桥问题模拟图欧拉指出：欧拉指出： 如果每块陆地所连接的桥都是偶数座，则从如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到任一陆地出发，必能通过每座桥

2、恰好一次而回到出发地出发地. .2/28/20224问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题问题):): 十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，能个城市，能否从某个城市出发在十二面体上依次经过每个城市否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）2/28/20225问题问题3(3(四色问题四色问题):): 对任何一张地图进行着色，两个共同边界的国家染不对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了同的颜色，则只需要四种颜色就

3、够了. .问题问题4(4(关键路径问题关键路径问题):): 一项工程任务一项工程任务, ,大到建造一座大坝大到建造一座大坝, ,一座体育中心一座体育中心, ,小至小至组装一台机床组装一台机床, ,一架电视机一架电视机, , 都要包括许多工序都要包括许多工序. .这些工序相这些工序相互约束互约束, ,只有在某些工序完成之后只有在某些工序完成之后, , 一个工序才能开始一个工序才能开始. . 即即它们之间存在完成的先后次序关系它们之间存在完成的先后次序关系, ,一般认为这些关系是预一般认为这些关系是预知的知的, , 而且也能够预计完成每个工序所需要的时间而且也能够预计完成每个工序所需要的时间. .

4、 这时工程领导人员迫切希望了解最少需要多少时间才能够这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目完成整个工程项目, , 影响工程进度的要害工序是哪几个？影响工程进度的要害工序是哪几个？ 2/28/20226 图论中的图论中的“图图”并不是通常意义下的几何图形或物体的并不是通常意义下的几何图形或物体的形状图形状图, , 而是以一种抽象的形式来表达一些确定的事物之间而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统的联系的一个数学系统. . 定义定义1 一个有序二元组一个有序二元组(V, E ) 称为一个称为一个图图, 记为记为G = (V, E ), 其中其中

5、 V称为称为G的顶点集的顶点集, V , 其元素称为顶点或结点其元素称为顶点或结点, 简称简称点点; E称为称为G的边集的边集, 其元素称为其元素称为边边, 它联结它联结V 中的两个点中的两个点, 如果这两个点是无序的如果这两个点是无序的, 则称该边为则称该边为无向边无向边, 否则否则, 称为称为有向边有向边. 如果如果V = v1, v2, , vn是有限非空点集是有限非空点集, 则称则称G为为有限图有限图或或n阶图阶图. 2/28/20227 如果如果E的每一条边都是无向边的每一条边都是无向边, 则称则称G为为无向图无向图( (如图如图1)1); 如果如果E的每一条边都是有向边的每一条边都

6、是有向边, 则称则称G为为有向图有向图( (如图如图2)2); 否否则则, 称称G为为混合图混合图. 图图1 1图图2 2并且常记并且常记V = v1, v2, , vn, |V | = n ;E = e1, e2, , em(ek=vivj ) , |E | = m.称点称点vi , vj为边为边vivj的的端点端点. 在有向图中在有向图中, 称点称点vi , vj分别为边分别为边vivj的的始始点点和和终点终点. 该图称为该图称为(n,m)图图2/28/20228 对于一个图对于一个图G = (V, E ), 人们常用图形来表示它人们常用图形来表示它, 称其为图解称其为图解. 凡是有向边凡

7、是有向边, 在图解上都用箭头标明其在图解上都用箭头标明其方向方向. 例如例如, 设设V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 则则G = (V, E ) 是一个有是一个有4个顶点和个顶点和6条条边的图边的图, G的图解如下图所示的图解如下图所示. 2/28/20229 一个图会有许多外形不同的图解一个图会有许多外形不同的图解, , 下面两个图表示同下面两个图表示同一个图一个图G = (V, E )的图解的图解. .其中其中V = v1 , v2 , v3 , v4,E = v1v2 , v1v3 ,

8、v1v4 , v2v3 , v2v4 , v3v4. 这两个图互为这两个图互为同构图同构图, ,今后将不计较这种外形上的差别今后将不计较这种外形上的差别, ,而而用一个容易理解的、确定的图解去表示一个图用一个容易理解的、确定的图解去表示一个图. .2/28/202210 有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点, 有一个公共端点的边称为有一个公共端点的边称为相邻边相邻边. 边和它的端点称为边和它的端点称为互相关联互相关联. 常用常用d(v)表示图表示图G中与顶点中与顶点v关联的边的数目关联的边的数目, d(v)称为顶点称为顶点v的的度数度数. 对于有向图对于有向图,还有还有出度

9、出度和和入度入度之分之分. 用用N(v)表示图表示图G中所有与顶点中所有与顶点v相邻的顶点的集合相邻的顶点的集合. d(v1)= d(v3)= d(v4)=4,d(v2)=2.mvdnii2)(1握手定理：握手定理：2/28/202211 (1) (1) 顶点个数是有限的顶点个数是有限的; (2) (2) 任意一条边有且只有两个不同的点与它相互关联任意一条边有且只有两个不同的点与它相互关联; (3) (3) 若是无向图若是无向图, , 则任意两个顶点最多只有一条边与之相联则任意两个顶点最多只有一条边与之相联结结; (4) (4) 若是有向图若是有向图, , 则任意两个顶点最多只有两条边与之则任

10、意两个顶点最多只有两条边与之相联结相联结. . 当两个顶点有两条边与之相联结时，这两条边的当两个顶点有两条边与之相联结时，这两条边的方向相反方向相反. . 如果某个有限图不满足如果某个有限图不满足(2)(3)(4),(2)(3)(4),可在某条边上增设顶点使可在某条边上增设顶点使之满足之满足. .2/28/202212 定义定义2 若将图若将图G的每一条边的每一条边e都对应一个实数都对应一个实数F (e), 则称则称F (e)为该边的为该边的权权, 并称图并称图G为为赋权图赋权图(网络网络), 记为记为G = (V, E , F ). 定义定义3 任意两点均有通路的图称为连通图任意两点均有通路

11、的图称为连通图. 定义定义4 连通而无圈的图称为连通而无圈的图称为树树, 常用常用T表示树表示树. 2/28/202213 例例 一摆渡人欲将一只狼一摆渡人欲将一只狼, ,一头羊一头羊, ,一篮菜从河西渡过河到一篮菜从河西渡过河到河东河东. .由于船小由于船小, ,一次只能带一物过河，并且狼与羊一次只能带一物过河，并且狼与羊, ,羊与菜不羊与菜不能独处能独处. .给出渡河方法给出渡河方法. . 解解：用四维：用四维0-10-1向量表示向量表示( (人人, ,狼狼, ,羊羊, ,菜菜) )在河西岸的状态在河西岸的状态( (在在河西岸则分量取河西岸则分量取1,1,否则取否则取0),0),共有共有2

12、4 =16 种状态种状态. .在河东岸的状在河东岸的状态类似记作态类似记作. . 由题设由题设, ,状态状态(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个个状态状态向量作为顶点向量作为顶点,将可能互相转移的状将可能互相转移的状态用线段连接起来构成一个图态用线段连接起来构成一个图. 根据此图便可找到根据此图便可找到渡河方法渡河方法. .2/28/202214(1,1,1,1) (1,1,1,0) (1,1,0

13、,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,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到到A10

14、的路的路. 从图中易得到两条路：从图中易得到两条路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.2/28/202215 邻接矩阵邻接矩阵 邻接矩阵表示了点与点之间的邻接关系邻接矩阵表示了点与点之间的邻接关系. .一个一个n阶图阶图G的邻接矩阵的邻接矩阵A = (aij )nn , 其中其中 ., 0;, 1EvEvaijijij0101100101001010A2/28/202216无向图无向图G的邻接矩阵的邻接矩阵A是一个对称矩阵是一个对称矩阵. . 0101101101011110A 权矩阵权矩阵 一个一个n阶赋权图阶赋权图G = (

15、V, E, F)的权矩阵的权矩阵A = (aij ) nn , 其中其中 .,;0),(EvjiEvvvFaijijjiij有限简单图基本有限简单图基本上可用权矩阵来上可用权矩阵来表示表示. .2/28/20221705420370860A无向图无向图G的权矩阵的权矩阵A是一个对称矩阵是一个对称矩阵. . 02420737064360A2/28/202218 关联矩阵（略）关联矩阵（略） 一个有一个有m条边的条边的n阶有向图阶有向图G的关联矩的关联矩阵阵A = (aij )nm , 其中其中 若若vi是是ej的始点的始点;若若vi是是ej的终点的终点;若若vi与与ej不关联不关联. ., 0,

16、 1, 1ija 有向图的关联矩阵每列的元素中有且仅有一个有向图的关联矩阵每列的元素中有且仅有一个1,1,有且仅有一有且仅有一个个 - - 1. 1. 1101100011011000000111011001A2/28/202219 一个有一个有m条边的条边的n阶无向图阶无向图G的关联矩阵的关联矩阵A = (aij )nm , 其中其中 若若vi与与ej关联关联;若若vi与与ej不关联不关联. ., 0, 1ija 无向图的关联矩阵每列的元素中有且仅有两个无向图的关联矩阵每列的元素中有且仅有两个1. 1. 110100101010011001000111A2/28/202220 定义定义1 设

17、设P(u, v) 是赋权图是赋权图G = (V, E , F) 中从点中从点u到到v的路的路径径, 用用E(P) 表示路径表示路径P(u, v)中全部边的集合中全部边的集合, 记记)()()(PEeeFPF则称则称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的的最短路最短路. 2/28/202221重要性质：重要性质：

18、若若v0 v1 vm 是是图图G中从中从v0到到vm的最短路的最短路, 则则 1km, v0v1 vk 必为必为G中从中从v0到到vk的最短路的最短路. 即：最短路是一条路，且最短路的任一段也是最短路即：最短路是一条路，且最短路的任一段也是最短路. 求非负赋权图求非负赋权图G中某一点到其它各点最短路，一般用中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般标号算法；求非负赋权图上任意两点间的最短路，一般用用Floyd算法算法. . 这两种算法均适用于有向非负赋权图这两种算法均适用于有向非负赋权图. . 下面分别介绍两种算法的基本过程下面分别介绍两种

19、算法的基本过程. .2/28/202222l指标（指标（a为起点）为起点） 设设T T为为V V的子集，的子集，P=V-TP=V-T且且aTaT，对所有，对所有tTtT，设，设 l(t) l(t)表示从表示从a a到到t t的所的所有通路中距离最短的一条的长度，且这条路径中不包含有通路中距离最短的一条的长度，且这条路径中不包含T T中其他的结点，中其他的结点，则称则称l(t)l(t)为为t t关于集合关于集合P P的指标，若不存在这样的路径，这记的指标，若不存在这样的路径，这记l(t)= l(t)= l注：注：l(t)l(t)不一定是从不一定是从a a到到t t的最短路径，因为最短路径中可能包

20、含的最短路径，因为最短路径中可能包含T T中中其他的节点。其他的节点。l定理定理1 若若t t是是T T中关于中关于P P由最小指标的结点，则由最小指标的结点，则l(t)l(t)是是a a和和t t之间的最短之间的最短距离。距离。l定理定理2 设设 T T为为V V的子集，的子集，P=V-TP=V-T，设，设 (1) (1)对对P P中的任一点中的任一点p,p,存在一条从存在一条从a a到到p p的最短路径的最短路径, ,这条路径仅有这条路径仅有P P中中的点构成的点构成, , (2) (2)对于每一点对于每一点t,t,它关于它关于P P的指标为的指标为l(t),l(t),令令x x为最小指标

21、所在的点为最小指标所在的点, , 即即:l(x)=min(l(t) (t T),:l(x)=min(l(t) (t T), (3) (3)令令P=P x,T=T-x,l(t)P=P x,T=T-x,l(t)表示表示TT中结点中结点t t关于关于PP的指标的指标, ,则则 l(t)=minl(t),l(x)+w(x,t)l(t)=minl(t),l(x)+w(x,t)2/28/2022231、初始化，P=a，T=V-a，对每个结点t计算指标 l(t)=w(a,t) 2、设x为T中关于P有最小指标的点, 即:l(x)=min(l(t) (tT), 3、若T=,则算法结束; 否则,令P=P Ux,T

22、=T-x 按照公式l(t)=minl(t),l(x)+w(x,t), 计算T中每一个结点t关于P的指标. 4、P代替P,T代替T,重复步骤2,3 （ 其中：w(x,y)为图的权矩阵） 2/28/2022241、初始化，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的指标. 若 l(x)+w(x,t) dik + dkj , ,则删除

23、则删除vi到到vj的连线的连线. .得到得到2/28/202229从上图中容易得到任意两点间的最短路从上图中容易得到任意两点间的最短路. .例如例如, ,v1到到v6的路有三条：的路有三条： v1v0v3v2v6( (长度为长度为12),12), v1v4v5v2v6( (长度为长度为7),7), v1v4v7v6( (长度为长度为12).12).2/28/202230 某企业每年年初某企业每年年初, ,都要作出决定都要作出决定, ,如果继续使用旧设备如果继续使用旧设备, ,要要付维修费；若购买一台新设备付维修费；若购买一台新设备, ,要付购买费要付购买费. .试制定一个试制定一个5 5年更年

24、更新计划新计划, ,使总支出最少使总支出最少. . 已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11, 12,12,13. 11,11, 12,12,13. 使用不同时间设备所需的维修费分别为使用不同时间设备所需的维修费分别为5,6,8,11,18.5,6,8,11,18. 解解 设设bi 表示设备在第表示设备在第i 年年初的购买费年年初的购买费, ,ci 表示设备使用表示设备使用i 年后的维修费年后的维修费, , V= v1, v2, , v6,点点vi表示第表示第i 年年初购进一台新设备年年初购进一台新设备, ,虚设虚设一个点一个点v6表示第表示第5 5年年底年年

25、底. . E = vivj | 1ij6. . ijkkijicbvvF1)(2/28/202231 这样上述设备更新问题就变为：在有向赋权图这样上述设备更新问题就变为：在有向赋权图G = (V, E, F )(图解如下图解如下) )中求中求v1到到v6的最短路问题的最短路问题. 2/28/202232 由实际问题可知由实际问题可知, ,设备使用三年后应当更新设备使用三年后应当更新, ,因此删因此删除该图中除该图中v1到到v5 , ,v1到到v6 , ,v2到到v6的连线；又设备使用一年后的连线；又设备使用一年后就更新则不划算就更新则不划算, ,因此再删除该图中因此再删除该图中v1v2 , ,

26、v2v3 , ,v3v4 , ,v4v5 , ,v5v6 五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6和和v1v4v6. . 而这两条路都是而这两条路都是v1到到v6的最短路的最短路. .2/28/202233 由树的定义不难知道由树的定义不难知道, 任意一个连通的任意一个连通的(n,m)图图G适当去掉适当去掉m - - n +1条边后条边后, 都可以变成树都可以变成树, 这棵树称为图这棵树称为图G的生成树的生成树. 设设T是图是图G的一棵生成树的一棵生成树, 用用F(T)表示树表示树T中所有边的权中所有边的权数之和数之和, F(

27、T)称为称为树树T的权的权. 一个连通图一个连通图G的生成树一般不止一棵的生成树一般不止一棵, 图图G的所有生成树中的所有生成树中权数最小的生成树称为图权数最小的生成树称为图G的最小生成树的最小生成树. 求最小生成树问题有很广泛的实际应用求最小生成树问题有很广泛的实际应用. 例如例如, 把把n个乡镇用个乡镇用高压电缆连接起来建立一个电网高压电缆连接起来建立一个电网, 使所用的电缆长度之和最短使所用的电缆长度之和最短, 即费用最小即费用最小, 就是一个求最小生成树问题就是一个求最小生成树问题. 2/28/202234Kruskal算算法：从未选入树中的边中选取权重最小的且不构成法：从未选入树中的

28、边中选取权重最小的且不构成回路的边加入到树中回路的边加入到树中. .（判断回路比较麻烦）（判断回路比较麻烦）Prim算法：把结点分成两个集合，已加入树中的算法：把结点分成两个集合，已加入树中的(P)(P)和未加和未加入树中的入树中的(Q)(Q)，然后每次选择一个点在，然后每次选择一个点在P P中一个点在中一个点在Q Q中的权中的权重最小的边，加入树中，并把相应点加入重最小的边，加入树中，并把相应点加入P P中。中。其最小生成树如下：其最小生成树如下：类似地类似地, ,可定义连通图可定义连通图G 的最大生成树的最大生成树. .2161342272435ABFGHDCE2/28/202235 现准

29、备现准备在在 n 个个居民点居民点v1, v2, , vn中设置一银行中设置一银行. .问设在哪个问设在哪个点点, ,可使最大服务距离最小可使最大服务距离最小? ? 若设置两个银行若设置两个银行, ,问设在哪两个点问设在哪两个点? ? 模型假设模型假设 假设各假设各个个居民点都有条件设置银行居民点都有条件设置银行, ,并有路并有路相连相连, ,且路长已知且路长已知. . 模型建立与求解模型建立与求解 用用Floyd算法求出任意两算法求出任意两个个居民点居民点vi , vj 之间的最短距离之间的最短距离, ,并用并用dij 表示表示. . 设置一个银行设置一个银行, ,银行设银行设在在 vi 点

30、点的最大服务距离为的最大服务距离为.,.,2 , 1,max1niddijnji2/28/202236求求k, ,使使.min1inikdd 即若设置一个银行即若设置一个银行, ,则银行设在则银行设在 vk 点点, ,可使最大服务距离可使最大服务距离最小最小. . 设置两个银行设置两个银行, ,假设银行设假设银行设在在vs , vt 点点使最大服务距使最大服务距离最小离最小. .记记.,minmax),(1jkiknkddjid则则s, ,t 满足：满足：).,(min),(1jidtsdnji进一步进一步, ,若设置多个银行呢？若设置多个银行呢？2/28/202237一、欧拉图一、欧拉图lG

31、=(V,E)为一连通无向图l经过G中每条边至少一次的回路称为巡回巡回；l经过G中每条边正好一次的巡回称为欧拉巡回欧拉巡回；l存在欧拉巡回的图称为欧拉图。欧拉图。二、中国邮递员问题二、中国邮递员问题（CPPchinese postman problem） l一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？l这一问题是我国管梅谷教授1962年首先提出，国际上称之为中国邮递员问题。 2/28/202238l解法：解法：若本身就是欧拉图，则直接可以找到一条欧拉巡回就是若本身就是欧拉图，则直接可以找到一条欧拉巡回就是本问题

32、的解。本问题的解。若不是欧拉图，必定有偶数个奇度数结点，在这些奇度数若不是欧拉图，必定有偶数个奇度数结点，在这些奇度数点之间添加一些边，使之变成欧拉图，再找出一个欧拉巡点之间添加一些边，使之变成欧拉图，再找出一个欧拉巡回。回。l具体解法：具体解法：Fleury算法算法+Edmonds最小对集算法最小对集算法2/28/202239三、哈密尔顿图三、哈密尔顿图lG=(V,E)为一连通无向图l经过G中每点一次且正好一次的路径称为哈密尔顿路径哈密尔顿路径；l经过G中每点一次且正好一次的回路称为哈密尔顿回路哈密尔顿回路；l存在哈密尔顿回路的图称为哈密尔顿图。哈密尔顿图。四、旅行商问题四、旅行商问题（TS

33、Ptraveling salesman problem）l一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线？ 即：从驻地出发，经过每个城市恰好一次，最后返回驻地（最小哈密尔顿回路）（最小哈密尔顿回路）l对于n个节点的旅行商问题，n个节点的任意一个全排列都是问题的一个可能解（假设任意两个点之间都有边）。G个节点的全排列有(n-1)!个，因此间题归结为在(n-1)!个回路中选取最小回路。 lTSP问题的解法属于NPNP完全问题完全问题，一般只研究其近似解法2/28/202240l最邻近算法最邻近算法(1) 选取任意一个点作为起始点,找出与该点相关联的权重最小的边,形成一条初

34、始路径.(2) 找出与最新加入到路径中的点相关联的权重最小的边加入到路径中,且要求不再路径中产生回路.(3) 重复(2)直到所有的结点都加入到路径中.(4) 将起点和最后加入的结点之间的边加入到路径中,形成Hamilton回路.l其他数值算法：其他数值算法： 人工神经元方法， 遗传算法等等2/28/202241 定义定义1 1 设设X, ,Y 都是非空有限集都是非空有限集, ,且且XY = , , E xy| |xX, ,yY, , 称称G =(X, Y, E)为为二部图二部图. . 二部图可认为是有限简单无向图二部图可认为是有限简单无向图. . 如果如果X中的每个点都与中的每个点都与Y中的每

35、个点邻接中的每个点邻接, ,则称则称G =(X, Y, E)为为完备二部图完备二部图. . 若若F：ER + +, ,则称则称G =(X, Y, E, F )为为二部赋权图二部赋权图. . 二部赋权图的权矩阵一般记作二部赋权图的权矩阵一般记作A=(aij )|X|Y | , ,其中其中aij = F (xi yj ). .2/28/202242 定义定义2 2 设设G =(X, Y, E)为二部图为二部图, ,且且M E. .若若M中任意两条边在中任意两条边在G中中均不邻接均不邻接, ,则称则称M是是二部图二部图G的一个的一个匹配匹配. . 定义定义3 3 设设M是二部图是二部图G的一个匹配的

36、一个匹配, ,如果如果G的每一个点都是的每一个点都是M中边的顶中边的顶点点, ,则称则称M是二部图是二部图G的的完美匹配完美匹配； 如果如果G中没有另外的匹配中没有另外的匹配M0 , ,使使| |M0| | |M|,|,则称则称M是二部图是二部图G的的最大最大匹配匹配. . 在二部赋权图在二部赋权图G =(X, Y, E, F )中中, ,权数最大的最大匹配权数最大的最大匹配M称为二部赋称为二部赋权图权图G的的最佳匹配最佳匹配. . 显然显然, ,每个完美匹配都是最大匹配每个完美匹配都是最大匹配, ,反之不一定成立反之不一定成立. .2/28/202243 给给n个工作人员个工作人员x1, x

37、2, , xn安排安排n项工作项工作y1, y2, , yn. . n个工作个工作人员中每个人能胜任一项或几项工作人员中每个人能胜任一项或几项工作, 但并但并不是所有工作人员都能从不是所有工作人员都能从事任何一项工作事任何一项工作. 比如比如x1能做能做y1, y2工作工作, x2能做能做y2, y3, y4工作等工作等. 这样便提出一个问题这样便提出一个问题, 对所有的工作人员能不能都分配一件对所有的工作人员能不能都分配一件他所能胜任的工作？他所能胜任的工作？ 我们构造一个二部图我们构造一个二部图G = ( X, Y, E ), 这里这里X = x1, x2, , xn,Y = y1, y2

38、, , yn, 并且当且仅当工作人员并且当且仅当工作人员xi胜任工作胜任工作yj时时, xi与与yj才相才相邻邻. 于是于是, 问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配. 因为因为 |X|=|Y|, 所以完美匹配即为最大匹配所以完美匹配即为最大匹配. 2/28/202244 从从G的任意匹配的任意匹配M开始开始. . 将将X中中M的所有非饱和点都给以标号的所有非饱和点都给以标号0 0和标记和标记* *, , 转向转向. . M的非饱和点即非的非饱和点即非M的某条边的顶点的某条边的顶点. . 若若X中所有有标号的点都已去掉了标记中所有有标号的点都已去掉了标记* *, ,

39、则则M是是G的最大匹配的最大匹配. . 否则任取否则任取X中一个既有标号又有标记中一个既有标号又有标记* *的点的点xi , , 去掉去掉xi的标记的标记* *, , 转向转向. . 找出在找出在G中所有与中所有与xi邻接的点邻接的点yj , , 若所有这样的若所有这样的yj都已有标号都已有标号, , 则转向则转向, , 否则转向否则转向. .2/28/202245 对与对与xi邻接且尚未给标号的邻接且尚未给标号的yj都给定标号都给定标号i. . 若所有的若所有的 yj 都是都是M的饱和点的饱和点, ,则转向则转向, ,否则逆向返回否则逆向返回. . 即由其中即由其中M的的任一个非饱和点任一个

40、非饱和点 yj 的标号的标号i 找到找到xi , ,再由再由 xi 的标号的标号k 找到找到 yk ,最后由最后由 yt 的的标号标号s找到标号为找到标号为0 0的的xs时结束时结束, ,获得获得M- -增广路增广路xs yt xi yj , , 记记P = xs yt , , xi yj ,重新记重新记M为为M P, ,转向转向. . 不必理会不必理会M- -增广路的定义增广路的定义. . M P = MP MP, , 是对称差是对称差. . 将将yj在在M中与之邻接的点中与之邻接的点xk , ,给以标号给以标号 j 和标记和标记* *, , 转向转向. .2/28/202246解解 取初始

41、匹配取初始匹配M0 = x2 y2 , x3 y3 , x5 y5 ( (上图粗线所示上图粗线所示). ). 给给X中中M0的两个非饱和点的两个非饱和点x1, ,x4都给以标号都给以标号0 0和标记和标记* * ( (如下图如下图所示所示). ). 去掉去掉x1的标记的标记*, 将与将与x1邻接的两个点邻接的两个点y2, y3都给以标号都给以标号1.1. 因为因为y2, y3都是都是M0的两个饱和点的两个饱和点, ,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2, x3都给以都给以相应的标号和标记相应的标号和标记* (如下图所示如下图所示). 2/28/202247 去掉去掉x2

42、的标记的标记*, 将与将与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多一边的匹配多一边的匹配(如下图如下图所示所示). 2/28/202248 再给

43、再给X中中M1的非饱和点的非饱和点x4给以标号给以标号0和标记和标记*, 然后去掉然后去掉x4的标记的标记*, 将与将与x4邻接的两个点邻接的两个点y2, y3都给以标号都给以标号4. 因为因为y2, y3都是都是M1的两个饱和点的两个饱和点, , 所以将它们在所以将它们在M1中邻接的两个点中邻接的两个点x1, x3都给以相应的标号和标记都给以相应的标号和标记* (如下图所示如下图所示). 去掉去掉x1的标记的标记*, 因为与因为与x1邻接的两个点邻接的两个点y2, y3都有标号都有标号4, 所以去掉所以去掉x3的标记的标记*. 而与而与x3邻接的两个点邻接的两个点y2, y3也都有标号也都有

44、标号4, 此时此时X中所有有标号的点都中所有有标号的点都已去掉了标记已去掉了标记*(如下图所示如下图所示), 因此因此M1是是G的最大匹配的最大匹配. G不存在饱和不存在饱和X的每个点的匹配的每个点的匹配, 当然也不存在完美匹配当然也不存在完美匹配.2/28/202249 给给n个工作人员个工作人员x1, x2, , xn安排安排n项工作项工作y1, y2, , yn. . 如果每个如果每个工作人员工作效率不同工作人员工作效率不同, 要求工作分配的同时考虑总效率最高要求工作分配的同时考虑总效率最高. 我们构造一个二部赋权图我们构造一个二部赋权图G = ( X, Y, E , F ), 这里这里

45、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 转化为完备二部赋权图转化为完备二部赋权图, ,而且不会影响结果而且不会影响结果. 2/28/20225

46、0 定义定义 设设G =( (X, Y, E, F) )为完备的二部赋权图为完备的二部赋权图, , 若若L：X Y R + + 满足：满足： xX, yY, L(x) + L(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) )为完备的二部赋权图为完备的二部赋权

47、图, ,L是其一个初始可行点是其一个初始可行点标记标记, ,通常取通常取 L(x) = max F (x y) | yY , xX, L(y) = 0, , yY. 2/28/202251M是是GL的一个匹配的一个匹配. . 若若X的每个点都是饱和的的每个点都是饱和的,则则M是最佳匹配是最佳匹配.否则取否则取M的非饱和点的非饱和点uX,令令S =u,T = ,转向转向. 记记NL(S)=v|uS,uvGL. 若若NL(S)= T, 则则GL没有完美匹配没有完美匹配, 转向转向. 否则转向否则转向. 调整标记调整标记, 计算计算aL=minL(x) + L (y) - - F (xy)|xS,

48、yYT. 由此得新的可行点标记由此得新的可行点标记.),(,)(,)()(ccLLTSvvLTvavLSvavLvH 令令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 = M P, 转向转向. 2/28/202252 定义定义1 1 设设G =(V, E )为有向图为有向图, ,在在V中指

49、定一点称为中指定一点称为发点发点( (记为记为vs ),),和和另一点称为另一点称为收点收点( (记为记为vt ), ), 其余点叫做中间点其余点叫做中间点. . 对每一条边对每一条边vivjE, ,对应一对应一个非负实数个非负实数Cij , ,称为它的称为它的容量容量. . 这样的这样的G称为称为容量网络容量网络, ,简称简称网络网络, ,记作记作G = (V, E, C ). . 定义定义2 2 网络网络G = (V, E, C )中任一条边中任一条边vivj有流量有流量 fij , ,称集合称集合 f = fij 为为网络网络G上的一个上的一个流流. . 满足下述条件的流满足下述条件的流

50、 f 称为可行流：称为可行流： ( (限制条件限制条件) )对每一边对每一边vivj , ,有有0 fij Cij ; ( (平衡条件平衡条件) )对于中间点对于中间点vk有有fik =fkj , , 即中间点即中间点vk的输入的输入量量 = 输出输出量量. . 2/28/202253 如果如果 f 是可行流是可行流, ,则对收、发点则对收、发点vt、vs有有fsi =fjt =Wf , ,即从即从vs点发出的物质总量点发出的物质总量 = vt点输入的量点输入的量. .Wf 称为网络流称为网络流 f 的总流量的总流量. . 上述概念可以这样来理解上述概念可以这样来理解, ,如如G是一个运输网络

51、是一个运输网络, ,则发点则发点vs表示发表示发送站送站, ,收点收点vt表示接收站表示接收站, ,中间点中间点vk表示中间转运站表示中间转运站, ,可行流可行流 fij 表示某条运输表示某条运输线上通过的运输量线上通过的运输量, ,容量容量Cij表示某条运输线能承担的最大运输量表示某条运输线能承担的最大运输量, ,Wf 表表示运输总量示运输总量. . 可行流总是存在的可行流总是存在的. .比如所有边的流量比如所有边的流量 fij = 0就是一个可行流就是一个可行流( (称为零称为零流流).).2/28/202254 所谓最大流问题就是在容量网络中所谓最大流问题就是在容量网络中, ,寻找流量最

52、大的可行流寻找流量最大的可行流. . 实际问题中实际问题中, ,一个网络会出现下面两种情况：一个网络会出现下面两种情况： 发点和收点都不止一个发点和收点都不止一个. . 解决的方法是再虚设一个发点解决的方法是再虚设一个发点vs和一个收点和一个收点vt , ,发点发点vs到所有原发点边到所有原发点边的容量都设为无穷大的容量都设为无穷大, , 所有原收点到收点所有原收点到收点vt 边的容量都设为无穷大边的容量都设为无穷大. . 网络中除了边有容量外网络中除了边有容量外, ,点也有容量点也有容量. . 解决的方法是将所有有容量的点分成两个点解决的方法是将所有有容量的点分成两个点, ,如点如点v有容量

53、有容量Cv , ,将点将点v分成两个点分成两个点v和和v, ,令令C(vv ) = Cv . . 2/28/202255 这里我们要进一步探讨不仅要使网上的流达到最大这里我们要进一步探讨不仅要使网上的流达到最大, ,或者达到要求的或者达到要求的预定值预定值, ,而且还要使运输流的费用是最小的而且还要使运输流的费用是最小的, ,这就是最小费用流问题这就是最小费用流问题. . 最小费用流问题的一般提法：最小费用流问题的一般提法： 已知网络已知网络G = (V, E, C ), ,每条边每条边vivjE 除了已给容量除了已给容量Cij外外, ,还给出了还给出了单位流量的费用单位流量的费用bij(0)

54、.). 所谓最小费用流问题就是求一个总流量已知的可行流所谓最小费用流问题就是求一个总流量已知的可行流 f = f ij 使使得总费用得总费用ijEvvijfbfbji)(最小最小. .2/28/202256 特别地特别地, ,当要求当要求 f 为最大流时为最大流时, , 即为最小费用最大流问题即为最小费用最大流问题. . 设网络设网络G = (V, E, C), 取初始可行流取初始可行流 f 为零流为零流, 求解最小费用流问题求解最小费用流问题的迭代步骤：的迭代步骤： 构造有向赋权图构造有向赋权图Gf =( (V, Ef , F),),对于任意的对于任意的vivjE, ,Ef , ,F 的定义

55、如的定义如下：下： 当当 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 . . 然后然后转向转向. .2/28/202257 求出含有负权的有向赋权图求出含有负权的有向赋权图Gf =( (V, Ef , F) )中发点中发点vs到收点到收点vt的最的最短路短路 , ,若最若最短路短路 存在转向存在转向; 否则否则f是所求的最

56、小费用最大流是所求的最小费用最大流, ,停止停止. . 增流增流. .,jiijjiijijijvvfvvfCvivj与与 相同相同, ,vivj与与 相反相反. .令令 = min ij| |vivj , 重新定义流重新定义流 f = f ij 为为.,jiijjiijijvvfvvff其它情况不变其它情况不变. . 如果如果Wf 大于或等于预定的流量值大于或等于预定的流量值, ,则适当减少则适当减少 值值, ,使使Wf 等于预定的等于预定的流量值流量值, ,那么那么 f 是是所求的最小费用流所求的最小费用流, , 停止停止; 否则转向否则转向. .2/28/202258 下面介绍求解有向赋

57、权图下面介绍求解有向赋权图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 . . 若所有的若所有的 (i )都无变化都无变化, ,停止停止;否则转向否则转向. . 在算法的每一步在算法的每一步, , (i )

58、都是从都是从v1到到vi的最短路长度的上界的最短路长度的上界. . 若不存在负若不存在负长回路长回路, ,则从则从v1到到vi的最短路长度是的最短路长度是 (i )的下界的下界, ,经过经过n - - 1次迭代后次迭代后 (i )将将保持不变保持不变. . 若在第若在第n次迭代后次迭代后 (i )仍在变化时仍在变化时, , 说明存在负长回路说明存在负长回路. . 2/28/202259 一项工程任务一项工程任务, ,大到建造一座大坝大到建造一座大坝, ,一座体育中心一座体育中心, ,小至组装一台机床小至组装一台机床, ,一一架电视机架电视机, , 都要包括许多工序都要包括许多工序. .这些工序

59、相互约束这些工序相互约束, ,只有在某些工序完成之后只有在某些工序完成之后, , 一个工序才能开始一个工序才能开始. . 即它们之间存在完成的先后次序关系即它们之间存在完成的先后次序关系, ,一般认为这些关一般认为这些关系是预知的系是预知的, , 而且也能够预计完成每个工序所需要的时间而且也能够预计完成每个工序所需要的时间. . 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目工程项目, , 影响工程进度的要害工序是哪几个？影响工程进度的要害工序是哪几个？ 2/28/202260 在在PT(Potentialtask

60、graph)图中图中, ,用结点表示工序用结点表示工序, ,如果工序如果工序 i 完成之完成之后工序后工序 j 才能启动才能启动, ,则图中有一条有向边则图中有一条有向边( (i , j ),),其长度其长度wi 表示工序表示工序 i 所需的所需的时间时间. . 这种图必定不存在有向回路这种图必定不存在有向回路, ,否则某些工序将在自身完成之后才能开始否则某些工序将在自身完成之后才能开始, ,这显然不符合实际情况这显然不符合实际情况. . 在在PT图中增加两个虚拟结点图中增加两个虚拟结点v0和和vn , ,使所有仅为始点的结点都直接与使所有仅为始点的结点都直接与v0联结联结, ,v0为新增边的