《《图论方法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图论方法》PPT课件.ppt（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、6 6 图论方法图论方法什么是图什么是图?ABCD哥尼斯堡七桥示意图哥尼斯堡七桥示意图问题问题1(1(哥尼斯堡七桥哥尼斯堡七桥问题问题):):能否从任一陆地出发通过每座桥恰好一次而能否从任一陆地出发通过每座桥恰好一次而回到出发点？回到出发点？ABDC七桥问题模拟图七桥问题模拟图欧拉指出：欧拉指出：如果每块陆地所连接的桥都是偶数座，则如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而从任一陆地出发，必能通过每座桥恰好一次而回到出发地回到出发地.问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题问题):):十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020
2、个城市，个城市，能否从某个城市出发在十二面体上依次经过每个能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）问题问题3(3(四色问题四色问题):):对任何一张地图进行着色，两个共同边界的对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了国家染不同的颜色，则只需要四种颜色就够了.问题问题4(4(关键路径问题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育一座体育中心中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括
3、都要包括许多工序许多工序.这些工序相互约束这些工序相互约束,只有在某些工序完只有在某些工序完成之后成之后,一个工序才能开始一个工序才能开始.即它们之间存在完即它们之间存在完成的先后次序关系成的先后次序关系,一般认为这些关系是预知的一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目少时间才能够完成整个工程项目,影响工程进度影响工程进度的要害工序是哪几个？的要害工序是哪几个？6.1 6.1 图论的基本概念图论的基本概念 图论中的图论中的“图图
4、”并不是通常意义下的几何图并不是通常意义下的几何图形或物体的形状图形或物体的形状图,而是以一种抽象的形式来表而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统达一些确定的事物之间的联系的一个数学系统.定义定义1 一个有序二元组一个有序二元组(V,E)称为一个称为一个图图,记为记为G=(V,E),其中其中 V称为称为G的顶点集的顶点集,V,其元素称为其元素称为顶点顶点或或结点结点,简称简称点点;E称为称为G的边集的边集,其元素称为其元素称为边边,它联结它联结V 中的两个点中的两个点,如果这两个点是无序的如果这两个点是无序的,则称该边则称该边为为无向边无向边,否则否则,称为称为有向边
5、有向边.如果如果V=v1,v2,vn是有限非空点集是有限非空点集,则则称称G为为有限图有限图或或n阶图阶图.如果如果E的每一条边都是无向边的每一条边都是无向边,则称则称G为为无向无向图图(如图如图1)1);如果如果E的每一条边都是有向边的每一条边都是有向边,则称则称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的的始点始点和和终点终点.对
6、于一个图对于一个图G=(V,E),人们常用图形来表示人们常用图形来表示它它,称其为称其为图解图解.凡是有向边凡是有向边,在图解上都用箭在图解上都用箭头标明其方向头标明其方向.例如例如,设设V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4,则则G=(V,E)是一个有是一个有4个顶点和个顶点和6条边的图条边的图,G的图解如下图所示的图解如下图所示.一个图会有许多外形不同的图解一个图会有许多外形不同的图解,下面两个下面两个图表示同一个图图表示同一个图G=(V,E)的图解的图解.其中其中V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v
7、2v4,v3v4.今后将不计较这种外形上的差别今后将不计较这种外形上的差别,而用一个容而用一个容易理解的、确定的图解去表示一个图易理解的、确定的图解去表示一个图.有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点,有一个公共有一个公共端点的边称为端点的边称为相邻边相邻边.边和它的端点称为边和它的端点称为互相关联互相关联.常用常用d(v)表示图表示图G中与顶点中与顶点v关联的边的数目关联的边的数目,d(v)称为顶点称为顶点v的的度数度数.用用N(v)表示图表示图G中所有与顶点中所有与顶点v相邻的顶点的集合相邻的顶点的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.我们今后只讨
8、论我们今后只讨论有限简单图有限简单图：(1)(1)顶点个数是有限的顶点个数是有限的;(2)(2)任意一条边有且只有两个不同的点与它任意一条边有且只有两个不同的点与它相互关联相互关联;(3)(3)若是无向图若是无向图,则任意两个顶点最多只有则任意两个顶点最多只有一条边与之相联结一条边与之相联结;(4)(4)若是有向图若是有向图,则任意两个顶点最多只有则任意两个顶点最多只有两条边与之相联结两条边与之相联结.当两个顶点有两条边与之相当两个顶点有两条边与之相联结时，这两条边的方向相反联结时，这两条边的方向相反.如果某个有限图不满足如果某个有限图不满足(2)(3)(4),(2)(3)(4),可在某条可在
9、某条边上增设顶点使之满足边上增设顶点使之满足.定义定义2 若将图若将图G的每一条边的每一条边e都对应一个实数都对应一个实数F(e),则称则称F(e)为该边的为该边的权权,并称图并称图G为为赋权图赋权图(网络网络),记为记为G=(V,E,F).定义定义3 设设G=(V,E)是一个图是一个图,v0,v1,vkV,且且 1ik,vi-1viE,则称则称v0 v1 vk是是G的一的一条条通路通路.如果通路中没有相同的边如果通路中没有相同的边,则称此通路则称此通路为为道路道路.始点和终点相同的道路称为始点和终点相同的道路称为圈圈或或回路回路.如果通路中既没有相同的边如果通路中既没有相同的边,又没有相同的
10、顶点又没有相同的顶点,则称此通路为则称此通路为路径路径,简称简称路路.定义定义4 任意两点均有通路的图称为任意两点均有通路的图称为连通图连通图.定义定义5 连通而无圈的图称为连通而无圈的图称为树树,常用常用T表示树表示树.例例 一摆渡人欲将一只狼一摆渡人欲将一只狼,一头羊一头羊,一篮菜从河一篮菜从河西渡过河到河东西渡过河到河东.由于船小由于船小,一次只能带一物过河，一次只能带一物过河，并且狼与羊并且狼与羊,羊与菜不能独处羊与菜不能独处.给出渡河方法给出渡河方法.解解：用四维：用四维0-10-1向量表示向量表示(人人,狼狼,羊羊,菜菜)在河在河西岸的状态西岸的状态(在河西岸则分量取在河西岸则分量
11、取1,1,否则取否则取0),0),共有共有24=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个个状态状态向量作为顶点向量作为顶点,将可能互将可能互相转移的状态用线段连接起来构成一个图相转移的状态用线段连接起来构成一个图.根据此图便可找到根据此图便可找到渡河方法渡河方法.(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(
12、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的的路路.从图中易得到两条从图中易得到两条路路：A1 A6 A3 A7 A2 A8 A5 A10;A1
13、A6 A3 A9 A4 A8 A5 A10.图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵 邻接矩阵表示了点与点之间的邻邻接矩阵表示了点与点之间的邻接关系接关系.一个一个n阶图阶图G的邻接矩阵的邻接矩阵A=(aij)nn,其中其中 无向图无向图G的邻接矩阵的邻接矩阵A是一个对称矩阵是一个对称矩阵.权矩阵权矩阵 一个一个n阶赋权图阶赋权图G=(V,E,F)的权的权矩阵矩阵A=(aij)nn,其中其中 有限简单有限简单图基本上可用图基本上可用权矩阵来表示权矩阵来表示.无向图无向图G的权矩阵的权矩阵A是一个对称矩阵是一个对称矩阵.关联矩阵关联矩阵 一个有一个有m条边的条边的n阶有向图阶有向图G的的关联矩
14、阵关联矩阵A=(aij)nm,其中其中 若若vi是是ej的始点的始点;若若vi是是ej的终点的终点;若若vi与与ej不关联不关联.有向图的关联矩阵每列的元素中有且仅有一有向图的关联矩阵每列的元素中有且仅有一个个1,1,有且仅有一个有且仅有一个-1.1.一个有一个有m条边的条边的n阶无向图阶无向图G的关联矩阵的关联矩阵A=(aij)nm,其中其中 若若vi与与ej关联关联;若若vi与与ej不关联不关联.无向图的关联矩阵每列的元素中有且仅有两无向图的关联矩阵每列的元素中有且仅有两个个1.1.6.2 6.2 最短路与最小生成树最短路与最小生成树 定义定义1 设设P(u,v)是赋权图是赋权图G=(V,
15、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的的最短路最短路.重要性质：重要性质：若若v0 v1 vm 是是图图G中从中从v0到到vm的最短路的最短路,则则 1km,v0v1 vk 必为必为G中从中从v0到到vk的最短路的最短路.即：最短路是
16、一条路，且最短路的任一段也即：最短路是一条路，且最短路的任一段也是最短路是最短路.求非负赋权图求非负赋权图G中某一点到其它各点最短路，中某一点到其它各点最短路，一般用一般用Dijkstra标号算法；求非负赋权图上任意标号算法；求非负赋权图上任意两点间的最短路，一般用两点间的最短路，一般用Floyd算法算法.这两种算法这两种算法均适用于有向非负赋权图均适用于有向非负赋权图.由于由于Dijkstra标号算法较为复杂，以下只介标号算法较为复杂，以下只介绍绍Floyd算法算法.求赋权图中任意两点的最短路的求赋权图中任意两点的最短路的Floyd算法：算法：设设A=(aij)nn为赋权图为赋权图G=(V,
17、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,rij=k,转向转向;终止判断终止判断.若若k=n终止终止;否则令否则令k=k+1,转向转向.最短路线可由最短路线可由rij得到得到.例例1 1 求下图中任意两点间的最短路求下图中任意两点间的最短路(P145(P145图图6-5).6-5).解解：用：用Floy
18、d算法算法,首先写出其首先写出其(对称的对称的)权矩权矩阵阵A=(aij)88，然后利用计算机编程计算，然后利用计算机编程计算.0 1 2 3 4 5 6 70 1 2 3 4 5 6 70 0 0 2 8 1 0 2 8 1 1 1 2 0 6 1 2 0 6 1 2 2 8 6 0 7 5 1 2 8 6 0 7 5 1 2 3 3 1 7 0 9 1 7 0 9 4 4 1 5 0 3 8 1 5 0 3 85 5 1 3 0 4 6 1 3 0 4 66 6 2 9 4 0 3 2 9 4 0 37 7 8 6 3 0 8 6 3 0以下仅从图上进行直观操作以下仅从图上进行直观操作.根
19、据若根据若dik+dkjdij,则令则令dij=dik+dkj.将原来将原来的的赋权值改变为赋权值改变为|v2v4|=4,|v5v6|=3.再依次改变为再依次改变为|v1v2|=5,|v0v2|=7.接下来根据接下来根据若若dij=dik+dkj,则删除则删除vi到到vj的连的连线线.得到得到从上图中容易得到任意两点间的最短路从上图中容易得到任意两点间的最短路.例如例如,v1到到v6的路有三条：的路有三条：v1v0v3v2v6(长度为长度为12),12),v1v4v5v2v6(长度为长度为7),7),v1v4v7v6(长度为长度为12).12).设备更新问题设备更新问题 某企业每年年初某企业每
20、年年初,都要作出决定都要作出决定,如果继续使如果继续使用旧设备用旧设备,要付维修费；若购买一台新设备要付维修费；若购买一台新设备,要付要付购买费购买费.试制定一个试制定一个5 5年更新计划年更新计划,使总支出最少使总支出最少.已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11,11,11,12,12,13.12,12,13.使用不同时间设备所需的维修费分别使用不同时间设备所需的维修费分别为为5,6,8,11,18.5,6,8,11,18.解解 设设bi 表示设备在第表示设备在第i 年年初的购买费年年初的购买费,ci 表表示设备使用示设备使用i 年后的维修费年后的维修费,
21、V=v1,v2,v6,点点vi表示第表示第i 年年初购进一台新设备年年初购进一台新设备,虚设一个点虚设一个点v6表示第表示第5 5年年底年年底.E=vivj|1ij6.这样上述设备更新问题就变为：在有向赋权这样上述设备更新问题就变为：在有向赋权图图G=(V,E,F)(图解如下图解如下)中求中求v1到到v6的最短路问的最短路问题题.由实际问题可知由实际问题可知,设备使用三年后应当更新设备使用三年后应当更新,因此删除该图中因此删除该图中v1到到v5,v1到到v6,v2到到v6的连线；又的连线；又设备使用一年后就更新则不划算设备使用一年后就更新则不划算,因此再删除该因此再删除该图中图中v1v2,v2
22、v3,v3v4,v4v5,v5v6 五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6和和v1v4v6.而这两条路都是而这两条路都是v1到到v6的最短路的最短路.最小生成树最小生成树 由树的定义不难知道由树的定义不难知道,任意一个连通的任意一个连通的p,q图图(p个顶点个顶点q条边条边)G适当去掉适当去掉q-p+1条边后条边后,都可都可以变成树以变成树,这棵树称为图这棵树称为图G的的生成树生成树.设设T是图是图G的一棵生成树的一棵生成树,用用F(T)表示树表示树T中中所有边的权数之和所有边的权数之和,F(T)称为称为树树T的权的权.一个
23、连通图一个连通图G的生成树一般不止一棵的生成树一般不止一棵,图图G的的所有生成树中权数最小的生成树称为图所有生成树中权数最小的生成树称为图G的的最小最小生成树生成树.求最小生成树问题有很广泛的实际应用求最小生成树问题有很广泛的实际应用.例例如如,把把n个乡镇用高压电缆连接起来建立一个电网个乡镇用高压电缆连接起来建立一个电网,使所用的电缆长度之和最短使所用的电缆长度之和最短,即费用最小即费用最小,就是就是一个求最小生成树问题一个求最小生成树问题.求连通图求连通图G的最小生成树的最小生成树T的算法的算法(Kruskal避避圈法圈法)：将图：将图G中的边按权从小到大逐条考察中的边按权从小到大逐条考察
24、,按按不构成圈的原则加入到不构成圈的原则加入到T 中中,直到直到 q(T)=p(G)-1为止为止.例如右图例如右图,其其中中p(G)=8.其最小生成树其最小生成树如下：如下：类似地类似地,可定义连通可定义连通图图G 的最大生成树的最大生成树.选址问题选址问题 现准备现准备在在 n 个个居民点居民点v1,v2,vn中设置一中设置一银行银行.问设在哪个点问设在哪个点,可使最大服务距离最小可使最大服务距离最小?若若设置两个银行设置两个银行,问设在哪两个点问设在哪两个点?模型假设模型假设 假设各假设各个个居民点都有条件设置银居民点都有条件设置银行行,并有路相连并有路相连,且路长已知且路长已知.模型建立
25、与求解模型建立与求解 用用Floyd算法求出任意两算法求出任意两个个居民点居民点vi,vj 之间的最短距离之间的最短距离,并用并用dij 表示表示.设置一个银行设置一个银行,银行设银行设在在 vi 点点的最大服务的最大服务距离为距离为求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在 vk 点点,可使最可使最大服务距离最小大服务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使使最大服务距离最小最大服务距离最小.记记则则s,t 满足：满足：进一步进一步,若设置多个银行呢？若设置多个银行呢？6.3 6.3 二部图的匹配及其应用二部图的匹配及其应用 定
26、义定义1 1 设设X,Y 都是非空有限集都是非空有限集,且且XY=,E xy|xX,yY,称称G=(X,Y,E)为为二部图二部图.二部图可认为是有限简单无向图二部图可认为是有限简单无向图.如果如果X中的每个点都与中的每个点都与Y中的每个点邻接中的每个点邻接,则则称称G=(X,Y,E)为为完备二部图完备二部图.若若F：ER+,则称则称G=(X,Y,E,F)为为二部赋二部赋权图权图.二部赋权图的权矩阵一般记作二部赋权图的权矩阵一般记作A=(aij)|X|Y|,其中其中aij=F(xi yj).定义定义2 2 设设G=(X,Y,E)为二部图为二部图,且且M E.若若M中任意两条边在中任意两条边在G中
27、均不邻接中均不邻接,则称则称M是是二部图二部图G的一个的一个匹配匹配.定义定义3 3 设设M是二部图是二部图G的一个匹配的一个匹配,如果如果G的的每一个点都是每一个点都是M中边的顶中边的顶点点,则称则称M是二部图是二部图G的的完美匹配完美匹配；如果如果G中没有另外的匹配中没有另外的匹配M0,使使|M0|M|,|,则则称称M是二部图是二部图G的的最大匹配最大匹配.在二部赋权图在二部赋权图G=(X,Y,E,F)中中,权数最大的权数最大的最大匹配最大匹配M称为二部赋权图称为二部赋权图G的的最佳匹配最佳匹配.显然显然,每个完美匹配都是最大匹配每个完美匹配都是最大匹配,反之不一反之不一定成立定成立.工作
28、安排问题之一工作安排问题之一 给给n个工作人员个工作人员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
29、,并且当并且当且仅当工作人员且仅当工作人员xi胜任工作胜任工作yj时时,xi与与yj才相邻才相邻.于是于是,问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配.因为因为|X|=|Y|,所以完美匹配即为最大匹配所以完美匹配即为最大匹配.求二部图求二部图G=(X,Y,E)的最大匹配算法的最大匹配算法(匈牙匈牙利算法利算法,P149),P149)迭代步骤迭代步骤:从从G的任意匹配的任意匹配M开始开始.将将X中中M的所有的所有非饱和点非饱和点都给以标号都给以标号0 0和和标记标记*,*,转向转向.M的非饱和点即非的非饱和点即非M的某条边的顶点的某条边的顶点.若若X中所有有标号的点都已去掉
30、了标记中所有有标号的点都已去掉了标记*,*,则则M是是G的最大匹配的最大匹配.否则任取否则任取X中一个既有标号中一个既有标号又有标记又有标记*的点的点xi,去掉去掉xi的标记的标记*,*,转向转向.找出在找出在G中所有与中所有与xi邻接的点邻接的点yj,若所有若所有这样的这样的yj都已有标号都已有标号,则转向则转向,否则转向否则转向.对与对与xi邻接且尚未给标号的邻接且尚未给标号的yj都给定标号都给定标号i.若所有的若所有的 yj 都是都是M的的饱和点饱和点,则转向则转向,否则否则逆向返回逆向返回.即由其中即由其中M的任一个非饱和点的任一个非饱和点 yj 的标的标号号i 找到找到xi,再由再由
31、 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 和和标记标记*,*,转向转向.例例 求下图所示二部图求下图所示二部图G的最大匹配的最大匹配.解解 取初始匹配取初始匹配M0=x2 y2,x3 y3,x5 y5 (上图粗线所示上图粗线所示).).给给X中中M
32、0的两个非饱和点的两个非饱和点x1,x4都给以标都给以标号号0 0和标记和标记*(*(如下图所示如下图所示).).给给X中中M0的两个非饱和点的两个非饱和点x1,x4都给以标号都给以标号0 0和标记和标记*(*(如下图所示如下图所示).).去掉去掉x1的标记的标记*,将与将与x1邻接的两个点邻接的两个点y2,y3都给以标号都给以标号1.1.因为因为y2,y3都是都是M0的两个饱和点的两个饱和点,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2,x3都给以相都给以相应的标号和标记应的标号和标记*(如下图所示如下图所示).去掉去掉x1的标记的标记*,将与将与x1邻接的两个点邻接的两个点
33、y2,y3都给以标号都给以标号1.1.因为因为y2,y3都是都是M0的两个饱和点的两个饱和点,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2,x3都给以相都给以相应的标号和标记应的标号和标记*(如下图所示如下图所示).去掉去掉x2的标记的标记*,将与将与x2邻接且尚未给标号邻接且尚未给标号的三个点的三个点y1,y4,y5都给以标号都给以标号2(如下图所示如下图所示).去掉去掉x2的标记的标记*,将与将与x2邻接且尚未给标号邻接且尚未给标号的三个点的三个点y1,y4,y5都给以标号都给以标号2(如下图所示如下图所示).因为因为y1是是M0的非饱和点的非饱和点,所以顺着标号逆所以顺着
34、标号逆向返回依次得到向返回依次得到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多一边的匹配多一边的匹配(如下图所示如下图所示).因为因为y1是是M0的非饱和点的非饱和点,所以顺着标号逆所以顺着标号逆向返回依次得到向返回依次得到x2,y2,直到直到x1为为0为止为止.于是得到于是得到M0的增广路的增广路x1 y2x2 y1,记记P=x1 y2,y2x2,x2 y1.取取M1=M0P=x1 y2,x2 y1,x3 y3,
35、x5 y5,则则M1是比是比M多一边的匹配多一边的匹配(如下图所示如下图所示).再给再给X中中M1的非饱和点的非饱和点x4给以标号给以标号0和标记和标记*,然后去掉然后去掉x4的标记的标记*,将与将与x4邻接的两个点邻接的两个点y2,y3都给以标号都给以标号4.因为因为y2,y3都是都是M1的两个饱和点的两个饱和点,所以将它所以将它们在们在M1中邻接的两个点中邻接的两个点x1,x3都给以相应的标号都给以相应的标号和标记和标记*(如下图所示如下图所示).去掉去掉x1的标记的标记*,因为与因为与x1邻接的两个点邻接的两个点y2,y3都有标号都有标号4,所以去掉所以去掉x3的标记的标记*.而与而与x
36、3邻接的两个点邻接的两个点y2,y3也都有标号也都有标号4,此时此时X中所有有标号的点都已去掉了标记中所有有标号的点都已去掉了标记*(如下图所如下图所示示),因此因此M1是是G的最大匹配的最大匹配.G不存在饱和不存在饱和X的每个点的匹配的每个点的匹配,当然也不存当然也不存在完美匹配在完美匹配.工作安排问题之二工作安排问题之二 给给n个工作人员个工作人员x1,x2,xn安排安排n项工作项工作y1,y2,yn.如果每个工作人员工作效率不同如果每个工作人员工作效率不同,要求工作分配的同时考虑总效率最高要求工作分配的同时考虑总效率最高.我们构造一个二部赋权图我们构造一个二部赋权图G=(X,Y,E,F)
37、,这里这里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 转化为转化为完备二部赋权图完备二部赋权图,而且不会影响结果而且不会影响结果.定义定义 设设G=(X,Y,E,F)为完备的二部赋权图为完备的二部赋权
38、图,若若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)的最佳匹的最佳匹配算法迭代步骤配算法迭代步骤(P152)(P152)：设设G=(X,Y,E,F)为完备的二部赋权图为完备的二部赋权图,L是其是其一个初始可行点标记一个初始可行点标记,通常取通常取 L(x)=max F(x y)|yY,xX,L(y)=0,yY.M是是GL的一个匹配的一个匹配.若若
39、X的每个点都是饱和的的每个点都是饱和的,则则M是最佳匹配是最佳匹配.否则取否则取M的非饱和点的非饱和点uX,令令S=u,T=,转向转向.记记NL(S)=v|uS,uvGL.若若NL(S)=T,则则GL没有完美匹配没有完美匹配,转向转向.否则转向否则转向.调整标记调整标记,计算计算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,转向转向.在在G
40、L中的中的u-y路是路是M-增广路增广路,设为设为P,并令并令 M=M P,转向转向.6.4 6.4 网络流问题网络流问题 定义定义1 1 设设G=(V,E)为有向图为有向图,在在V中指定一点中指定一点称为称为发点发点(记为记为vs),),和另一点称为和另一点称为收点收点(记为记为vt),),其余点叫做中间点其余点叫做中间点.对每一条边对每一条边vivjE,对应一个对应一个非负实数非负实数Cij,称为它的称为它的容量容量.这样的这样的G称为称为容量网容量网络络,简称简称网络网络,记作记作G=(V,E,C).定义定义2 2 网络网络G=(V,E,C)中任一条边中任一条边vivj有流有流量量 fi
41、j,称集合称集合 f=fij 为网络为网络G上的一个上的一个流流.满足下述条件的流满足下述条件的流 f 称为称为可行流可行流：(限制条件限制条件)对每一边对每一边vivj,有有0 fij Cij;(平衡条件平衡条件)对于中间点对于中间点vk有有fik=fkj ,即中间点即中间点vk的输入的输入量量=输出输出量量.如果如果 f 是可行流是可行流,则对收、发点则对收、发点vt、vs有有fsi=fjt=Wf,即从即从vs点发出的物质总量点发出的物质总量=vt点输入的量点输入的量.Wf 称为称为网络流网络流 f 的总流量的总流量.上述概念可以这样来理解上述概念可以这样来理解,如如G是一个运输网是一个运
42、输网络络,则发点则发点vs表示发送站表示发送站,收点收点vt表示接收站表示接收站,中间中间点点vk表示中间转运站表示中间转运站,可行流可行流 fij 表示某条运输线上表示某条运输线上通过的运输量通过的运输量,容量容量Cij表示某条运输线能承担的最表示某条运输线能承担的最大运输量大运输量,Wf 表示运输总量表示运输总量.可行流总是存在的可行流总是存在的.比如所有边的流量比如所有边的流量 fij=0就是一个可行流就是一个可行流(称为零流称为零流).).所谓所谓最大流问题最大流问题就是在容量网络中就是在容量网络中,寻找流量寻找流量最大的可行流最大的可行流.求最大可行流的算法求最大可行流的算法(不必理
43、会其不必理会其中中可增广链可增广链的定义的定义)见见P155-156.P155-156.实际问题中实际问题中,一个网络会出现下面两种情况：一个网络会出现下面两种情况：发点和收点都不止一个发点和收点都不止一个.解决的方法是再虚设一个发点解决的方法是再虚设一个发点vs和一个收点和一个收点vt,发点发点vs到所有原发点边的容量都设为无穷大到所有原发点边的容量都设为无穷大,所有原收点到收点所有原收点到收点vt 边的容量都设为无穷大边的容量都设为无穷大.网络中除了边有容量外网络中除了边有容量外,点也有容量点也有容量.解决的方法是将所有有容量的点分成两个点解决的方法是将所有有容量的点分成两个点,如点如点v
44、有容量有容量Cv,将点将点v分成两个点分成两个点v和和v,令令C(vv)=Cv.最小费用流问题最小费用流问题 这里我们要进一步探讨不仅要使网上的流达这里我们要进一步探讨不仅要使网上的流达到最大到最大,或者达到要求的预定值或者达到要求的预定值,而且还要使运输而且还要使运输流的费用是最小的流的费用是最小的,这就是最小费用流问题这就是最小费用流问题.最小费用流问题的一般提法：最小费用流问题的一般提法：已知网络已知网络G=(V,E,C),每条边每条边vivjE 除了已除了已给容量给容量Cij外外,还给出了单位流量的费用还给出了单位流量的费用bij(0).).所谓最小费用流问题就是求一个总流量已知所谓最
45、小费用流问题就是求一个总流量已知的可行流的可行流 f=f ij 使得总费用使得总费用最小最小.特别地特别地,当要求当要求 f 为最大流时为最大流时,此问题即为此问题即为最最小费用最大流问题小费用最大流问题.设网络设网络G=(V,E,C),取初始可行流取初始可行流 f 为零流为零流,求解最小费用流问题的迭代步骤求解最小费用流问题的迭代步骤(P158-159)(P158-159)：构造有向赋权图构造有向赋权图Gf=(V,Ef,F),),对于任意对于任意的的vivjE,Ef,F 的定义如下：的定义如下：当当 f ij=0时时,vivjEf,F(vivj)=bij;当当 f ij=Cij时时,vjvi
46、Ef,F(vjvi)=-bij;当当0 f ijCij时时,vivjEf,F(vivj)=bij,vjviEf,F(vjvi)=-bij.然后然后转向转向.求出含有负权的有向赋权图求出含有负权的有向赋权图Gf=(V,Ef,F)中发点中发点vs到收点到收点vt的最短路的最短路 ,若最若最短路短路 存在转存在转向向;否则否则f是所求的最小费用最大流是所求的最小费用最大流,停止停止.增流增流.vivj与与 相同相同,vivj与与 相反相反.令令 =min ij|vivj ,重新定义流重新定义流 f=f ij 为为其它情况不变其它情况不变.如果如果Wf 大于或等于预定的流量值大于或等于预定的流量值,则
47、适当减则适当减少少 值值,使使Wf 等于预定的流量值等于预定的流量值,那么那么 f 是是所求的所求的最小费用流最小费用流,停止停止;否则转向否则转向.下面介绍求解有向赋权图下面介绍求解有向赋权图G=(V,E,F)中含中含有负权的最短路的有负权的最短路的Ford算法算法.设边的权设边的权vivj为为wij,v1到到vi的路长记为的路长记为 (i).Ford算法的迭代步骤算法的迭代步骤(P160-161)(P160-161)：赋初值赋初值 (1)=0,(i)=,i=2,3,n.更新更新 (i),i=2,3,n.(i)=min (i),min (j)+wji|ji.若所有的若所有的 (i)都无变化都
48、无变化,停止停止;否则转向否则转向.在算法的每一步在算法的每一步,(i)都是从都是从v1到到vi的最短路长度的的最短路长度的上界上界.若不存在负长回路若不存在负长回路,则从则从v1到到vi的最短路长度是的最短路长度是 (i)的下界的下界,经过经过n-1次迭代后次迭代后 (i)将保持不变将保持不变.若在第若在第n次次迭代后迭代后 (i)仍在变化时仍在变化时,说明存在负长回路说明存在负长回路.6.5 6.5 关键路径问题关键路径问题 一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育一座体育中心中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括都要包括许多工序
49、许多工序.这些工序相互约束这些工序相互约束,只有在某些工序完只有在某些工序完成之后成之后,一个工序才能开始一个工序才能开始.即它们之间存在完即它们之间存在完成的先后次序关系成的先后次序关系,一般认为这些关系是预知的一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目少时间才能够完成整个工程项目,影响工程进度影响工程进度的要害工序是哪几个？的要害工序是哪几个？PT(Potentialtask graph)图图 在在PT(Potentialta
50、sk graph)图中图中,用结点表示用结点表示工序工序,如果工序如果工序 i 完成之后工序完成之后工序 j 才能启动才能启动,则图则图中有一条有向边中有一条有向边(i,j),),其长度其长度wi 表示工序表示工序 i 所所需的时间需的时间.这种图必定不存在有向回路这种图必定不存在有向回路,否则某些工序将否则某些工序将在自身完成之后才能开始在自身完成之后才能开始,这显然不符合实际情况这显然不符合实际情况.在在PT图中增加两个虚拟结点图中增加两个虚拟结点v0和和vn,使所有仅使所有仅为始点的结点都直接与为始点的结点都直接与v0联结联结,v0为新增边的始点为新增边的始点,这些新增边的权都设为这些新