数学建模--图论.ppt

《数学建模--图论.ppt》由会员分享，可在线阅读，更多相关《数学建模--图论.ppt（97页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数学建模基地系列课件数学建模基地系列课件-数学建模数学建模数学建模数学建模 图论方法专题图论方法专题专题板块系列专题板块系列概率统计专题概率统计专题1优化专题优化专题2模糊方法及微分方程专题模糊方法及微分方程专题3图论方法专题图论方法专题华中农业大学数学建模基地华中农业大学数学建模基地图论方法专题一一图论的基本概念图论的基本概念二二二二最短路与最小生成树最短路与最小生成树三三三三二部图的匹配二部图的匹配四四四四网络流网络流华中农业大学数学建模基地华中农业大学数学建模基地ABCD哥尼斯堡哥尼斯堡七桥示意图七桥示意图问题问题1:七桥问题七桥问题能否从任一陆地出发通过每座桥恰好一次而能否从任一陆地

2、出发通过每座桥恰好一次而回到出发点？回到出发点？图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地七桥七桥问题模拟图问题模拟图:ABDC欧拉指出：如果每块陆地所连接的桥都是偶数座，则欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出从任一陆地出发，必能通过每座桥恰好一次而回到出发地。发地。图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地问题问题2:哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）十二面体的十二面体的20个顶点代表世界上个顶点代表世界上20个城市，能个城市，能否从某个城市出发在十二面体

3、上依次经过每个否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？城市恰好一次最后回到出发点？图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地问题问题3:四色问题四色问题 对任何一张地图进行着色，两个共同边界的对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了。国家染不同的颜色，则只需要四种颜色就够了。德德摩尔根致哈密顿的信（摩尔根致哈密顿的信（1852年年10月月23日）日）我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需

