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

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

1、2022-8-1南京信息工程大学数理学院 费文龙1图图 论论 模模 型型主讲：费文龙F数学建模培训2022-8-1南京信息工程大学数理学院 费文龙21.图论基本概念2.最短路径算法3.最小生成树算法4.遍历性问题5.二分图与匹配6.网络流问题7.关键路径问题8.系统监控模型9.着色模型2022-8-1南京信息工程大学数理学院 费文龙3ABCD哥尼斯堡七桥示意图哥尼斯堡七桥示意图问题问题1(1(哥尼斯堡七桥哥尼斯堡七桥问题问题):): 能否从任一陆地出发通过每座桥恰好一次而能否从任一陆地出发通过每座桥恰好一次而回到出发点？回到出发点？2022-8-1南京信息工程大学数理学院 费文龙4ABDC七桥

2、问题模拟图七桥问题模拟图欧拉指出：欧拉指出： 如果每块陆地所连接的桥都是偶数座，则如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而从任一陆地出发，必能通过每座桥恰好一次而回到出发地回到出发地. .2022-8-1南京信息工程大学数理学院 费文龙5问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题问题):): 十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，个城市，能否从某个城市出发在十二面体上依次经过每个能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅

3、行游戏）2022-8-1南京信息工程大学数理学院 费文龙6问题问题3(3(四色问题四色问题):): 对任何一张地图进行着色，两个共同边界的国家染对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了不同的颜色，则只需要四种颜色就够了. .问题问题4(4(关键路径问题关键路径问题):): 一项工程任务一项工程任务, ,大到建造一座大坝大到建造一座大坝, ,一座体育中心一座体育中心, ,小至组装一台机床小至组装一台机床, ,一架电视机一架电视机, , 都要包括许多工序都要包括许多工序. .这这些工序相互约束些工序相互约束, ,只有在某些工序完成之后只有在某些工序完成之后,

4、, 一个工序一个工序才能开始才能开始. . 即它们之间存在完成的先后次序关系即它们之间存在完成的先后次序关系, ,一般一般认为这些关系是预知的认为这些关系是预知的, , 而且也能够预计完成每个工序而且也能够预计完成每个工序所需要的时间所需要的时间. . 这时工程领导人员迫切希望了解最少需要多少时间这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目才能够完成整个工程项目, , 影响工程进度的要害工序是影响工程进度的要害工序是哪几个？哪几个？ 2022-8-1南京信息工程大学数理学院 费文龙7 图论中的图论中的“图图”并不是通常意义下的几何图形或物并不是通常意义下的几何图形或物体的

5、形状图体的形状图, , 而是以一种抽象的形式来表达一些确定的而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统事物之间的联系的一个数学系统. . 定义定义1 一个有序二元组一个有序二元组(V, E ) 称为一个称为一个图图, 记为记为G = (V, E ), 其中其中 V称为称为G的顶点集的顶点集, V , 其元素称为其元素称为顶点顶点或或结点结点, 简称简称点点; E称为称为G的边集的边集, 其元素称为其元素称为边边, 它联结它联结V 中的两中的两个点个点, 如果这两个点是无序的如果这两个点是无序的, 则称该边为则称该边为无向边无向边, 否则否则, 称为称为有向边有向边. 如果

6、如果V = v1, v2, , vn是有限非空点集是有限非空点集, 则称则称G为为有有限图限图或或n阶图阶图. 2022-8-1南京信息工程大学数理学院 费文龙8 如果如果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 ,

7、vj为边为边vivj的的端点端点. 在有向图中在有向图中, 称点称点vi , vj分别为边分别为边vivj的的始点始点和和终点终点. 该图称为该图称为(n,m)图图2022-8-1南京信息工程大学数理学院 费文龙9 对于一个图对于一个图G = (V, E ), 人们常用图形来表示人们常用图形来表示它它, 称其为称其为图解图解. 凡是有向边凡是有向边, 在图解上都用箭头在图解上都用箭头标明其方向标明其方向. 例如例如, 设设V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 则则G = (V, E ) 是一个有是

