1、1 引言 B B题题 灾情巡视路线灾情巡视路线 下图为某县的乡（镇）、村公路网示意图，下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。灾情巡视路线指从全县各乡（镇）、村巡视。灾情巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短若分三组（路）巡视，
2、试设计总路程最短且各组尽可能均衡的灾情巡视路线。且各组尽可能均衡的灾情巡视路线。19981998年全国大学生数学建模竞赛题目年全国大学生数学建模竞赛题目 假定巡视人员在各乡（镇）停留时间假定巡视人员在各乡（镇）停留时间T=2T=2小时，在小时，在各村停留时间各村停留时间t=1t=1小时，汽车行驶速度小时，汽车行驶速度V=35V=35公里公里/小时。小时。要要2424小时内完成巡视，至少应分几组；给出这种分组小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的灾情巡视路线。下你认为最佳的灾情巡视路线。在上述关于在上述关于T,tT,t和和V V的假定下，如果巡视人员足的假定下，如果巡视人员足够
3、多，完成巡视的最短时间是多少；给出在这种最短够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的灾情巡视路线。时间完成巡视的要求下，你认为最佳的灾情巡视路线。若巡视组数已定若巡视组数已定(如三组），要求尽快完成巡视，如三组），要求尽快完成巡视，讨论讨论T T，t t和和V V改变对最佳灾情巡视路线的影响。改变对最佳灾情巡视路线的影响。旅行商问题旅行商问题（TSPTSPtraveling salesman problemtraveling salesman problem）一名推销员准备前往若干城市推销产品。如何为他一名推销员准备前往若干城市推销产品。如何为他（她）设
4、计一条最短的旅行路线（从驻地出发，经过每个城（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商久，通常称之为旅行商(推销员）问题。推销员）问题。哈哈 密密 尔尔 顿顿 图图 1859 1859年，数学家哈密尔顿发明了一种周游世界的游戏：年，数学家哈密尔顿发明了一种周游世界的游戏：在一个在一个1212面体的每个角点代表一个城市，问能否从某城市面体的每个角点代表一个城市，问能否从某城市出发，沿出发，沿1212面体的棱行走，经过每个城市一且仅一次，最面体的棱行走，经过每个城市
5、一且仅一次，最后回到出发地。后回到出发地。用图论的语言来讲，就是在用图论的语言来讲，就是在1212面体图上找出生成圈。面体图上找出生成圈。哈哈 密密 尔尔 顿顿 图图推销员问题推销员问题-定义定义 流动推销员需要访问某地区的所有城镇，最流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题小这就是推销员问题 若用顶点表示城镇，边表示连接两城镇的若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于路，边上的权表示距离（或时间、费用），于是推销员问题就成为是推销员问题就成为问题问题定义在加权图
6、定义在加权图G=(V,E)中，中，（）权最小的哈密尔顿圈称为（）权最小的哈密尔顿圈称为最佳最佳H圈圈（）经过每个顶点至少一次的权最小的闭通路称（）经过每个顶点至少一次的权最小的闭通路称为为最佳推销员回路最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长回路，长22最佳推销员回路，长最佳推销员回路，长4推销员问题近似算法：推销员问题近似算法：二边逐次修正法二边逐次修正法：（）任取初始 H 圈:C0=v1,v2,vi,vj,vn,v1（）对所有
7、的 i,j，1i+1jn,若w(vi,vj)+w(vi+1,vj+1)0，则则(G)(G)|V(G)|定定 理理 3 对对 于二分于二分 图图 G，有有(G)(G)引理引理1 设设G=(X,Y,E)为二部图为二部图,则则 G存在存在饱和饱和X的每个点的匹配的充要条件是的每个点的匹配的充要条件是对任意对任意S ,有有|N(S)|S|.其中其中,N(S)=v|uS,v与与u相邻相邻.G存在完美匹配的充要条件是存在完美匹配的充要条件是对任意对任意S 或或S 有有|N(S)|S|.X XY二部图的二部图的匹配、独力集匹配、独力集分析：6 种 高度 5 个 槽 的钥匙 最多 可能有 ，通 过排 列组 合
8、，除 去不 满足 条件 的各种 情 况，可 以算 出一批 锁具 的总数为 5880件 由于两个 锁具 对应 的 5 个 槽 高 中有 4 个 相 同，另一 个 只相 差 1，被视 为互 开，那 么它们 各 自 槽 高 之 和必为 一个 奇数、一个 偶数 另外，槽 高 之和为 奇数 和偶数 的锁 具 可 以一 一对 应，因 而各 占一 半：2 9 4 0件，槽 高 之和为奇数(或偶数)的两锁具之间不可能互开，所 以若 6 O个装一箱，2 9 4 0个锁具可 以装 4 9箱，4 9箱槽高之和为奇数或偶数的锁具，肯定不能互开 现在的问题是 4 9 箱是不是最大可能的?567776将锁具的互开关系用图
9、表示，锁具集合用 表示，其中 和 分别表示槽高之和为奇数和偶数的锁具集合。若 能 够互 开，则 两 点 连 一 边。对 问题 1 构 造 的二分 图，由于奇数 类锁 具 与偶 数类 锁 具 的对 称 性，引理 1 满 足，所 以存 在饱 和 的每个顶点的匹配，而 的顶 点互不 相邻，因此 从而点独立数 由于奇数类点独立集和偶数类点独立集都有2940个点,所 以 ，说 明奇数 类点集 和偶 数类 点集 都是 最大 的点 独立集,因此 4 9 箱 是 不能互 开 的最 大可 能12V V V 1V2V12,ijvV vV1V1V12940|V|M|(G)(G)|V|(G)(G)|V|29402940(G)2940