4、要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地问题问题4(4(关键路径问题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这这些工序相互约束些工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,一个工序一个工序才能开始才能开始.即它们之间存在完成的先后次序关系即它们之间存在完成的先后次序关系,一般一般认为这些关系是预知的认为这些关系是预知的,而且也能够

5、预计完成每个工序而且也能够预计完成每个工序所需要的时间所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目才能够完成整个工程项目,影响工程进度的要害工序是影响工程进度的要害工序是哪几个？哪几个？图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地定义定义1 一个有序二元组一个有序二元组(V,E)称为一个称为一个图图,记为记为G=(V,E),其中其中 V或或V(G)称称为为G的的顶顶点点集集,V,其其元元素素称称为为顶顶点点或或结结点点,简称简称点点;E或或E(G)称为称为G的的边集边集,其元素称为其

6、元素称为边边,它联结它联结V 中的中的两个点两个点,如果这两个点是无序的如果这两个点是无序的,则称该边为则称该边为无向边无向边,否则否则,称为称为有向边有向边.图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地如果如果V=v1,v2,vn是有限非空点集是有限非空点集,则称则称G为为有限图有限图或或n阶图阶图.如果如果E的每一条边都是无向边的每一条边都是无向边,则称则称G为为无向图无向图;如果如果E的每一条边都是有向边的每一条边都是有向边,则称则称G为为有向图有向图;否则否则,称称G为为混合图混合图.记记E=e1,e2,em(ek=vivj).图论的基本概念图论的基本概

7、念华中农业大学数学建模基地华中农业大学数学建模基地对于一个图对于一个图G=(V,E),人们常用图形来表示它人们常用图形来表示它,称其为称其为图解图解.凡是有向边凡是有向边,在图解上都用箭头标明其方向在图解上都用箭头标明其方向.称点称点vi,vj为边为边vivj的的端点端点.有边联结的两个点称为有边联结的两个点称为相邻顶点相邻顶点,有一个公共端点的边称为有一个公共端点的边称为相邻边相邻边.边和它的端点称为边和它的端点称为互相关联互相关联.有向图中的关联又分有向图中的关联又分出关联出关联和和入关联入关联。图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地常用常用d(v)表

8、示图表示图G中与顶点中与顶点v关联的边的数目关联的边的数目,d(v)称为顶点称为顶点v的的度数度数.与顶点与顶点v出出关联的边的数目称为关联的边的数目称为出度出度，记作，记作d+(v),与顶点与顶点v入入关联的边的数目称为关联的边的数目称为入度入度，记作，记作d-(v)。用用N(v)表示图表示图G中所有与顶点中所有与顶点v相邻的顶点的集合相邻的顶点的集合.图论的基本概念图论的基本概念任意两顶点都相临的简单图称为任意两顶点都相临的简单图称为完全图完全图.有有n个顶点的完全图记为个顶点的完全图记为K n。华中农业大学数学建模基地华中农业大学数学建模基地几个基本定理：几个基本定理：图论的基本概念图论

9、的基本概念华中农业大学数学建模基地华中农业大学数学建模基地用图论思想求解以下各题用图论思想求解以下各题例例1、一摆渡人欲将一只狼，一头羊，一篮菜从、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。河方法。图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地解：解：用四维用四维0-1向量表示（人，狼，羊，菜）的在西岸向量表示（人，狼，羊，菜）的在西岸状态，（在西岸则分量取状态，（在西岸则分量取1，否则取，否则取

10、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)也是也是不允许的，不允许的，图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶

11、图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地例例2、考虑中国象棋的如下问题：、考虑中国象棋的如下问题：（1）下过奇数盘棋的人数是偶数个。）下过奇数盘棋的人数是偶数个。（2）马有多少种跳法？）马有多少种跳法？（3）马跳出后又跳回起点，证明马跳了偶数步。）马跳出后又跳回起点，证明马跳了偶数步。（4）红方的马能不能在自己一方的棋盘上不重复）红方的马能不能在自己一方的棋盘上不重复的跳遍每一点，最后跳回起

12、点？的跳遍每一点，最后跳回起点？图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地例例3、证明：在任意、证明：在任意6人的集会上，总有人的集会上，总有3人互相认人互相认识，或总有识，或总有3人互相不认识。人互相不认识。解：以顶点表示人，以边表示认识，得解：以顶点表示人，以边表示认识，得6个顶点个顶点的简单图的简单图G。问题：问题：3人互相认识即人互相认识即G包含包含K3为子图，为子图，3人互相不认识即人互相不认识即G包含（包含（3,0）图为子图。）图为子图。图论的基本概念图论的基本概念华中农业大学数学建模基地华中农业大学数学建模基地图论的基本概念图论的基本概念华中农业

13、大学数学建模基地华中农业大学数学建模基地定义2若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F).定义3设G=(V,E)是一个图,v0,v1,vkV,且“1ik,vi1viE,则称v0v1vk是G的一条通路.图论的基本概念图论的基本概念如果通路中没有相同的顶点,则称此通路为路径,简称路.始点和终点相同的路称为圈或回路华中农业大学数学建模基地华中农业大学数学建模基地定义定义4 顶点u与v称为连通的，如果存在u-v通路，任二顶点都连通的图称为连通图连通图，否则，称为不连通图。极大连通子图称为连通支连通支。图论的基本概念图论的基本概念

14、定义5连通而无圈的图称为树,常用T表示树.树中最长路的长称为树的高。树的度为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。设G是有向图，如果G的基础图是树，则称G是有向树，也简称树。华中农业大学数学建模基地华中农业大学数学建模基地邻接矩阵A=(aij)nn,例4：写出右图的邻接矩阵：解：图的矩阵表示图的矩阵表示华中农业大学数学建模基地华中农业大学数学建模基地权矩阵A=(aij)nn 例5：写出右图的权矩阵：解：图的矩阵表示图的矩阵表示华中农业大学数学建模基地华中农业大学数学建模基地关联矩阵A A=(aij)nm 有向图：无向图：图的矩阵表示图的矩阵表示华中农业大学数学建模基地华中农业