8、一个有4个顶个顶点和点和6条边的图条边的图, G的图解如下图所示的图解如下图所示. 2022-8-1南京信息工程大学数理学院 费文龙10 一个图会有许多外形不同的图解一个图会有许多外形不同的图解, , 下面两个图表示下面两个图表示同一个图同一个图G = (V, E )的图解的图解. .其中其中V = v1 , v2 , v3 , v4,E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4. 这两个图互为这两个图互为同构图同构图, ,今后将不计较这种外形上的差今后将不计较这种外形上的差别别, ,而用一个容易理解的、确定的图解去表示一个图而用一个容易理解的、确定的

9、图解去表示一个图. .2022-8-1南京信息工程大学数理学院 费文龙11 有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点, 有一个公共端点的有一个公共端点的边称为边称为相邻边相邻边. 边和它的端点称为边和它的端点称为互相关联互相关联. 常用常用d(v)表示表示图图G中与顶点中与顶点v关联的边的数目关联的边的数目, d(v)称为顶点称为顶点v的的度数度数. 对对于有向图于有向图,还有还有出度出度和和入度入度之分之分. 用用N(v)表示图表示图G中所有与顶点中所有与顶点v相邻的顶点的集合相邻的顶点的集合. d(v1)= d(v3)= d(v4)=4,d(v2)=2.mvdnii2)(1

10、握手定理：握手定理：2022-8-1南京信息工程大学数理学院 费文龙12我们今后只讨论我们今后只讨论有限简单图有限简单图： (1) (1) 顶点个数是有限的顶点个数是有限的; (2) (2) 任意一条边有且只有两个不同的点与它相互关联任意一条边有且只有两个不同的点与它相互关联; (3) (3) 若是无向图若是无向图, , 则任意两个顶点最多只有一条边与则任意两个顶点最多只有一条边与之相联结之相联结; (4) (4) 若是有向图若是有向图, , 则任意两个顶点最多只有两条边与则任意两个顶点最多只有两条边与之相联结之相联结. . 当两个顶点有两条边与之相联结时，这两条当两个顶点有两条边与之相联结时

11、，这两条边的方向相反边的方向相反. . 如果某个有限图不满足如果某个有限图不满足(2)(3)(4),(2)(3)(4),可在某条边上增设可在某条边上增设顶点使之满足顶点使之满足. .2022-8-1南京信息工程大学数理学院 费文龙13 定义定义2 若将图若将图G的每一条边的每一条边e都对应一个实数都对应一个实数F (e), 则则称称F (e)为该边的为该边的权权, 并称图并称图G为为赋权图赋权图(网络网络), 记为记为G = (V, E , F ). 定义定义3 任意两点均有通路的图称为任意两点均有通路的图称为连通图连通图. 定义定义4 连通而无圈的图称为连通而无圈的图称为树树, 常用常用T表

12、示树表示树. 2022-8-1南京信息工程大学数理学院 费文龙14 例例 一摆渡人欲将一只狼一摆渡人欲将一只狼, ,一头羊一头羊, ,一篮菜从河西渡过一篮菜从河西渡过河到河东河到河东. .由于船小由于船小, ,一次只能带一物过河，并且狼与羊一次只能带一物过河，并且狼与羊, ,羊与菜不能独处羊与菜不能独处. .给出渡河方法给出渡河方法. . 解解：用四维：用四维0-10-1向量表示向量表示( (人人, ,狼狼, ,羊羊, ,菜菜) )在河西岸的在河西岸的状态状态( (在河西岸则分量取在河西岸则分量取1,1,否则取否则取0),0),共有共有24 =16 种状态种状态. .在河东岸的状态类似记作在河

13、东岸的状态类似记作. . 由题设由题设, ,状态状态(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个个状态状态向量作为顶点向量作为顶点,将可能互相转移将可能互相转移的状态用线段连接起来构成一个图的状态用线段连接起来构成一个图. 根据此图便可找到根据此图便可找到渡河方法渡河方法. .2022-8-1南京信息工程大学数理学院 费文龙15(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1)

14、 (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的的路路. 从图中易得到两

15、条从图中易得到两条路路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.2022-8-1南京信息工程大学数理学院 费文龙16图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵 邻接矩阵表示了点与点之间的邻接关系邻接矩阵表示了点与点之间的邻接关系. .一个一个n阶图阶图G的邻接矩阵的邻接矩阵A = (aij )nn , 其中其中 ., 0;, 1EvEvaijijij0101100101001010A2022-8-1南京信息工程大学数理学院 费文龙17无向图无向图G的邻接矩阵的邻接矩阵A是一个对称矩阵是一个对称矩阵. . 010110110101111

16、0A 权矩阵权矩阵 一个一个n阶赋权图阶赋权图G = (V, E, F)的权矩阵的权矩阵A = (aij ) nn , 其中其中 .,;0),(EvjiEvvvFaijijjiij有限简单图基本有限简单图基本上可用权矩阵来上可用权矩阵来表示表示. .2022-8-1南京信息工程大学数理学院 费文龙1805420370860A无向图无向图G的权矩阵的权矩阵A是一个对称矩阵是一个对称矩阵. . 02420737064360A2022-8-1南京信息工程大学数理学院 费文龙19 关联矩阵（略）关联矩阵（略） 一个有一个有m条边的条边的n阶有向图阶有向图G的的关联矩阵关联矩阵A = (aij )nm

17、, 其中其中 若若vi是是ej的始点的始点;若若vi是是ej的终点的终点;若若vi与与ej不关联不关联. ., 0, 1, 1ija 有向图的关联矩阵每列的元素中有且仅有一个有向图的关联矩阵每列的元素中有且仅有一个1,1,有有且仅有一个且仅有一个 - - 1. 1. 1101100011011000000111011001A2022-8-1南京信息工程大学数理学院 费文龙20 一个有一个有m条边的条边的n阶无向图阶无向图G的关联矩阵的关联矩阵A = (aij )nm , 其中其中 若若vi与与ej关联关联;若若vi与与ej不关联不关联. ., 0, 1ija 无向图的关联矩阵每列的元素中有且仅

18、有两个无向图的关联矩阵每列的元素中有且仅有两个1. 1. 110100101010011001000111A2022-8-1南京信息工程大学数理学院 费文龙21 定义定义1 设设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的路

19、径的路径P (u, v)都有都有F (P0)F(P), 则称则称P0 (u, v) 是是G 中连接中连接u, v的的最短路最短路. 2022-8-1南京信息工程大学数理学院 费文龙22重要性质：重要性质： 若若v0 v1 vm 是是图图G中从中从v0到到vm的最短路的最短路, 则则 1km, v0v1 vk 必为必为G中从中从v0到到vk的最短路的最短路. 即：最短路是一条路，且最短路的任一段也是最短即：最短路是一条路，且最短路的任一段也是最短路路. 求非负赋权图求非负赋权图G中某一点到其它各点最短路，一般中某一点到其它各点最短路，一般用用Dijkstra标号算法；求非负赋权图上任意两点间的最

20、标号算法；求非负赋权图上任意两点间的最短路，一般用短路，一般用Floyd算法算法. . 这两种算法均适用于有向非负赋权图这两种算法均适用于有向非负赋权图. . 下面分别介绍两种算法的基本过程下面分别介绍两种算法的基本过程. .2022-8-1南京信息工程大学数理学院 费文龙23Dijkstra算法算法l指标指标（a为起点）为起点） 设设T T为为V V的子集，的子集，P=V-TP=V-T且且aTaT，对所有，对所有tTtT，设，设 l(t)l(t)表示从表示从a a到到t t的所有通路中距离最短的一条的长度，且这条路径中不包含的所有通路中距离最短的一条的长度，且这条路径中不包含T T中中其他的

21、结点，则称其他的结点，则称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中的任一

22、点中的任一点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)

23、,l(x)+w(x,t)2022-8-1南京信息工程大学数理学院 费文龙24Dijkstra算法算法（求（求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=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)为图的权矩阵） 2022-8-1南京信息工程大学数理学院 费文龙25

24、改进改进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的指标. 若 l(x)+w(x,t) dik + dkj , ,则删除则删除vi到到vj的连线的连线. .得到得到2022-8-1南京信息工程大学数理学院 费文龙30从上图中容易得到任意两点

25、间的最短路从上图中容易得到任意两点间的最短路. .例如例如, ,v1到到v6的路有三条：的路有三条： v1v0v3v2v6( (长度为长度为12),12), v1v4v5v2v6( (长度为长度为7),7), v1v4v7v6( (长度为长度为12).12).2022-8-1南京信息工程大学数理学院 费文龙31例例 设备更新问题设备更新问题 某企业每年年初某企业每年年初, ,都要作出决定都要作出决定, ,如果继续使用旧设如果继续使用旧设备备, ,要付维修费；若购买一台新设备要付维修费；若购买一台新设备, ,要付购买费要付购买费. .试制定试制定一个一个5 5年更新计划年更新计划, ,使总支出最

26、少使总支出最少. . 已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为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 |

27、 1ij6. . ijkkijicbvvF1)(2022-8-1南京信息工程大学数理学院 费文龙32 这样上述设备更新问题就变为：在有向赋权图这样上述设备更新问题就变为：在有向赋权图G = (V, E, F )(图解如下图解如下) )中求中求v1到到v6的最短路问题的最短路问题. 2022-8-1南京信息工程大学数理学院 费文龙33 由实际问题可知由实际问题可知, ,设备使用三年后应当更新设备使用三年后应当更新, ,因此删因此删除该图中除该图中v1到到v5 , ,v1到到v6 , ,v2到到v6的连线；又设备使用一年的连线；又设备使用一年后就更新则不划算后就更新则不划算, ,因此再删除该图中因

