数模培训-图论模型ppt课件

图图 论论 模模 型型主讲：费文龙F数学建模培训5/25/20241南京信息工程大学数理学院费文龙图论模型主讲：费文龙数学建模培训8/5/2023图论模型1.图论基本概念2.最短路径算法3.最小生成树算法4.遍历性问题5.二分图与匹配6.网络流问题7.关键路径问题8.系统监控模型9.着色模型5/25/20242南京信息工程大学数理学院费文龙图论模型图论基本概念网络流问题8/5/20232南京信息工程1、图论的基本概念、图论的基本概念ABCD哥尼斯堡七桥示意图哥尼斯堡七桥示意图问题问题1(1(哥尼斯堡七桥哥尼斯堡七桥问题问题):):能否从任一陆地出发通过每座桥恰好一次而能否从任一陆地出发通过每座桥恰好一次而回到出发点？回到出发点？5/25/20243南京信息工程大学数理学院费文龙1、图论的基本概念ABCD哥尼斯堡七桥示意图问题1(哥尼斯堡ABDC七桥问题模拟图七桥问题模拟图欧拉指出：欧拉指出：如果每块陆地所连接的桥都是偶数座，则如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而从任一陆地出发，必能通过每座桥恰好一次而回到出发地回到出发地.5/25/20244南京信息工程大学数理学院费文龙ABDC七桥问题模拟图欧拉指出：8/5/20234南京信息工问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题问题):):十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，个城市，能否从某个城市出发在十二面体上依次经过每个能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）5/25/20245南京信息工程大学数理学院费文龙问题2(哈密顿环球旅行问题):哈密顿圈（环球旅行游戏）8/5问题问题3(3(四色问题四色问题):):对任何一张地图进行着色，两个共同边界的国家染对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了不同的颜色，则只需要四种颜色就够了.问题问题4(4(关键路径问题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这这些工序相互约束些工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,一个工序一个工序才能开始才能开始.即它们之间存在完成的先后次序关系即它们之间存在完成的先后次序关系,一般一般认为这些关系是预知的认为这些关系是预知的,而且也能够预计完成每个工序而且也能够预计完成每个工序所需要的时间所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目才能够完成整个工程项目,影响工程进度的要害工序是影响工程进度的要害工序是哪几个？哪几个？5/25/20246南京信息工程大学数理学院费文龙问题3(四色问题):问题4(关键路径问题):8/5/2023图的定义图的定义 图论中的图论中的“图图”并不是通常意义下的几何图形或物并不是通常意义下的几何图形或物体的形状图体的形状图,而是以一种抽象的形式来表达一些确定的而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统事物之间的联系的一个数学系统.定义定义1一个有序二元组一个有序二元组(V,E)称为一个称为一个图图,记为记为G=(V,E),其中其中 V称为称为G的顶点集的顶点集,V,其元素称为其元素称为顶点顶点或或结点结点,简称简称点点;E称为称为G的边集的边集,其元素称为其元素称为边边,它联结它联结V 中的两中的两个点个点,如果这两个点是无序的如果这两个点是无序的,则称该边为则称该边为无向边无向边,否则否则,称为称为有向边有向边.如果如果V=v1,v2,vn是有限非空点集是有限非空点集,则称则称G为为有限图有限图或或n阶图阶图.5/25/20247南京信息工程大学数理学院费文龙图的定义图论中的“图”并不是通常意义下的几何图形或物 如果如果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的的始点始点和和终点终点.该图称为该图称为(n,m)图图5/25/20248南京信息工程大学数理学院费文龙如果E的每一条边都是无向边,则称G为无向图(如图1 对于一个图对于一个图G=(V,E),人们常用图形来表示人们常用图形来表示它它,称其为称其为图解图解.凡是有向边凡是有向边,在图解上都用箭在图解上都用箭头标明其方向头标明其方向.例如例如,设设V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4,则则G=(V,E)是一个有是一个有4个顶点和个顶点和6条边的图条边的图,G的图解如下图所示的图解如下图所示.5/25/20249南京信息工程大学数理学院费文龙对于一个图G=(V,E),人们常用图形来表 一个图会有许多外形不同的图解一个图会有许多外形不同的图解,下面两个图表示下面两个图表示同一个图同一个图G=(V,E)的图解的图解.其中其中V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4.这两个图互为这两个图互为同构图同构图,今后将不计较这种外形上的差今后将不计较这种外形上的差别别,而用一个容易理解的、确定的图解去表示一个图而用一个容易理解的、确定的图解去表示一个图.5/25/202410南京信息工程大学数理学院费文龙一个图会有许多外形不同的图解,下面两个图表示同一个 有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点,有一个公共端点的有一个公共端点的边称为边称为相邻边相邻边.边和它的端点称为边和它的端点称为互相关联互相关联.常用常用d(v)表示表示图图G中与顶点中与顶点v关联的边的数目关联的边的数目,d(v)称为顶点称为顶点v的的度数度数.对对于有向图于有向图,还有还有出度出度和和入度入度之分之分.用用N(v)表示图表示图G中所有与顶点中所有与顶点v相邻的顶点的集合相邻的顶点的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.握手定理：握手定理：5/25/202411南京信息工程大学数理学院费文龙有边联结的两个点称为相邻的点,有一个公共端点的边称我们今后只讨论我们今后只讨论有限简单图有限简单图：(1)(1)顶点个数是有限的顶点个数是有限的;(2)(2)任意一条边有且只有两个不同的点与它相互关联任意一条边有且只有两个不同的点与它相互关联;(3)(3)若是无向图若是无向图,则任意两个顶点最多只有一条边与则任意两个顶点最多只有一条边与之相联结之相联结;(4)(4)若是有向图若是有向图,则任意两个顶点最多只有两条边与则任意两个顶点最多只有两条边与之相联结之相联结.当两个顶点有两条边与之相联结时，这两条当两个顶点有两条边与之相联结时，这两条边的方向相反边的方向相反.如果某个有限图不满足如果某个有限图不满足(2)(3)(4),(2)(3)(4),可在某条边上增设可在某条边上增设顶点使之满足顶点使之满足.5/25/202412南京信息工程大学数理学院费文龙我们今后只讨论有限简单图：(1)顶点个数是有限的;8/定义定义2若将图若将图G的每一条边的每一条边e都对应一个实数都对应一个实数F(e),则称则称F(e)为该边的为该边的权权,并称图并称图G为为赋权图赋权图(网络网络),记为记为G=(V,E,F).定义定义3任意两点均有通路的图称为任意两点均有通路的图称为连通图连通图.定义定义4连通而无圈的图称为连通而无圈的图称为树树,常用常用T表示树表示树.5/25/202413南京信息工程大学数理学院费文龙定义2若将图G的每一条边e都对应一个实数F(e)例例 一摆渡人欲将一只狼一摆渡人欲将一只狼,一头羊一头羊,一篮菜从河西渡过一篮菜从河西渡过河到河东河到河东.由于船小由于船小,一次只能带一物过河，并且狼与羊一次只能带一物过河，并且狼与羊,羊与菜不能独处羊与菜不能独处.给出渡河方法给出渡河方法.解解：用四维：用四维0-10-1向量表示向量表示(人人,狼狼,羊羊,菜菜)在河西岸的在河西岸的状态状态(在河西岸则分量取在河西岸则分量取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个个状态状态向量作为顶点向量作为顶点,将可能互相转移将可能互相转移的状态用线段连接起来构成一个图的状态用线段连接起来构成一个图.根据此图便可找到根据此图便可找到渡河方法渡河方法.5/25/202414南京信息工程大学数理学院费文龙例一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到(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,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的的路路.从图中易得到两条从图中易得到两条路路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.5/25/202415南京信息工程大学数理学院费文龙(1,1,1,1)(1,1,1,0)(1,1,0,1图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵 邻接矩阵表示了点与点之间的邻接关系邻接矩阵表示了点与点之间的邻接关系.一个一个n阶图阶图G的邻接矩阵的邻接矩阵A=(aij)nn,其中其中 5/25/202416南京信息工程大学数理学院费文龙图的矩阵表示邻接矩阵邻接矩阵表示了点与点之间无向图无向图G的邻接矩阵的邻接矩阵A是一个对称矩阵是一个对称矩阵.权矩阵权矩阵 一个一个n阶赋权图阶赋权图G=(V,E,F)的权矩阵的权矩阵A=(aij)nn,其中其中 有限简单图基本有限简单图基本上可用权矩阵来上可用权矩阵来表示表示.5/25/202417南京信息工程大学数理学院费文龙无向图G的邻接矩阵A是一个对称矩阵.权矩阵无向图无向图G的权矩阵的权矩阵A是一个对称矩阵是一个对称矩阵.5/25/202418南京信息工程大学数理学院费文龙无向图G的权矩阵A是一个对称矩阵.8/5/202318南京 关联矩阵（略）关联矩阵（略）一个有一个有m条边的条边的n阶有向图阶有向图G的的关联矩阵关联矩阵A=(aij)nm,其中其中 若若vi是是ej的始点的始点;若若vi是是ej的终点的终点;若若vi与与ej不关联不关联.有向图的关联矩阵每列的元素中有且仅有一个有向图的关联矩阵每列的元素中有且仅有一个1,1,有有且仅有一个且仅有一个-1.1.5/25/202419南京信息工程大学数理学院费文龙关联矩阵（略）一个有m条边的n阶有向图G的关 一个有一个有m条边的条边的n阶无向图阶无向图G的关联矩阵的关联矩阵A=(aij)nm,其中其中 若若vi与与ej关联关联;若若vi与与ej不关联不关联.无向图的关联矩阵每列的元素中有且仅有两个无向图的关联矩阵每列的元素中有且仅有两个1.1.5/25/202420南京信息工程大学数理学院费文龙一个有m条边的n阶无向图G的关联矩阵A=(aij2 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的的最短路最短路.5/25/202421南京信息工程大学数理学院费文龙2、最短路径算法定义1设P(u,v)是赋权图G重要性质：重要性质：若若v0v1vm 是是图图G中从中从v0到到vm的最短路的最短路,则则 1km,v0v1vk 必为必为G中从中从v0到到vk的最短路的最短路.即：最短路是一条路，且最短路的任一段也是最短即：最短路是一条路，且最短路的任一段也是最短路路.求非负赋权图求非负赋权图G中某一点到其它各点最短路，一般中某一点到其它各点最短路，一般用用Dijkstra标号算法；求非负赋权图上任意两点间的最标号算法；求非负赋权图上任意两点间的最短路，一般用短路，一般用Floyd算法算法.这两种算法均适用于有向非负赋权图这两种算法均适用于有向非负赋权图.下面分别介绍两种算法的基本过程下面分别介绍两种算法的基本过程.5/25/202422南京信息工程大学数理学院费文龙重要性质：若v0v1vm是图G中从v0到vDijkstra算法算法l指标指标（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的最短路径，因为最短路径中可能包含的最短路径，因为最短路径中可能包含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为最小指标所为最小指标所在的点在的点,即即: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)5/25/202423南京信息工程大学数理学院费文龙Dijkstra算法指标（a为起点）设T为V的子集Dijkstra算法算法（求（求（求（求a 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=,则算法结束;否则,令P=PUx,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)为图的权矩阵）5/25/202424南京信息工程大学数理学院费文龙Dijkstra算法（求a点到其他点的最短路径）1、初始化，改进改进Dijkstra算法算法（求（求（求（求a 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=PUx,T=T-x按照公式l(t)=minl(t),l(x)+w(x,t),计算T中每一个结点t关于P的指标.若l(x)+w(x,t)dik+dkj,则删除则删除vi到到vj的连线的连线.得到得到5/25/202429南京信息工程大学数理学院费文龙以下仅从图上进行直观操作.根据若dik+dkj从上图中容易得到任意两点间的最短路从上图中容易得到任意两点间的最短路.例如例如,v1到到v6的路有三条：的路有三条：v1v0v3v2v6(长度为长度为12),12),v1v4v5v2v6(长度为长度为7),7),v1v4v7v6(长度为长度为12).12).5/25/202430南京信息工程大学数理学院费文龙从上图中容易得到任意两点间的最短路.例如,v1到v6的路有三例例 设备更新问题设备更新问题 某企业每年年初某企业每年年初,都要作出决定都要作出决定,如果继续使用旧设如果继续使用旧设备备,要付维修费；若购买一台新设备要付维修费；若购买一台新设备,要付购买费要付购买费.试制定试制定一个一个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 年后的维修费年后的维修费,V=v1,v2,v6,点点vi表示第表示第i 年年初购进一台新设备年年初购进一台新设备,虚设一个点虚设一个点v6表示第表示第5 5年年底年年底.E=vivj|1ij6.5/25/202431南京信息工程大学数理学院费文龙例设备更新问题某企业每年年初,都要作出决定,如果 这样上述设备更新问题就变为：在有向赋权图这样上述设备更新问题就变为：在有向赋权图G=(V,E,F)(图解如下图解如下)中求中求v1到到v6的最短路问题的最短路问题.5/25/202432南京信息工程大学数理学院费文龙这样上述设备更新问题就变为：在有向赋权图G=(V 由实际问题可知由实际问题可知,设备使用三年后应当更新设备使用三年后应当更新,因此删因此删除该图中除该图中v1到到v5,v1到到v6,v2到到v6的连线；又设备使用一年的连线；又设备使用一年后就更新则不划算后就更新则不划算,因此再删除该图中因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6和和v1v4v6.而这两条路都是而这两条路都是v1到到v6的最短路的最短路.5/25/202433南京信息工程大学数理学院费文龙由实际问题可知,设备使用三年后应当更新,因此删除该图3 3、最小生成树、最小生成树 由树的定义不难知道由树的定义不难知道,任意一个连通的任意一个连通的(n,m)图图G适适当去掉当去掉m-n+1条边后条边后,都可以变成树都可以变成树,这棵树称为图这棵树称为图G的的生成树生成树.设设T是图是图G的一棵生成树的一棵生成树,用用F(T)表示树表示树T中所有边中所有边的权数之和的权数之和,F(T)称为称为树树T的权的权.一个连通图一个连通图G的生成树一般不止一棵的生成树一般不止一棵,图图G的所有生的所有生成树中权数最小的生成树称为图成树中权数最小的生成树称为图G的的最小生成树最小生成树.求最小生成树问题有很广泛的实际应用求最小生成树问题有很广泛的实际应用.例如例如,把把n个乡镇用高压电缆连接起来建立一个电网个乡镇用高压电缆连接起来建立一个电网,使所用的电使所用的电缆长度之和最短缆长度之和最短,即费用最小即费用最小,就是一个求最小生成树问就是一个求最小生成树问题题.5/25/202434南京信息工程大学数理学院费文龙3、最小生成树由树的定义不难知道,任意一个连通的Kruskal算算法：法：从未选入树中的边中选取权重最小的且不从未选入树中的边中选取权重最小的且不构成回路的边加入到树中构成回路的边加入到树中.（判断回路比较麻烦）（判断回路比较麻烦）Prim算法：算法：把结点分成两个集合，已加入树中的把结点分成两个集合，已加入树中的(P)(P)和和未加入树中的未加入树中的(Q)(Q)，然后每次选择一个点在，然后每次选择一个点在P P中一个点在中一个点在Q Q中的权重最小的边，加入树中，并把相应点加入中的权重最小的边，加入树中，并把相应点加入P P中。中。其最小生成树如下：其最小生成树如下：类似地类似地,可定义连通图可定义连通图G 的最大生成树的最大生成树.5/25/202435南京信息工程大学数理学院费文龙Kruskal算法：从未选入树中的边中选取权重最小的且不构成例例 选址问题选址问题 现准备现准备在在n 个个居民点居民点v1,v2,vn中设置一银行中设置一银行.问设在哪个点问设在哪个点,可使最大服务距离最小可使最大服务距离最小?若设置两个银若设置两个银行行,问设在哪两个点问设在哪两个点?模型假设模型假设 假设各假设各个个居民点都有条件设置银行居民点都有条件设置银行,并并有路相连有路相连,且路长已知且路长已知.模型建立与求解模型建立与求解 用用Floyd算法求出任意两算法求出任意两个个居民居民点点vi,vj 之间的最短距离之间的最短距离,并用并用dij 表示表示.设置一个银行设置一个银行,银行设银行设在在vi 点点的最大服务距离为的最大服务距离为5/25/202436南京信息工程大学数理学院费文龙例选址问题现准备在n个居民点v1,v2,求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在vk 点点,可使最大服务可使最大服务距离最小距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使最大服使最大服务距离最小务距离最小.记记则则s,t 满足：满足：进一步进一步,若设置多个银行呢？若设置多个银行呢？5/25/202437南京信息工程大学数理学院费文龙求k,使即若设置一个银行,则银行设在vk点,可使4、遍历性问题一、欧拉图一、欧拉图lG=(V,E)为一连通无向图l经过G中每条边至少一次的回路称为巡回巡回；l经过G中每条边正好一次的巡回称为欧拉巡回欧拉巡回；l存在欧拉巡回的图称为欧拉图。欧拉图。二、中国邮递员问题二、中国邮递员问题（CPPchinesepostmanproblem）l一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？l这一问题是我国管梅谷教授1962年首先提出，国际上称之为中国邮递员问题。5/25/202438南京信息工程大学数理学院费文龙4、遍历性问题一、欧拉图8/5/202338南京信息工程大学l解法：解法：若本身就是欧拉图，则直接可以找到一条欧拉巡回若本身就是欧拉图，则直接可以找到一条欧拉巡回就是本问题的解。就是本问题的解。若不是欧拉图，必定有偶数个奇度数结点，在这些若不是欧拉图，必定有偶数个奇度数结点，在这些奇度数点之间添加一些边，使之变成欧拉图，再找奇度数点之间添加一些边，使之变成欧拉图，再找出一个欧拉巡回。出一个欧拉巡回。l具体解法：具体解法：Fleury算法算法+Edmonds最小对集算最小对集算法法5/25/202439南京信息工程大学数理学院费文龙8/5/202339南京信息工程大学数理学院费文龙三、哈密尔顿图三、哈密尔顿图lG=(V,E)为一连通无向图l经过G中每点一次且正好一次的路径称为哈密尔顿路径哈密尔顿路径；l经过G中每点一次且正好一次的回路称为哈密尔顿回路哈密尔顿回路；l存在哈密尔顿回路的图称为哈密尔顿图。哈密尔顿图。四、旅行商问题四、旅行商问题（TSPtravelingsalesmanproblem）l一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线？即：从驻地出发，经过每个城市恰好一次，最后返回驻地（最小哈密尔顿回路）（最小哈密尔顿回路）l对于n个节点的旅行商问题，n个节点的任意一个全排列都是问题的一个可能解（假设任意两个点之间都有边）。G个节点的全排列有(n-1)!个，因此间题归结为在(n-1)!个回路中选取最小回路。lTSP问题的解法属于NPNP完全问题完全问题，一般只研究其近似解法5/25/202440南京信息工程大学数理学院费文龙三、哈密尔顿图8/5/202340南京信息工程大学数理学院l最邻近算法最邻近算法(1)选取任意一个点作为起始点,找出与该点相关联的权重最小的边,形成一条初始路径.(2)找出与最新加入到路径中的点相关联的权重最小的边加入到路径中,且要求不再路径中产生回路.(3)重复(2)直到所有的结点都加入到路径中.(4)将起点和最后加入的结点之间的边加入到路径中,形成Hamilton回路.l其他数值算法：其他数值算法：人工神经元方法，遗传算法等等5/25/202441南京信息工程大学数理学院费文龙最邻近算法8/5/202341南京信息工程大学数理学院费文5 5、二分图与匹配、二分图与匹配 定义定义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).5/25/202442南京信息工程大学数理学院费文龙5、二分图与匹配定义1设X,Y都是非空有限集,定义定义2 2 设设G=(X,Y,E)为二部图为二部图,且且M E.若若M中任意两条边中任意两条边在在G中均不邻接中均不邻接,则称则称M是是二部图二部图G的一个的一个匹配匹配.定义定义3 3 设设M是二部图是二部图G的一个匹配的一个匹配,如果如果G的每一个点都是的每一个点都是M中边的顶中边的顶点点,则称则称M是二部图是二部图G的的完美匹配完美匹配；如果如果G中没有另外的匹配中没有另外的匹配M0,使使|M0|M|,|,则称则称M是二部图是二部图G的的最大匹配最大匹配.在二部赋权图在二部赋权图G=(X,Y,E,F)中中,权数最大的最大匹配权数最大的最大匹配M称为称为二部赋权图二部赋权图G的的最佳匹配最佳匹配.显然显然,每个完美匹配都是最大匹配每个完美匹配都是最大匹配,反之不一定成立反之不一定成立.5/25/202443南京信息工程大学数理学院费文龙定义2设G=(X,Y,E)为二部图,且M工作安排问题之一工作安排问题之一 给给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,并且当且仅当工作人员并且当且仅当工作人员xi胜任工胜任工作作yj时时,xi与与yj才相邻才相邻.于是于是,问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配.因为因为|X|=|Y|,所以完美匹配即为最大匹配所以完美匹配即为最大匹配.5/25/202444南京信息工程大学数理学院费文龙工作安排问题之一给n个工作人员x1,x2,求二部图求二部图求二部图求二部图G G=(=(X X,Y Y,E E)的最大匹配算法的最大匹配算法的最大匹配算法的最大匹配算法(匈牙利算法匈牙利算法匈牙利算法匈牙利算法,交替链交替链交替链交替链算法算法算法算法)迭代步骤迭代步骤迭代步骤迭代步骤:从从G的任意匹配的任意匹配M开始开始.将将X中中M的所有的所有非饱和点非饱和点都给以标号都给以标号0 0和标记和标记*,*,转向转向.M的非饱和点即非的非饱和点即非M的某条边的顶点的某条边的顶点.若若X中所有有标号的点都已去掉了标记中所有有标号的点都已去掉了标记*,*,则则M是是G的最大的最大匹配匹配.否则任取否则任取X中一个既有标号又有标记中一个既有标号又有标记*的点的点xi,去掉去掉xi的标的标记记*,*,转向转向.找出在找出在G中所有与中所有与xi邻接的点邻接的点yj,若所有这样的若所有这样的yj都已有标都已有标号号,则转向则转向,否则转向否则转向.5/25/202445南京信息工程大学数理学院费文龙求二部图G=(X,Y,E)的最大匹配算法 对与对与xi邻接且尚未给标号的邻接且尚未给标号的yj都给定标号都给定标号i.若所有的若所有的yj 都是都是M的的饱和点饱和点,则转向则转向,否则逆向返回否则逆向返回.即由即由其中其中M的任一个非饱和点的任一个非饱和点yj 的标号的标号i 找到找到xi,再由再由xi 的标号的标号k 找到找到yk,最后由最后由yt 的标号的标号s找到标号为找到标号为0 0的的xs时结束时结束,获得获得M-增广路增广路xs ytxi yj,记记P=xs yt,xi yj ,重新记重新记M为为M P,转向转向.不必理会不必理会M-增广路增广路的定义的定义.M P=MP MP,是对称差是对称差.将将yj在在M中与之邻接的点中与之邻接的点xk,给以标号给以标号j 和标记和标记*,*,转向转向.5/25/202446南京信息工程大学数理学院费文龙对与xi邻接且尚未给标号的yj都给定标号i.例例 求下图所示二部图求下图所示二部图G的最大匹配的最大匹配.解解 取初始匹配取初始匹配M0=x2y2,x3y3,x5y5(上图粗线所示上图粗线所示).).给给X中中M0的两个非饱和点的两个非饱和点x1,x4都给以标号都给以标号0 0和标记和标记*(*(如如下图所示下图所示).).去掉去掉x1的标记的标记*,将与将与x1邻接的两个点邻接的两个点y2,y3都给以标号都给以标号1.1.因为因为y2,y3都是都是M0的两个饱和点的两个饱和点,所以将它们在所以将它们在M0中邻接的两个中邻接的两个点点x2,x3都给以相应的标号和标记都给以相应的标号和标记*(如下图所示如下图所示).5/25/202447南京信息工程大学数理学院费文龙例求下图所示二部图G的最大匹配.解取初始匹配M0 去掉去掉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,x3y3,x5y5,则则M1是比是比M多一边的匹配多一边的匹配(如下图所示如下图所示).5/25/202448南京信息工程大学数理学院费文龙去掉x2的标记*,将与x2邻接且尚未给标号的三 再给再给X中中M1的非饱和点的非饱和点x4给以标号给以标号0和标记和标记*,然后去掉然后去掉x4的的标记标记*,将与将与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的每个点的匹配的每个点的匹配,当然也不存在完美匹配当然也不存在完美匹配.5/25/202449南京信息工程大学数理学院费文龙再给X中M1的非饱和点x4给以标号0和标记*,工作安排问题之二工作安排问题之二 给给n个工作人员个工作人员x1,x2,xn安排安排n项工作项工作y1,y2,yn.如果每个工作人员工作效率不同如果每个工作人员工作效率不同,要求工作分配的同时考虑总要求工作分配的同时考虑总效率最高效率最高.我们构造一个二部赋权图我们构造一个二部赋权图G=(X,Y,E,F),这里这里X=x1,x2,xn,Y=y1,y2,yn,F(xiyj)为工作人员为工作人员xi胜任工胜任工作作yj时的工作效率时的工作效率.则问题转化为：求二部赋权图则问题转化为：求二部赋权图G的最佳匹配的最佳匹配.在求在求G的最佳匹配时的最佳匹配时,总可以假设总可以假设G为完备二部赋权图为完备二部赋权图.若若xi与与yj不相邻不相邻,可令可令F(xiyj)=0.同样地同样地,还可虚设点还可虚设点x或或y,使使|X|=|Y|.如此就将如此就将G转化为完备二部赋权图转化为完备二部赋权图,而且不会影响结果而且不会影响结果.5/25/202450南京信息工程大学数理学院费文龙工作安排问题之二给n个工作人员x1,x2,定义定义 设设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)为完备的二部赋权图为完备的二部赋权图,L是其一个初始可是其一个初始可行点标记行点标记,通常取通常取 L(x)=max F(x y)|yY,xX,L(y)=0,yY.5/25/202451南京信息工程大学数理学院费文龙定义设G=(X,Y,E,F)为完备的二部赋M是是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,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=M P,转向转向.5/25/202452南京信息工程大学数理学院费文龙M是GL的一个匹配.若X的每个点都是饱和的,则M是最佳6 6、网络流问题、网络流问题 定义定义1 1 设设G=(V,E)为有向图为有向图,在在V中指定一点称为中指定一点称为发点发点(记为记为vs),),和另一点称为和另一点称为收点收点(记为记为vt),),其余点叫做中间点其余点叫做中间点.对每一条边对每一条边vivjE,对应一个非负实数对应一个非负实数Cij,称为它的称为它的容量容量.这样的这样的G称为称为容量网容量网络络,简称简称网络网络,记作记作G=(V,E,C).定义定义2 2 网络网络G=(V,E,C)中任一条边中任一条边vivj有流量有流量fij,称集合称集合f=fij 为网络为网络G上的一个上的一个流流.满足下述条件的流满足下述条件的流f 称为称为可行流可行流：(限制条件限制条件)对每一边对每一边vivj,有有0fij Cij;(平衡条件平衡条件)对于中间点对于中间点vk有有fik=fkj ,即中间点即中间点vk的输入的输入量量=输出输出量量.5/25/202453南京信息工程大学数理学院费文龙6、网络流问题定义1设G=(V,E)为有向 如果如果f 是可行流是可行流,则对收、发点则对收、发点vt、vs有有fsi=fjt=Wf,即从即从vs点发出的物质总量点发出的物质总量=vt点输入的量点输入的量.Wf 称为网络流称为网络流f 的总流量的总流量.上述概念可以这样来理解上述概念可以这样来理解,如如G是一个运输网络是一个运输网络,则发点则发点vs表示表示发送站发送站,收点收点vt表示接收站表示接收站,中间点中间点vk表示中间转运站表示中间转运站,可行流可行流fij 表表示某条运输线上通过的运输量示某条运输线上通过的运输量,容量容量Cij表示某条运输线能承担的最表示某条运输线能承担的最大运输量大运输量,Wf 表示运输总量表示运输总量.可行流总是存在的可行流总是存在的.比如所有边的流量比如所有边的流量fij=0就是一个可行流就是一个可行流(称为零流称为零流).).5/25/202454南京信息工程大学数理学院费文龙如果f是可行流,则对收、发点vt、vs有 所谓所谓最大流问题最大流问题就是在容量网络中就是在容量网络中,寻找流量最大的可行流寻找流量最大的可行流.实际问题中实际问题中,一个网络会出现下面两种情况：一个网络会出现下面两种情况：发点和收点都不止一个发点和收点都不止一个.解决的方法是再虚设一个发点解决的方法是再虚设一个发点vs和一个收点和一个收点vt,发点发点vs到所有到所有原发点边的容量都设为无穷大原发点边的容量都设为无穷大,所有原收点到收点所有原收点到收点vt 边的容量都边的容量都设为无穷大设为无穷大.网络中除了边有容量外网络中除了边有容量外,点也有容量点也有容量.解决的方法是将所有有容量的点分成两个点解决的方法是将所有有容量的点分成两个点,如点如点v有容量有容量Cv,将点将点v分成两个点分成两个点v和和v,令令C(vv)=Cv.5/25/202455南京信息工程大学数理学院费文龙所谓最大流问题就是在容量网络中,寻找流量最大的可行流最小费用流问题最小费用流问题最小费用流问题最小费用流问题 这里我们要进一步探讨不仅要使网上的流达到最大这里我们要进一步探讨不仅要使网上的流达到最大,或者达或者达到要求的预定值到要求的预定值,而且还要使运输流的费用是最小的而且还要使运输流的费用是最小的,这就是最小这就是最小费用流问题费用流问题.最小费用流问题的一般提法：最小费用流问题的一般提法：已知网络已知网络G=(V,E,C),每条边每条边vivjE 除了已给容量除了已给容量Cij外外,还还给出了单位流量的费用给出了单位流量的费用bij(0).).所谓最小费用流问题就是求一个总流量已知的可行流所谓最小费用流问题就是求一个总流量已知的可行流f=f ij 使得总费用使得总费用最小最小.5/25/202456南京信息工程大学数理学院费文龙最小费用流问题这里我们要进一步探讨不仅要使网上的流 特别地特别地,当要求当要求f 为最大流时为最大流时,即为即为最小费用最大流问题最小费用最大流问题.设网络设网络G=(V,E,C),取初始可行流取初始可行流f 为零流为零流,求解最小费用流求解最小费用流问题的迭代步骤：问题的迭代步骤：构造有向赋权图构造有向赋权图Gf=(V,Ef,F),),对于任意的对于任意的vivjE,Ef,F 的的定义如下：定义如下：当当f ij=0时时,vivjEf,F(vivj)=bij;当当f ij=Cij时时,vjviEf,F(vjvi)=-bij;当当0f ijCij时时,vivjEf,F(vivj)=bij,vjviEf,F(vjvi)=-bij.然后然后转向转向.5/25/202457南京信息工程大学数理学院费文龙特别地,当要求f为最大流时,即为最小费用最大流 求出含有负权的有向赋权图求出含有负权的有向赋权图Gf=(V,Ef,F)中发点中发点vs到收点到收点vt的最短路的最短路 ,若最若最短路短路 存在转向存在转向;否则否则f是所求的最小费用最大是所求的最小费用最大流流,停止停止.增流增流.vivj与与 相同相同,vivj与与 相反相反.令令=min ij|vivj ,重新定义流重新定义流f=f ij 为为其它情况不变其它情况不变.如果如果Wf 大于或等于预定的流量值大于或等于预定的流量值,则适当减少则适当减少 值值,使使Wf 等等于预定的流量值于预定的流量值,那么那么f 是是所求的最小费用流所求的最小费用流,停止停止;否则转向否则转向.5/25/202458南京信息工程大学数理学院费文龙求出含有负权的有向赋权图Gf=(V,Ef,下面介绍求解有向赋权图下面介绍求解有向赋权图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)都是从都是从v1到到vi的最短路长度的上界的最短路长度的上界.若若不存在负长回路不存在负长回路,则从则从v1到到vi的最短路长度是的最短路长度是 (i)的下界的下界,经过经过n-1次迭代后次迭代后 (i)将保持不变将保持不变.若在第若在第n次迭代后次迭代后 (i)仍在变化时仍在变化时,说明存在负长回路说明存在负长回路.5/25/202459南京信息工程大学数理学院费文龙下面介绍求解有向赋权图G=(V,E,F)中7 7、关键路径问题（拓扑排序）、关键路径问题（拓扑排序）一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装小至组装一台机床一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这些工序相互约束这些工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,一个工序才能开始一个工序才能开始.即它们之间存在即它们之间存在完成的先后次序关系完成的先后次序关系,一般认为这些关系是预知的一般认为这些关系是预知的,而且也能够而且也能够预计完成每个工序所需要的时间预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目成整个工程项目,影响工程进度的要害工序是哪几个？影响工程进度的要害工序是哪几个？5/25/202460南京信息工程大学数理学院费文龙7、关键路径问题（拓扑排序）一项工程任务,大到建造一PT(Potentialtaskgraph)PT(Potentialtaskgraph)图图图图 在在PT(Potentialtaskgraph)图中图中,用结点表示工序用结点表示工序,如果工序如果工序i 完成之后工序完成之后工序j 才能启动才能启动,则图中有一条有向边则图中有一条有向边(i,j),),其长度其长度wi 表示工序表示工序i 所需的时间所需的时间.这种图必定不存在有向回路这种图必定不存在有向回路,否则某些工序将在自身完成之后否则某些工序将在自身完成之后才能开始才能开始,这显然不符合实际情况这显然不符合实际情况.在在PT图中增加两个虚拟结点图中增加两个虚拟结点v0和和vn,使所有仅为始点的结点都使所有仅为始点的结点都直接与直接与v0联结联结,v0为新增边的始点为新增边的始点,这些新增边的权都设为这些新增边的权都设为0;使所使所有仅为终点的结点都直接与有仅为终点的结点都直接与vn联结联结,vn为新增边的终点为新增边的终点.这样得到这样得到的图的图G仍然不存在有向回路仍然不存在有向回路.5/25/202461南京信息工程大学数理学院费文龙PT(Potentialtaskgraph)图在 例例 一项工程由一项工程由1313道工序组成道工序组成,所需时间所需时间(单位：天单位：天)及先行工及先行工序如下表所示序如下表所示(P172).(P172).工序序号工序序号 A B C D E F G H I A B C D E F G H I所需时间所需时间 2 6 3 2 4 3 8 4 2 2 6 3 2 4 3 8 4 2先行工序先行工序 A A B C,D D D D G,H A A B C,D D D D G,H工序序号工序序号 J K L M J K L M所需时间所需时间 3 8 5 6 3 8 5 6先行工序先行工序 G H,E J K G H,E J K 试问这项工程至少需要多少天才能完成试问这项工程至少需要多少天才能完成?那些工程不能延误那些工程不能延误?那些工程可以延误那些工程可以延误?最多可延误多少天最多可延误多少天?5/25/202462南京信息工程大学数理学院费文龙例一项工程由13道工序组成,所需时间(单位：天)先作出该工程的先作出该工程的PT图图.由于除了工序由于除了工序A A外，均有先行工序外，均有先行工序,因因此不必虚设虚拟结点此不必虚设虚拟结点v0.A AB B2 22 2C C6 6D D3 3E E2 2F F2 2G G2 2H H2 2K K4 4N N3 3I I8 8J J8 84 44 42 2L L3 3M M8 85 56 6 在在PT图中图中,容易看出各工序先后完成的顺序及时间容易看出各工序先后完成的顺序及时间.虚拟结点虚拟结点5/25/202463南京信息工程大学数理学院费文龙先作出该工程的PT图.由于除了工序A外，均有先行工序A AB B2 22 2C C6 6D D3 3E E2 2F F2 2G G2 2H H2 2K K4 4N N3 3I I8 8J J8 84 44 42 2L L3 3M M8 85 56 6 这项工程至少需这项工程至少需要多少天才能完成要多少天才能完成?就是要求就是要求A A到到N N的最长路的最长路,此路径称为此路径称为关键路径关键路径.那些工程不能延误那些工程不能延误?那些工程可以延误那些工程可以延误?最多可延误多少天最多可延误多少天?关键路径上的那些工程不能延误关键路径上的那些工程不能延误.5/25/202464南京信息工程大学数理学院费文龙AB22C6D3E2F2G2H2K4N3I8J8442L3M关键路径关键路径关键路径关键路径(最长路径最长路径最长路径最长路径)算法算法算法算法 定理定理 若有向图若有向图G中中不存在有向回路不