15、大学数学建模基地例6：写出右图与其基本图的关联矩阵解：分别为：图的矩阵表示图的矩阵表示华中农业大学数学建模基地华中农业大学数学建模基地定义定义 1 设设 P(u,v)是赋权图是赋权图G=(V,E,F)中从中从点点u到到v的路径的路径,用用E(P)表示路径表示路径P(u,v)中全中全部边的集合部边的集合,记记F(P)=,则称则称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 中连接中连

16、接u,v的的最短路最短路.最短路最短路华中农业大学数学建模基地华中农业大学数学建模基地重要性质：重要性质：若若v0 v1 vm 是是G中从中从v0到到vm的最短路的最短路,则则对对1km,v0v1 vk 必为必为G中从中从v0到到vk的的最短路最短路.即：最短路是一条路，且最短路的任一段即：最短路是一条路，且最短路的任一段也是最短路。也是最短路。最短路最短路华中农业大学数学建模基地华中农业大学数学建模基地例例7 对下面的有向图求顶点对下面的有向图求顶点v0到到其余顶点的其余顶点的最短路。最短路。1445642537最短路最短路华中农业大学数学建模基地华中农业大学数学建模基地Dijkstra算法

17、：求某一顶点到其余顶点的最短路最短路最短路华中农业大学数学建模基地华中农业大学数学建模基地68523374例例8：求下列任意两点的最短路和距离。：求下列任意两点的最短路和距离。最短路最短路华中农业大学数学建模基地华中农业大学数学建模基地Floyd算法算法:求任意两顶点的最短路求任意两顶点的最短路 设设A=(aij)nn为赋权图为赋权图G=(V,E,F)的权矩阵的权矩阵,dij表表示从示从vi到到vj点的距离点的距离,rij表示从表示从vi到到vj点的最短路中一个点的最短路中一个点的编号点的编号.赋初值赋初值.对所有对所有i,j,dij=aij,rij=j.k=1.转向转向.更新更新dij,ri

18、j.对所有对所有i,j,若若dik+dk jdij,则令则令dij=dik+dkj,rij=k,转向转向;终止判断终止判断.若若k=n终止终止;否则令否则令k=k+1,转向转向.最短路线可由最短路线可由rij得到得到.最短路最短路华中农业大学数学建模基地华中农业大学数学建模基地 求非负赋权图求非负赋权图G中某一点到其它各点最短路，一般中某一点到其它各点最短路，一般用用Dijkstra标号算法；标号算法；Dijkstra标号算法只适用于全部权为非负情况。标号算法只适用于全部权为非负情况。求非负赋权图上任意两点间的最短路，一般用求非负赋权图上任意两点间的最短路，一般用Floyd算法算法.Floyd

19、算法可以适用于有负权的情况，还能判断是算法可以适用于有负权的情况，还能判断是否有负回路。否有负回路。这两种算法均适用于有向赋权图这两种算法均适用于有向赋权图.最短路最短路华中农业大学数学建模基地华中农业大学数学建模基地由树的定义不难知道由树的定义不难知道,任意一个连通的任意一个连通的(p,q)图图G适适当当去去掉掉q-p+1条条边边后后,都都可可以以变变成成树树,这这棵棵树树称为图称为图G的的生成树生成树.设设T是图是图G的一棵生成树的一棵生成树,用用F(T)表示树表示树T中所有边的权数之和中所有边的权数之和,F(T)称为树称为树T的的权权.一个连通图一个连通图G的生成树一般不止一棵的生成树一