28、此再删除该图中v1v2 , ,v2v3 , ,v3v4 , ,v4v5 , ,v5v6 五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6和和v1v4v6. . 而这两条路都是而这两条路都是v1到到v6的最短路的最短路. .2022-8-1南京信息工程大学数理学院 费文龙343 3、最小生成树、最小生成树 由树的定义不难知道由树的定义不难知道, 任意一个连通的任意一个连通的(n,m)图图G适适当去掉当去掉m - - n +1条边后条边后, 都可以变成树都可以变成树, 这棵树称为图这棵树称为图G的的生成树生成树. 设设T是图是图G的一棵生

29、成树的一棵生成树, 用用F(T)表示树表示树T中所有边的中所有边的权数之和权数之和, F(T)称为称为树树T的权的权. 一个连通图一个连通图G的生成树一般不止一棵的生成树一般不止一棵, 图图G的所有生的所有生成树中权数最小的生成树称为图成树中权数最小的生成树称为图G的的最小生成树最小生成树. 求最小生成树问题有很广泛的实际应用求最小生成树问题有很广泛的实际应用. 例如例如, 把把n个乡镇用高压电缆连接起来建立一个电网个乡镇用高压电缆连接起来建立一个电网, 使所用的电使所用的电缆长度之和最短缆长度之和最短, 即费用最小即费用最小, 就是一个求最小生成树问就是一个求最小生成树问题题. 2022-8

