数学建模图论案例讲解课件

数学建模图论案例讲解课件1B题灾情巡视路线下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。灾情巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的灾情巡视路线。1998年全国大学生数学建模竞赛题目B题灾情巡视路线1998年全国大学生数学建模竞赛题目2

假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的灾情巡视路线。在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的灾情巡视路线。若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳灾情巡视路线的影响。假定巡视人员在各乡（镇）停留时间T=3

4

旅行商问题（TSP－travelingsalesmanproblem）

一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商(推销员）问题。旅行商问题（TSP－travelingsalesman5哈密尔顿图1859年，数学家哈密尔顿发明了一种周游世界的游戏：在一个12面体的每个角点代表一个城市，问能否从某城市出发，沿12面体的棱行走，经过每个城市一且仅一次，最后回到出发地。用图论的语言来讲，就是在12面体图上找出生成圈。哈密尔顿图1859年，数学家哈密尔顿发明了一6哈密尔顿图哈密尔顿图7推销员问题-定义

流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题．

若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题．推销员问题-定义流动推销员需要访问某地区的所有城镇8定义在加权图G=(V,E)中，（１）权最小的哈密尔顿圈称为最佳H圈．（２）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路．

一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈．H回路，长22最佳推销员回路，长4定义在加权图G=(V,E)中，一般说来，最佳哈9数学建模图论案例讲解课件10推销员问题近似算法：二边逐次修正法：推销员问题近似算法：二边逐次修正法：11分析：

灾情巡视路线问题是一个寻求最佳多旅行商回路的问题。1、多旅行商问题

跟单旅行商问题的区别。单旅行商问题可以转化为加权图的最优H圈问题。多旅行商问题怎么办？2、第一问目标：总路程最短且尽可能均衡。如何表述。目标1：

目标2：

分析：

灾情巡视路线问题是一个寻求最佳多旅行商回路12限制条件第一问目标简化：多目标单目标

分组：方法很多。可以给定一个初始分组，然后基于上述单目标进行调整。问题2：最小组数问题。（问题3也涉及）分析：求r组多旅行商路线，在满足题目要求限制条件下，使得每个路线都包含县城，且总体能覆盖V。并证明r-1组不可能。限制条件13限制条件：在巡视点有一定停留时间的情况下24小时完成巡视。巡视点停留：引入点权。对村乡进行编号，村权35，乡权70.时间化为距离，将点权和边权统一起来。对每一个旅行商路线，求其总权T_i,优化的目标为使得分组的最大的总权尽量小。方法：调整分组。在给定上述目标和约束的条件下，对问题2不难得到4个旅行商路线可以满足。如何证明3个不行？限制条件：在巡视点有一定停留时间的情况下24小时完成巡视。14问题3：最短时间及最优巡视方案最短时间：县城到最远乡镇的距离。不难确定。最优巡视方案？？？可以按照问题2的模型确定组数。答案为22.但是如何证明21不行？思考题？问题3：最短时间及最优巡视方案最短时间：县城到最远乡镇的距15问题4：组数已定，讨论T,t,V的改变对最佳巡视路线的影响要尽快完成巡视,就得要求每组完成巡视时问尽量均衡,因为总的完成巡视时间按最长的完成巡视时间计算。现在讨论在均衡度允许的范围内已分成n组后，改变T,t,V对最佳巡视路线的影响。显然在分组不变的情况下,无论如何改变分组后，对每组内的最沈封丛视路线是没有影响的，但可能会影响各组间的均衡性因此该问题实际上是讨论T,t,V对分组的影响,即在不破坏原来分组均衡的条件下,T、t,V允许的最大变化范围问题4：组数已定，讨论T,t,V的改变对最佳巡视路线的影响要161994全国大学生数学建模竞赛题目B题锁具装箱

某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从{1,2,3,4,5,6}6个数(单位略)中任取一数。由于工艺及其它原因,制造锁具时对5个槽的高度还有两个限制:至少有3个不同的数;相邻两槽高度之差不能为5。满足以上条件制造出来的所有互不相同的锁具称为一批。出来的所有互不相同的锁具称为一批。从顾客的利益出发,自然希望在每批锁具中"一把钥匙开一把锁"。但是在当前工艺条件下,对于同一批中两个锁具是否能够互开,有以下试验结果:若二者相对应的5个槽的高度中有4个相同,另一个的高度差为1,则可能互开;在其它情形下,不可能互开。原来,销售部门在一批锁具中随意地取每60个装一箱出售。团体顾客往往购买几箱到几十箱,他们抱怨购得的锁具会出现互相开的情形。现聘聘请你为顾问,回答并解决以下问题:1994全国大学生数学建模竞赛题目B题锁具装箱17每一批锁具有多少个,装多少箱。为销售部门提供一种方案,包括如何装箱(仍是60个锁具一箱),如何给箱子以标志,出售时如何利用这些标志,使团体顾客不再或减少抱怨。采取你提出的方案,团体顾客的购买量不超过多少箱,就可以保证一定不会出现互开。按照原来的装箱办法,如何定量地衡量团体顾客抱怨互开的程度(试对购买一、二箱者给出具体结果)。每一批锁具有多少个,装多少箱。18称G=(X,Y,E)为二部图.如果X中的每个点都与Y中的每个点邻接,则称G=(X,Y,E)为完备二部图.若

F：E→R+,则称G=(X,Y,E,F)为二部赋权图.定义1

设X,Y都是非空有限顶点集,且X∩Y=Φ,二部图的匹配、独力集称G=(X,Y,E)为二部图.如果X中的每个点19定义3

若匹配M的某条边与点v关联,则称M饱和点v,并且称v是M的饱和点,否则称v是M的非饱和点.定义4

设M是图G的一个匹配,如果G的每一个点都是M的饱和点,则称M是完美匹配；如果G中没有另外的匹配M0,使

|M0|＞|M|,则称M是最大匹配.

含边数最多的最大匹配中所含的边数称为图G的边独立数，记为每个完美匹配都是最大匹配,反之不一定成立.二部图的匹配、独力集定义3若匹配M的某条边与点v关联,则称M饱和定义4设M20例16：判断下图的匹配最大匹配非完美匹配完美匹配二部图的匹配、独力集例16：判断下图的匹配最大匹配完美匹配二部图的匹配、独力集21定义5若图G的一个顶点子集中的任意两个点都互不相邻,则称该顶点子集为为G的一个点独立集。图G的独立数为G的最大点独力集所含的点数，记为定义6若图G的一个顶点子集K称为G的一个点覆盖子集，如果G中的任意一条边都至少有一个顶点包含在G中.图G的覆盖数为G的最小点覆盖集中所含的点数，记为

若G中任一个顶点都是图G的边集S中一条边的顶点，则称S为G的一个边覆盖集。含边数最少的边覆盖集中的边数称为图G的边覆盖数。二部图的匹配、独力集定义5若图G的一个顶点子集中的任意两个点都互不相邻,则22二部图的匹配、独力集-相关定理定理1定理2若图G没有孤立顶点，即顶点的最小度

>0，则定理3对于二分图G，有二部图的匹配、独力集-相关定理定理1定理2若23引理1

设G=(X,Y,E)为二部图,则①G存在饱和X的每个点的匹配的充要条件是对任意S

,有|N(S)|≥|S|.其中,N(S)={v|u∈S,v与u相邻}.②G存在完美匹配的充要条件是对任意S或S有

|N(S)|≥|S|.二部图的匹配、独力集引理1设G=(X,Y,E)为二部图,则①G24分析：6种高度5个槽的钥匙最多可能有，通过排列组合，除去不满足条件的各种情况，可以

算出一批锁具的总数为5880件由于两个锁具对应的5个槽高中有4个相同，另一个只相差1，被视为互开，那么它们各自槽高之和必为一个奇数、一个偶数．另外，槽高之和为奇数和偶数的锁具可以一一对应，因而各占一半：2940件，槽高之和为奇数(或偶数)的两锁具之间不可能互开，所以若6O个装一箱，2940个锁具可以装49箱，49箱槽高之和为奇数或偶数的锁具，肯定不能互开．现在的问题是49箱是不是最大可能的?分析：6种高度5个槽的钥匙最多可能有25将锁具的互开关系用图表示，锁具集合用表示，其中和分别表示槽高之和为奇数和偶数的锁具集合。若能够互开，则两点连一边。对问题1构造的二分图，由于奇数类锁具与偶数类锁具的对称性，引理1满足，所以存在饱和的每个顶点的匹配，而的顶点互不相邻，因此从而点独立数

．由于奇数类点独立集和偶数类点独立集都有2940个点,所以，说明奇数类点集和偶数类点集都是最大的点独立集,因此49箱是不能互开的最大可能．将锁具的互开关系用图表示，锁具集合用26ThankYou!ThankYou!27数学建模图论案例讲解课件28B题灾情巡视路线下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。灾情巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的灾情巡视路线。1998年全国大学生数学建模竞赛题目B题灾情巡视路线1998年全国大学生数学建模竞赛题目29

假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的灾情巡视路线。在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的灾情巡视路线。若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳灾情巡视路线的影响。假定巡视人员在各乡（镇）停留时间T=30

31

旅行商问题（TSP－travelingsalesmanproblem）

一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商(推销员）问题。旅行商问题（TSP－travelingsalesman32哈密尔顿图1859年，数学家哈密尔顿发明了一种周游世界的游戏：在一个12面体的每个角点代表一个城市，问能否从某城市出发，沿12面体的棱行走，经过每个城市一且仅一次，最后回到出发地。用图论的语言来讲，就是在12面体图上找出生成圈。哈密尔顿图1859年，数学家哈密尔顿发明了一33哈密尔顿图哈密尔顿图34推销员问题-定义

流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题．

若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题．推销员问题-定义流动推销员需要访问某地区的所有城镇35定义在加权图G=(V,E)中，（１）权最小的哈密尔顿圈称为最佳H圈．（２）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路．

一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈．H回路，长22最佳推销员回路，长4定义在加权图G=(V,E)中，一般说来，最佳哈36数学建模图论案例讲解课件37推销员问题近似算法：二边逐次修正法：推销员问题近似算法：二边逐次修正法：38分析：

灾情巡视路线问题是一个寻求最佳多旅行商回路的问题。1、多旅行商问题

跟单旅行商问题的区别。单旅行商问题可以转化为加权图的最优H圈问题。多旅行商问题怎么办？2、第一问目标：总路程最短且尽可能均衡。如何表述。目标1：

目标2：

分析：

灾情巡视路线问题是一个寻求最佳多旅行商回路39限制条件第一问目标简化：多目标单目标

分组：方法很多。可以给定一个初始分组，然后基于上述单目标进行调整。问题2：最小组数问题。（问题3也涉及）分析：求r组多旅行商路线，在满足题目要求限制条件下，使得每个路线都包含县城，且总体能覆盖V。并证明r-1组不可能。限制条件40限制条件：在巡视点有一定停留时间的情况下24小时完成巡视。巡视点停留：引入点权。对村乡进行编号，村权35，乡权70.时间化为距离，将点权和边权统一起来。对每一个旅行商路线，求其总权T_i,优化的目标为使得分组的最大的总权尽量小。方法：调整分组。在给定上述目标和约束的条件下，对问题2不难得到4个旅行商路线可以满足。如何证明3个不行？限制条件：在巡视点有一定停留时间的情况下24小时完成巡视。41问题3：最短时间及最优巡视方案最短时间：县城到最远乡镇的距离。不难确定。最优巡视方案？？？可以按照问题2的模型确定组数。答案为22.但是如何证明21不行？思考题？问题3：最短时间及最优巡视方案最短时间：县城到最远乡镇的距42问题4：组数已定，讨论T,t,V的改变对最佳巡视路线的影响要尽快完成巡视,就得要求每组完成巡视时问尽量均衡,因为总的完成巡视时间按最长的完成巡视时间计算。现在讨论在均衡度允许的范围内已分成n组后，改变T,t,V对最佳巡视路线的影响。显然在分组不变的情况下,无论如何改变分组后，对每组内的最沈封丛视路线是没有影响的，但可能会影响各组间的均衡性因此该问题实际上是讨论T,t,V对分组的影响,即在不破坏原来分组均衡的条件下,T、t,V允许的最大变化范围问题4：组数已定，讨论T,t,V的改变对最佳巡视路线的影响要431994全国大学生数学建模竞赛题目B题锁具装箱

某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从{1,2,3,4,5,6}6个数(单位略)中任取一数。由于工艺及其它原因,制造锁具时对5个槽的高度还有两个限制:至少有3个不同的数;相邻两槽高度之差不能为5。满足以上条件制造出来的所有互不相同的锁具称为一批。出来的所有互不相同的锁具称为一批。从顾客的利益出发,自然希望在每批锁具中"一把钥匙开一把锁"。但是在当前工艺条件下,对于同一批中两个锁具是否能够互开,有以下试验结果:若二者相对应的5个槽的高度中有4个相同,另一个的高度差为1,则可能互开;在其它情形下,不可能互开。原来,销售部门在一批锁具中随意地取每60个装一箱出售。团体顾客往往购买几箱到几十箱,他们抱怨购得的锁具会出现互相开的情形。现聘聘请你为顾问,回答并解决以下问题:1994全国大学生数学建模竞赛题目B题锁具装箱44每一批锁具有多少个,装多少箱。为销售部门提供一种方案,包括如何装箱(仍是60个锁具一箱),如何给箱子以标志,出售时如何利用这些标志,使团体顾客不再或减少抱怨。采取你提出的方案,团体顾客的购买量不超过多少箱,就可以保证一定不会出现互开。按照原来的装箱办法,如何定量地衡量团体顾客抱怨互开的程度(试对购买一、二箱者给出具体结果)。每一批锁具有多少个,装多少箱。45称G=(X,Y,E)为二部图.如果X中的每个点都与Y中的每个点邻接,则称G=(X,Y,E)为完备二部图.若

F：E→R+,则称G=(X,Y,E,F)为二部赋权图.定义1

设X,Y都是非空有限顶点集,且X∩Y=Φ,二部图的匹配、独力集称G=(X,Y,E)为二部图.如果X中的每个点46定义3

若匹配M的某条边与点v关联,则称M饱和点v,并且称v是M的饱和点,否则称v是M的非饱和点.定义4

设M是图G的一个匹配,如果G的每一个点都是M的饱和点,则称M是完美匹配；如果G中没有另外的匹配M0,使

|M0|＞|M|,则称M是最大匹配.

含边数最多的最大匹配中所含的边数称为图G的边独立数，记为每个完美匹配都是最大匹配,反之不一定成立.二部图的匹配、独力集定义3若匹配M的某条边与点v关联,则称M饱和定义4设M47例16：判断下图的匹配最大匹配非完美匹配完美匹配二部图的匹配、独力集例16：判断下图的匹配最大匹配完美匹配二部图的匹配、独力集48定义5若图G的一个顶点子集中的任意两个点都互不相邻,则称该顶点子集为为G的一个点独立集。图G的独立数为G的最大点独力集所含的点数，记为定义6若图G的一个顶点子集K称为G的一个点覆盖子集，如果G中的任意一条边都至少有一个顶点包含在G中.图G的覆盖数为G的最小点覆盖集中所含的点数，记为

若G中任一个顶点都是图G的边集S中一条边的顶点，则称S为G的一个边覆盖集。含边数最少的边覆盖集中的边数称为图G的边覆盖数。二部图的匹配、独力集定义5若图G的一个顶点子集中的任意两个点都互不相邻,则49二部图的匹配、独力集-相关定理定理1定理2若图G没有孤立顶点，即顶点的最小度

>0，则定理3对于二分图G，有二部图的匹配、独力集-相关定理定理1定理2若50引理1

设G=(X,Y,E)为二部图,则①G存在饱和X的每个点的匹配的充要条件是对任意S

,有|N(S