20、般不止一棵,图图G的所有生成树中权数最小的生成树称为的所有生成树中权数最小的生成树称为图图G的的最小生成树最小生成树.最小生成树最小生成树华中农业大学数学建模基地华中农业大学数学建模基地64686865505061456054例例9：如下图：如下图G，求最小生成树：求最小生成树：Kruskal算法：从最小边开始按最小权加边，算法：从最小边开始按最小权加边，有圈去掉。有圈去掉。最小生成树最小生成树华中农业大学数学建模基地华中农业大学数学建模基地 例例10(10(设备更新问题设备更新问题)某企业使用一台设备某企业使用一台设备,每年年每年年初初,企业都要作出决定企业都要作出决定,如果继续使用旧的如果

21、继续使用旧的,要付维修费；要付维修费；若购买一台新设备若购买一台新设备,要付购买费要付购买费.试制定一个试制定一个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 年后的维修费年

22、后的维修费,V=v1,v2,v6,点点vi表示第表示第i 年年年年初购进一台新设备初购进一台新设备,虚设一个点虚设一个点v6表示第表示第5 5年年底年年底.E=vivj|1ij6.求求v1到到v6的最短路问题的最短路问题.最小生成树最小生成树华中农业大学数学建模基地华中农业大学数学建模基地 由实际问题可知由实际问题可知,设备使用三年后应当更新设备使用三年后应当更新,因此删因此删除该图中除该图中v1到到v5,v1到到v6,v2到到v6的连线；又设备使用一年的连线；又设备使用一年后就更新则不划算后就更新则不划算,因此再删除该图中因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6 五条

23、连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6和和v1v4v6.而这两条路都是而这两条路都是v1到到v6的最短路的最短路.最小生成树最小生成树华中农业大学数学建模基地华中农业大学数学建模基地例例11 多阶段存储问题多阶段存储问题某公司根据市场情况，预计某商品今后六个月的某公司根据市场情况，预计某商品今后六个月的需要量，进货单价与存储单价如下需要量，进货单价与存储单价如下月份123456需要（件）607070504540单价（元）800 780860 860 760 810存储月份存储月份 1223344556存储单价存储单价 40353

24、52540若当月订购当月所需商品不附加存储费，问如何若当月订购当月所需商品不附加存储费，问如何进货使总费用最小。进货使总费用最小。最小生成树最小生成树华中农业大学数学建模基地华中农业大学数学建模基地称称G=(X,Y,E)为为二部图二部图.如果如果X中的每个点都与中的每个点都与Y中的中的每个点邻接每个点邻接,则称则称G=(X,Y,E)为为完备二部图完备二部图.若若 F：E R+,则称则称G=(X,Y,E,F)为为二部赋权图二部赋权图.定义定义1 设设X,Y都是非空有限顶点集都是非空有限顶点集,且且X Y=,二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地定

25、义定义3 若匹配若匹配M的某条边与点的某条边与点v关联关联,则称则称M饱和饱和点点v,并且称并且称v是是M的的饱和点饱和点,否则称否则称v是是M的的非饱非饱和点和点.定义定义4 设设M是图是图G的一个匹配的一个匹配,如果如果G的每一个点的每一个点都是都是M的饱和点的饱和点,则称则称M是是完美匹配完美匹配；如果；如果G中中没有另外的匹配没有另外的匹配M0,使使|M0|M|,则称则称M是是最最大匹配大匹配.每个完美匹配都是最大匹配每个完美匹配都是最大匹配,反之不一定成立反之不一定成立.二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地例例16：判断下图的匹配判

26、断下图的匹配最大匹配最大匹配非完美匹配非完美匹配完美匹配完美匹配二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地定义定义5 设设M是图是图G的的一个匹配的的一个匹配,其边在其边在EM和和M 中交错出现的路中交错出现的路,称为称为G的一条的一条M交错路交错路.起点起点和终点都不是和终点都不是M的饱和点的的饱和点的M 交错路交错路,称为称为M 增广路增广路.定理定理1 G的一个匹配的一个匹配M是最大匹配的是最大匹配的充要条件充要条件是是G不包含不包含M 增广路增广路.二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地定理

27、定理2 设设G=(X,Y,E)为二部图为二部图,则则 G存在存在饱和饱和X的每个点的匹配的充要条件是的每个点的匹配的充要条件是对任意对任意S ,有有|N(S)|S|.其中其中,N(S)=v|uS,v与与u相邻相邻.G存在完美匹配的充要条件是存在完美匹配的充要条件是对任意对任意S 或或S 有有|N(S)|S|.二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地工作安排问题之一工作安排问题之一 给给n个工作人员个工作人员x1,x2,xn安排安排n项工作项工作y1,y2,yn.n个工作人员中每个人能胜任一项或几项工作个工作人员中每个人能胜任一项或几项工作,但并但

28、并不是所有工作人员都能从事任何一项工作不是所有工作人员都能从事任何一项工作.比如比如x1能做能做y1,y2工作工作,x2能做能做y2,y3,y4工作等工作等.这样便提出一个问题这样便提出一个问题,对所有的工作人员能不能都对所有的工作人员能不能都分配一件他所能胜任的工作？分配一件他所能胜任的工作？二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地 我们构造一个二部图我们构造一个二部图G=(X,Y,E),这里这里X=x1,x2,xn,Y=y1,y2,yn,并且当且仅当工作人员并且当且仅当工作人员xi胜任工作胜任工作yj时时,xi与与yj才相邻才相邻.于是于是,

29、问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配.因为因为|X|=|Y|,所以完美匹配即为最大匹配所以完美匹配即为最大匹配.二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地例例17：求下图完美匹配：求下图完美匹配Hungarian算法：算法：二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：解解 取初始匹配取初始匹配M0=x2 y2,x3 y3,x5 y5 给给X中中M0的两个非饱和点的两个非饱和点x1,x4都给以标号都给以标号0

30、 0和和标记标记*(如下图所示如下图所示).).00*二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：00 去掉去掉x1的标记的标记*,将与将与x1邻接的两个点邻接的两个点y2,y3都给都给以标号以标号1.1.因为因为y2,y3都是都是M0的两个饱和点的两个饱和点,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2,x3都给以相应的标号和标记都给以相应的标号和标记*.*11*23*二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地例例1