30、-1南京信息工程大学数理学院 费文龙35Kruskal算算法：法：从未选入树中的边中选取权重最小的且从未选入树中的边中选取权重最小的且不构成回路的边加入到树中不构成回路的边加入到树中. .（判断回路比较麻烦）（判断回路比较麻烦）Prim算法：算法：把结点分成两个集合，已加入树中的把结点分成两个集合，已加入树中的(P)(P)和和未加入树中的未加入树中的(Q)(Q)，然后每次选择一个点在，然后每次选择一个点在P P中一个点在中一个点在Q Q中的权重最小的边，加入树中，并把相应点加入中的权重最小的边，加入树中，并把相应点加入P P中。中。其最小生成树如下：其最小生成树如下：类似地类似地, ,可定义连

31、通图可定义连通图G 的最大生成树的最大生成树. .2161342272435ABFGHDCE1122223HDCEFGAB2022-8-1南京信息工程大学数理学院 费文龙36例例 选址问题选址问题 现准备现准备在在 n 个个居民点居民点v1, v2, , vn中设置一银行中设置一银行. .问问设在哪个点设在哪个点, ,可使最大服务距离最小可使最大服务距离最小? ? 若设置两个银行若设置两个银行, ,问设在哪两个点问设在哪两个点? ? 模型假设模型假设 假设各假设各个个居民点都有条件设置银行居民点都有条件设置银行, ,并并有路相连有路相连, ,且路长已知且路长已知. . 模型建立与求解模型建立与

32、求解 用用Floyd算法求出任意两算法求出任意两个个居民居民点点vi , vj 之间的最短距离之间的最短距离, ,并用并用dij 表示表示. . 设置一个银行设置一个银行, ,银行设银行设在在 vi 点点的最大服务距离为的最大服务距离为.,.,2 , 1,max1niddijnji2022-8-1南京信息工程大学数理学院 费文龙37求求k, ,使使.min1inikdd 即若设置一个银行即若设置一个银行, ,则银行设在则银行设在 vk 点点, ,可使最大服务可使最大服务距离最小距离最小. . 设置两个银行设置两个银行, ,假设银行设假设银行设在在vs , vt 点点使最大服务使最大服务距离最小

33、距离最小. .记记.,minmax),(1jkiknkddjid则则s, ,t 满足：满足：).,(min),(1jidtsdnji进一步进一步, ,若设置多个银行呢？若设置多个银行呢？2022-8-1南京信息工程大学数理学院 费文龙38一、欧拉图一、欧拉图lG=(V,E)为一连通无向图l经过G中每条边至少一次的回路称为巡回巡回；l经过G中每条边正好一次的巡回称为欧拉巡回欧拉巡回；l存在欧拉巡回的图称为欧拉图。欧拉图。二、中国邮递员问题二、中国邮递员问题（CPPchinese postman problem） l一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发

34、，经过投递区内每条街道至少一次，最后返回邮局）？l这一问题是我国管梅谷教授1962年首先提出，国际上称之为中国邮递员问题。 2022-8-1南京信息工程大学数理学院 费文龙39l解法：解法：若本身就是欧拉图，则直接可以找到一条欧拉巡回若本身就是欧拉图，则直接可以找到一条欧拉巡回就是本问题的解。就是本问题的解。若不是欧拉图，必定有偶数个奇度数结点，在这些若不是欧拉图，必定有偶数个奇度数结点，在这些奇度数点之间添加一些边，使之变成欧拉图，再找奇度数点之间添加一些边，使之变成欧拉图，再找出一个欧拉巡回。出一个欧拉巡回。l具体解法：具体解法：Fleury算法算法+Edmonds最小对集算最小对集算法法

35、2022-8-1南京信息工程大学数理学院 费文龙40三、哈密尔顿图三、哈密尔顿图lG=(V,E)为一连通无向图l经过G中每点一次且正好一次的路径称为哈密尔顿路径哈密尔顿路径；l经过G中每点一次且正好一次的回路称为哈密尔顿回路哈密尔顿回路；l存在哈密尔顿回路的图称为哈密尔顿图。哈密尔顿图。四、旅行商问题四、旅行商问题（TSPtraveling salesman problem）l一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线？ 即：从驻地出发，经过每个城市恰好一次，最后返回驻地（最小哈密尔顿回路）（最小哈密尔顿回路）l对于n个节点的旅行商问题，n个节点的任意一个全排列都

36、是问题的一个可能解（假设任意两个点之间都有边）。G个节点的全排列有(n-1)!个，因此间题归结为在(n-1)!个回路中选取最小回路。 lTSP问题的解法属于NPNP完全问题完全问题，一般只研究其近似解法2022-8-1南京信息工程大学数理学院 费文龙41l最邻近算法最邻近算法(1) 选取任意一个点作为起始点,找出与该点相关联的权重最小的边,形成一条初始路径.(2) 找出与最新加入到路径中的点相关联的权重最小的边加入到路径中,且要求不再路径中产生回路.(3) 重复(2)直到所有的结点都加入到路径中.(4) 将起点和最后加入的结点之间的边加入到路径中,形成Hamilton回路.l其他数值算法：其他

37、数值算法： 人工神经元方法， 遗传算法等等2022-8-1南京信息工程大学数理学院 费文龙42 定义定义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 )为为二部赋权图二部赋权图. . 二部赋权图的权矩阵一般记作二