31、8：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：00*11*23*去掉去掉x2的标记的标记*,将与将与x2邻接且尚未给标号的三邻接且尚未给标号的三个点个点y1,y4,y5都给以标号都给以标号2.222二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：00*1123*222 因为因为y1是是M0的非饱和点的非饱和点,逆向返回逆向返回,直到直到x1为为0为为止止.于是得到于是得到M0的增广路的增广路x1 y2x2 y1,记记P=x1 y2,y2x2,x2 y1.取取M1=

32、M0P=x1 y2,x2 y1,x3 y3,x5 y5,则则M1是比是比M多一边的匹配多一边的匹配.二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：0*再给再给X中中M1的非饱和点的非饱和点x4给以标号给以标号0和标记和标记*,然后然后去掉去掉x4的标记的标记*,将与将与x4邻接的两个点邻接的两个点y2,y3都给以标号都给以标号4.44二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈

33、亚利算法：044 因为因为y2,y3都是都是M1的两个饱和点的两个饱和点,所以将它们在所以将它们在M1中中邻接的两个点邻接的两个点x1,x3都给以相应的标号和标记都给以相应的标号和标记*.*23二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：044*23 去掉去掉x1的标记的标记*,因为与因为与x1邻接的两个点邻接的两个点y2,y3都有标号都有标号4,所以去掉所以去掉x3的标记的标记*.而与而与x3邻接的两个点邻接的两个点y2,y3也都有标号也都有标号4,此时此时X中所中所有有标号的

34、点都已去掉了标记有有标号的点都已去掉了标记*(如下图所示如下图所示),因此因此M1是是G的最大匹配的最大匹配.没有完美匹配。没有完美匹配。二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：注意到注意到S=x1,x3,x4时，时，N(S)=y1,y3,所以没有完美匹配。所以没有完美匹配。二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地定义定义6 设设G=(X,Y,E,F)为完备的二部赋权为完备的二部赋权图图,若若L：X Y R+满足：满足：对任意对