38、部赋权图的权矩阵一般记作A=(aij )|X|Y | , ,其中其中aij = F (xi yj ). .2022-8-1南京信息工程大学数理学院 费文龙43 定义定义2 2 设设G =(X, Y, E)为二部图为二部图, ,且且M E. .若若M中任意两条边中任意两条边在在G中均不邻接中均不邻接, ,则称则称M是是二部图二部图G的一个的一个匹配匹配. . 定义定义3 3 设设M是二部图是二部图G的一个匹配的一个匹配, ,如果如果G的每一个点都是的每一个点都是M中边的顶中边的顶点点, ,则称则称M是二部图是二部图G的的完美匹配完美匹配； 如果如果G中没有另外的匹配中没有另外的匹配M0 , ,使

39、使| |M0| | |M|,|,则称则称M是二部图是二部图G的的最大匹配最大匹配. . 在二部赋权图在二部赋权图G =(X, Y, E, F )中中, ,权数最大的最大匹配权数最大的最大匹配M称为称为二部赋权图二部赋权图G的的最佳匹配最佳匹配. . 显然显然, ,每个完美匹配都是最大匹配每个完美匹配都是最大匹配, ,反之不一定成立反之不一定成立. .2022-8-1南京信息工程大学数理学院 费文龙44工作安排问题之一工作安排问题之一 给给n个工作人员个工作人员x1, x2, , xn安排安排n项工作项工作y1, y2, , yn. . n个工作人员中每个人能胜任一项或几项工作个工作人员中每个人

40、能胜任一项或几项工作, 但并但并不是所有不是所有工作人员都能从事任何一项工作工作人员都能从事任何一项工作. 比如比如x1能做能做y1, y2工作工作, x2能能做做y2, y3, y4工作等工作等. 这样便提出一个问题这样便提出一个问题, 对所有的工作人员能不能都分配对所有的工作人员能不能都分配一件他所能胜任的工作？一件他所能胜任的工作？ 我们构造一个二部图我们构造一个二部图G = ( X, Y, E ), 这里这里X = x1, x2, , xn,Y = y1, y2, , yn, 并且当且仅当工作人员并且当且仅当工作人员xi胜任工作胜任工作yj时时, xi与与yj才相邻才相邻. 于是于是,

41、 问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配. 因为因为 |X|=|Y|, 所以完美匹配即为最大匹配所以完美匹配即为最大匹配. 2022-8-1南京信息工程大学数理学院 费文龙45 求二部图求二部图G = ( X, Y, E )的最大匹配算法的最大匹配算法( (匈牙利算法匈牙利算法, ,交替链交替链算法算法) )迭代步骤迭代步骤: 从从G的任意匹配的任意匹配M开始开始. . 将将X中中M的所有的所有非饱和点非饱和点都给以标号都给以标号0 0和标记和标记* *, , 转向转向. . M的非饱和点即非的非饱和点即非M的某条边的顶点的某条边的顶点. . 若若X中所有有标号的点都

42、已去掉了标记中所有有标号的点都已去掉了标记* *, , 则则M是是G的最大的最大匹配匹配. . 否则任取否则任取X中一个既有标号又有标记中一个既有标号又有标记* *的点的点xi , , 去掉去掉xi的标的标记记* *, , 转向转向. . 找出在找出在G中所有与中所有与xi邻接的点邻接的点yj , , 若所有这样的若所有这样的yj都已有标都已有标号号, , 则转向则转向, , 否则转向否则转向. .2022-8-1南京信息工程大学数理学院 费文龙46 对与对与xi邻接且尚未给标号的邻接且尚未给标号的yj都给定标号都给定标号i. . 若所有的若所有的 yj 都是都是M的的饱和点饱和点, ,则转向

43、则转向, ,否则逆向返回否则逆向返回. . 即由即由其中其中M的任一个非饱和点的任一个非饱和点 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 , ,给

44、以标号给以标号 j 和标记和标记* *, , 转向转向. .2022-8-1南京信息工程大学数理学院 费文龙47例例 求下图所示二部图求下图所示二部图G的最大匹配的最大匹配. . 解解 取初始匹配取初始匹配M0 = x2 y2 , x3 y3 , x5 y5 ( (上图粗线所示上图粗线所示). ). 给给X中中M0的两个非饱和点的两个非饱和点x1, ,x4都给以标号都给以标号0 0和标记和标记* * ( (如如下图所示下图所示). ). 去掉去掉x1的标记的标记*, 将与将与x1邻接的两个点邻接的两个点y2, y3都给以标号都给以标号1.1. 因因为为y2, y3都是都是M0的两个饱和点的两个