35、任意xX,yY,L(x)+L(y)F(x y),则称则称L为为G的一个的一个可行点标记可行点标记,记相应的生成记相应的生成子图为子图为GL=(X,Y,EL,F),这里这里EL=x yE|L(x)+L(y)=F(x y).定理定理3 设设L是完备的二部赋权图是完备的二部赋权图G=(X,Y,E,F)的可行点标记的可行点标记,若若M*是是GL的完美匹配的完美匹配,则则M*是是G的最佳匹配的最佳匹配.(权数最大的匹配权数最大的匹配)二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地工作安排问题之二工作安排问题之二 给给n个工作人员个工作人员x1,x2,xn安排安排

36、n项工作项工作y1,y2,yn.如果每个工作人员工作效率不同如果每个工作人员工作效率不同,要求工作分配的同要求工作分配的同时考虑时考虑总效率最高总效率最高.二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地 我们构造一个二部赋权图我们构造一个二部赋权图G=(X,Y,E,F),这里这里X=x1,x2,xn,Y=y1,y2,yn,F(xi yj)为工作人员为工作人员xi胜胜任工作任工作yj时的工作效率时的工作效率.则问题转化为：求二部赋权图则问题转化为：求二部赋权图G的最佳匹配的最佳匹配.在求在求G 的最佳匹配时的最佳匹配时,总可以假设总可以假设G为完备二部赋

37、权为完备二部赋权图图.若若xi与与yj不相邻不相邻,可令可令F(xi yj)=0.同样地同样地,还可虚设点还可虚设点x或或y,使使|X|=|Y|.如此就将如此就将G 转化为完备二部赋权图转化为完备二部赋权图,而且不而且不会影响结果会影响结果.二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地例例19：求赋权矩阵为：求赋权矩阵为的的完备二部赋权图完备二部赋权图G=(X,Y,E,F)的最佳匹配。的最佳匹配。可行顶点标号法：可行顶点标号法：矩阵覆盖法：矩阵覆盖法：分枝定界法：分枝定界法：二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学

38、数学建模基地矩阵覆盖法：矩阵覆盖法：STEP1：求等价分配矩阵。：求等价分配矩阵。STEP2：求独立零元，画上框。（非同列同行的零）：求独立零元，画上框。（非同列同行的零）STEP3：最优判别：达到：最优判别：达到n个独立零元。停。个独立零元。停。STEP4：求覆盖线：求覆盖线：1）封锁没有画框零元的行，封锁就打）封锁没有画框零元的行，封锁就打；2）在封锁行中未画框零元的列也封锁；）在封锁行中未画框零元的列也封锁；3）在封锁列中画框零元的行也封锁；）在封锁列中画框零元的行也封锁；4）未封锁行与封锁列画上覆盖线。）未封锁行与封锁列画上覆盖线。STEP5：调节分配矩阵：在未覆盖元中选取最大元：调节

39、分配矩阵：在未覆盖元中选取最大元k，未覆盖行加未覆盖行加 k，覆盖列减，覆盖列减 k。转。转STEP2.二部图的匹配及其应用二部图的匹配及其应用华中农业大学数学建模基地华中农业大学数学建模基地 定定义义1 设设G=(V,E)为为有有向向图图,在在V中中指指定定一一点点称称为为发发点点(记记为为vs),和和另另一一点点称称为为收收点点(记记为为vt),其其余余点点叫叫做做中中间间点点.对对每每一一条条边边vivjE,对对应应一一个个非非负负实实数数Cij,称称为为它它的的容容量量.这这样样的的G称称为为容容量量网网络络,简简称称网网络络,记记作作G=(V,E,C).G中中任任一一边边vivj有有

40、流流量量fij,称称集集合合f=fij为为网络网络G上的一个上的一个流流.网络流问题网络流问题华中农业大学数学建模基地华中农业大学数学建模基地定义定义2 满足下述条件的流满足下述条件的流 f 称为称为可行流可行流：(容量限制条件容量限制条件)对每一边对每一边vivj,有有0 fij Cij;(平衡条件平衡条件)对于中间点对于中间点vk有有fik=fkj,即中即中间点间点vk的输入量的输入量=输出量输出量.如果如果f 是可行流是可行流,则对收、发点则对收、发点vt、vs有有fsi=fjt=Wf,即从即从vs点发出的物质总量点发出的物质总量=vt点输入的量点输入的量.Wf称为网络称为网络流流 f的

41、总流量的总流量.网络流问题网络流问题华中农业大学数学建模基地华中农业大学数学建模基地一个可行流一个可行流 f=f ij,当当 f ij=C ij时时,则称流则称流 f 对边对边vivj是是饱饱和和的的;当当f ijC ij时时,则称流则称流 f 对边对边是非饱和是非饱和的的.把把f ij=0的边的边称为称为零流边零流边,f ij 0的边称为的边称为非零流边非零流边.若若 为网络中从为网络中从vs到到vt的一条链的一条链(有向图中的路有向图中的路),定义链的定义链的方向是从方向是从vs到到vt,边的方向与链的方向相同称为边的方向与链的方向相同称为前向边前向边,前前向边的全体记为向边的全体记为+;

42、边的方向与链的方向相反称为边的方向与链的方向相反称为后向后向边边,后向边的全体记为后向边的全体记为.最大流问题最大流问题华中农业大学数学建模基地华中农业大学数学建模基地定义定义3 设设f是一个可行流是一个可行流,是从是从vs到到vt一条链一条链.如果满足如果满足 当当vivj+时时,0 f ij Cij,即即+中中的的每每一一条条边边都都非非饱和边饱和边;当当vivj时时,0 f ij C ij,即即 中中的的每每一一条条边边都都非非零边零边.则称则称为从为从vs到到vt的关于的关于f 的的可增广链可增广链.最大流问题最大流问题华中农业大学数学建模基地华中农业大学数学建模基地定义定义4 容量网

43、络容量网络G=(V,E,C),若点集若点集V被剖分为两被剖分为两个非空集合个非空集合S,S c=V S,vs,vt分属于分属于S,S c.则把边集则把边集(S,S c)=vivj|vivjE,viS,vjS c 称为称为G的的割集割集.若若把把一一割割集集的的边边从从网网络络中中去去掉掉,则则从从vs到到vt便便不不在在相相通通,所所以以割割集集是是从从vs到到vt的的必必经经之之路路.割割集集(S,S c)中中所所有有边边的容量之和的容量之和,称为这个称为这个割集的容量割集的容量,记为记为C(S,S c).最大流问题最大流问题华中农业大学数学建模基地华中农业大学数学建模基地定理定理1 设设

44、f 为网络为网络G=(V,E,C)的任一可行流的任一可行流,(S,S c)是剖分是剖分vs,vt 的任一割集的任一割集,则有则有Wf C(S,S c).若有可行流若有可行流 f 和割集和割集(S,S c),使得使得Wf=C(S,S c),则则f 一定是一定是G的的最大流最大流,而而(S,S c)必定是必定是G中所有割集中容量小的一个中所有割集中容量小的一个,即即最小割集最小割集.例例20：给出网络的割。：给出网络的割。2343125最大流问题最大流问题华中农业大学数学建模基地华中农业大学数学建模基地定理定理2(最大流最大流最小割定理最小割定理)任一个网络中任一个网络中G中中,从从vs到到vt的

45、的最大流的流量最大流的流量等于分割等于分割vs,vt的的最小割的容量最小割的容量.推论推论 可行流可行流f是最大流的充要条件是不存在从是最大流的充要条件是不存在从vs到到vt的的(关于关于f的的)可增广链可增广链.最大流问题最大流问题华中农业大学数学建模基地华中农业大学数学建模基地 实际问题中实际问题中,一个网络会出现下面两种情况：一个网络会出现下面两种情况：发点和收点都不止一个发点和收点都不止一个.解决的方法是再虚设一个发点解决的方法是再虚设一个发点vs和一个收点和一个收点vt,发点发点vs到所有原发点边的容量都设为无穷大到所有原发点边的容量都设为无穷大,所有原收点到所有原收点到收点收点vt