45、饱和点, ,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2, x3都给以相应的标号和标记都给以相应的标号和标记* (如下图所示如下图所示). 2022-8-1南京信息工程大学数理学院 费文龙48 去掉去掉x2的标记的标记*, 将与将与x2邻接且尚未给标号的三个点邻接且尚未给标号的三个点y1, y4, y5都给以标号都给以标号2 (如下图所示如下图所示). 因为因为y1是是M0的非饱和点的非饱和点, 所以顺着标号逆向返回依次得到所以顺着标号逆向返回依次得到x2, y2, 直到直到x1为为0为止为止. .于是得到于是得到M0的增广路的增广路x1 y2x2 y1, 记记P = x1 y

46、2 , y2x2 , x2 y1. 取取M1 = M0P = x1 y2 , x2 y1 , x3 y3 , x5 y5, 则则M1是比是比M多一边的匹配多一边的匹配(如下图所示如下图所示). 2022-8-1南京信息工程大学数理学院 费文龙49 再给再给X中中M1的非饱和点的非饱和点x4给以标号给以标号0和标记和标记*, 然后去掉然后去掉x4的的标记标记*, 将与将与x4邻接的两个点邻接的两个点y2, y3都给以标号都给以标号4. 因为因为y2, y3都是都是M1的两个饱和点的两个饱和点, , 所以将它们在所以将它们在M1中邻接的两中邻接的两个点个点x1, x3都给以相应的标号和标记都给以相

47、应的标号和标记* (如下图所示如下图所示). 去掉去掉x1的标记的标记*, 因为与因为与x1邻接的两个点邻接的两个点y2, y3都有标号都有标号4, 所所以去掉以去掉x3的标记的标记*. 而与而与x3邻接的两个点邻接的两个点y2, y3也都有标号也都有标号4, 此时此时X中所有有标号中所有有标号的点都已去掉了标记的点都已去掉了标记*(如下图所示如下图所示), 因此因此M1是是G的最大匹配的最大匹配. G不存在饱和不存在饱和X的每个点的匹配的每个点的匹配, 当然也不存在完美匹配当然也不存在完美匹配.2022-8-1南京信息工程大学数理学院 费文龙50工作安排问题之二工作安排问题之二 给给n个工作

48、人员个工作人员x1, x2, , xn安排安排n项工作项工作y1, y2, , yn. . 如如果每个工作人员工作效率不同果每个工作人员工作效率不同, 要求工作分配的同时考虑总效要求工作分配的同时考虑总效率最高率最高. 我们构造一个二部赋权图我们构造一个二部赋权图G = ( X, Y, E , F ), 这里这里X = x1, x2, , xn,Y = y1, y2, , yn, F(xi yj )为工作人员为工作人员xi胜任工作胜任工作yj时的工作效率时的工作效率. 则问题转化为：求二部赋权图则问题转化为：求二部赋权图G的最佳匹配的最佳匹配. 在求在求G 的最佳匹配时的最佳匹配时, 总可以假

49、设总可以假设G为完备二部赋权图为完备二部赋权图. .若若xi与与yj不相邻不相邻, 可令可令F(xi yj )=0. 同样地同样地, 还可虚设点还可虚设点x或或y, ,使使|X|=|Y|. .如此就将如此就将G 转化为完备二部赋权图转化为完备二部赋权图, ,而且不会影响结果而且不会影响结果. 2022-8-1南京信息工程大学数理学院 费文龙51 定义定义 设设G =( (X, Y, E, F) )为完备的二部赋权图为完备的二部赋权图, , 若若L：X Y R + + 满足：满足： xX, yY, L(x) + L(y)F(xy), ,则称则称L为为G的一个的一个可行点标记可行点标记, ,记相应

50、的生成子图为记相应的生成子图为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. 2022-8-1南京信息工程大学数理学院 费文龙52M是是GL的一个匹配的一个匹配. . 若