46、 边边的容量都设为无穷大的容量都设为无穷大.网络中除了边有容量外网络中除了边有容量外,点也有容量点也有容量.解决的方法是将所有有容量的点分成两个点解决的方法是将所有有容量的点分成两个点,如点如点v有容量有容量Cv,将点将点v分成两个点分成两个点v和和v,令令C(vv)=Cv.最大流问题最大流问题华中农业大学数学建模基地华中农业大学数学建模基地例例21：求网络的最大流。：求网络的最大流。探索：单向调整法：探索：单向调整法：双向调整法：双向调整法：Ford-Fulkerson算法算法最大流问题最大流问题华中农业大学数学建模基地华中农业大学数学建模基地例例22：图图6-24表明一个网络及初始可行流表

47、明一个网络及初始可行流,每条每条边上的有序数表示边上的有序数表示(C ij,f ij).求这个网络的最大求这个网络的最大流流.标号算法：标号算法：最大流问题最大流问题华中农业大学数学建模基地华中农业大学数学建模基地一般提法：一般提法：已已知知网网络络G=(V,E,C),每每条条边边vivjE除除了了已已给给容容量量Cij外外,还还给给出出了了单单位位流流量量的的费费用用bij(0).所所谓谓最最小小费费用用流流问问题题就就是是求求一一个个总总流流量量已已知知的的可可行行流流f=f ij 使使得得总总费费用用最小最小.当要求当要求f为最大流时为最大流时,此问题即为此问题即为最小费用最大流问题最小

48、费用最大流问题.最小费用流问题最小费用流问题华中农业大学数学建模基地华中农业大学数学建模基地例例23：求下列网络的最小费用流。：求下列网络的最小费用流。3,14,23,65,24,2负回路算法：负回路算法：迭加算法：迭加算法：最小费用流问题最小费用流问题华中农业大学数学建模基地华中农业大学数学建模基地 定义定义：一个工程由若干相互独立的活动组成，每个：一个工程由若干相互独立的活动组成，每个活动称为活动称为工序工序，我们，我们用顶点表示工序用顶点表示工序，如果工序，如果工序 i 完成完成之后工序之后工序 j 才能启动才能启动,则图中有一条有向边则图中有一条有向边(i,j),其其权权wi 表示工序

49、表示工序 i 所需的时间所需的时间。这样得。这样得到的赋权有向图到的赋权有向图G=（V,E）称为）称为PT图图。PT图必定不存在有向回路。图必定不存在有向回路。在在PT图中，当起点与终点不唯一时，可增加图中，当起点与终点不唯一时，可增加两个两个虚拟结点虚拟结点v0和和vn 作为新的起点与终点，作为新的起点与终点，v0和和vn表示表示虚工序虚工序，与，与v0连接的边的权为连接的边的权为0，与，与vn连接连接的边的权为原终点工序所需时间。的边的权为原终点工序所需时间。PT图图华中农业大学数学建模基地华中农业大学数学建模基地 例例24 24 一项工程由一项工程由1313道工序组成道工序组成,所需时间

50、所需时间(单位：单位：天天)及先行工序如下表所示及先行工序如下表所示(P172).(P172).工序序号工序序号 A B C D E F G H I J K L MA B C D E F G H I J K L M所需时间所需时间 2 6 3 2 4 3 8 4 2 3 2 5 62 6 3 2 4 3 8 4 2 3 2 5 6先行工序先行工序 -A A A A B B C,DC,D D D D D D D G,HG,H G G H,EH,E J J K K 试问这项工程至少需要多少天才能完成试问这项工程至少需要多少天才能完成?那些工程不那些工程不能延误能延误?那些工程可以延误那些工程可以延