（基础数学专业论文）哈密尔顿图在实际中的应用.pdf

摘要 摘要 到目前为止，哈密尔顿图的非平凡的充分必要条件尚不清楚，事实 上，这是图论中还没解决的主要问题之一，但哈密尔顿图在实际问题中， 应用又非常广泛，因此哈密尔顿图一直受到图论界以及运筹学学科研究 人员的大力关注。 本文主要讨论了h a m i i t o n 图的相关知识及其应用。 第章：简单介绍了h a m i i t o n 图的产生及发展过程。 第二、三章：在给出h a m i l t o n 图的有关概念的基础上，讨论h a m i l t o n 图存在的必要条件和充分条件。 第四章：介绍并讨论了h a m i i r o n 图在实际中的应用旅行货郎问 题，用搜索方法得出了有关最优解。 第五章：介绍了1 9 9 8 年全国大学生数学建模竞赛题灾情巡视路 线，给出了比较好的解决方法。 关键词：哈密尔顿图；必要条件；充分条件；旅游货郎问题 灾情巡视路线 哈密尔顿图的应用 a b s t r a c t u pt on o w , t h es u f f i c i e n tc o n d i t i o n sa n dn e c e s s a r yc o n d i t i o n so ft h e n o n t r i v i a lf o rt h eh a m i l t o ng r a p ha r es t i l lu n c l e a r i nf a c t ，i ti so n eo ft h e m a j o ru n s o l v e dp r o b l e m si ng r a p ht h e o r y ，b u ti ti sw i d e l yu s e di nm a n yr e a l a p p l i c a t i o n s t h i sp a p e rd i s c u s s e st h er e l a t e dc o n d i t i o n sa n da p p l i c a t i o n sf o r t h eh a m i l t o ng r a p h c h a p t e r 1i n t r o d u c e st h e o r i g i n o ft h eh a m i l t o n g r a p h a n di t s e v o l v e m e n t c h a p t e r2 - 3 i n t r o d u c e st h er e l a t e dc o n c e p t so ft h eh a m i l t o n g r a p h ，a n df u r t h e r d i s c u s s e si t ss u f f i c i e n tc o n d i t i o n s a n d n e c e s s a r y c o n d i t i o n s r e s p e c t i v e l y c h a p t e r4d i s c u s s e so n eo ft h em a j o ra p p l i c a t i o n s o ft h eh a m i l t o ng r a p h 一一t h et r a v e l i n gs a l e s m a np r o b l e m ，a n dp r o p o s e sa s e a r c h i n ga l g o r i t h m t h a ts o l v e s t h eb e s ts o l u t i o n p r o b l e m c h a p t e r 5 i n t r o d u c e s “t h ep r o b l e mo fm a k i n ga ni n s p e c t i o nt o u rf o rt h ec o n d i t i o no f ad i s a s t e r i nt h em o d e l i n gc o m p e t i t i o no fm a t h e m a t i c sf o rt h en a t i o n a l c o l l e g ei n19 9 8a n dg i v e sag o o ds o l u t i o nt ot h i sp r o b l e m k e y w o r d s ：h a m i l t o ng r a p h ；s u f f i c i e n tc o n d i t i o n ；n e c e s s a r y c o n d i t i o n ；t h et r a v e l i n gs a l e s m a np r o b l e m ；d i s a s t e rc o n s i d e rr e v i s i n g 2 引言 引言 图论是一门既古老又年轻的学科。随着科学技术的蓬勃发展，它的应用已经渗 透到自然科学、社会科学的各个领域。利用它可以解决很多实际问题。对于图沦中 的欧拉( e u l e r ) 图以及与之有关的邮递员问题等已经有了很好的解决方法，然而哈 密尔顿( h a m i i r o n ) 图以及与之有关的旅游货郎问题一直悬而未决。哈密尔顿 ( h a m i i r o n ) 图理论有着重要的理论意义和实际意义，许多图论以及运筹学学科研究 人员都进行着深入的研究。 大部分图论及其应用书上都给出h a m i l t o n 图的有关概念，一些文献上给出了 h a m i i t o n 图存在的必要条件和个别充分条件，但都不完善。 本文第一章简单介绍了h a m i l t o n 图的产生及发展过程。 第二章在给出h a m i l t o n 图的有关概念的基础上讨论h a m i l t o n 图存在的必要条 件和充分条件。 第三章介绍并讨论了h a m i i r o n 图在世纪中的应用旅游货郎问题，用搜索方 法得出了有关最优解的问题。 第四章：介绍了1 9 9 8 年全国大学生数学建模竞赛题灾情巡视路线问题，给 出了比较好的解决方法 目前，图论的理论与方法在计算机科学、运筹学、电网络分析、化学、物理以 及社会科学等方面起着很重要的作用：同时，对数学竞赛与数学建模及其应用起指 导作用；利用图论的理论与方法，可以解决很多实际问题。 本文起一个抛砖引玉的作用，希望更多的数学爱好者了解并关注此问题，以便 更好地为实际服务，解决更多的实际问题。 哈密尔顿图的应用 第一章哈密尔顿图的产生 哈密尔顿( h a m i i r o n ) 是爱尔兰的一位数学家和天文学家。他的一生是多姿多彩 的，自从哈密尔顿发现“四元数”之后，他又发现了另外一种他命名为“t h ei c o s i a n c a l c u l u s ”的代数系统，这系统有加法和乘法的运算子( o p e r a t o r s ) ，可是乘法不 满足交换律( c o m m u t a t iv ei a w 即x y - y x 这个规律) 。 他发现这代数系统是和正则1 2 面体( r e g u l a r i c o s i o np o l y h e d r o n ) 有关系的。 于是，哈密尔顿于1 8 5 9 年提出了所谓的“周游世界游戏”：用一个正十二面体的2 0 个顶点表示全世界的2 0 个大城市( 图l - 1 ( 1 ) ) ，一个人要从某一个城市出发，经过每 个城市恰好一次，然后回到出发点，问这样的旅行路线是否存在? 这个游戏曾风靡 一时。运用拓扑的思想，将这个正十二面体“拉平”就会得到一个与它同构的平面 图( 图一( 2 ) ) ，这样，这个游戏就转化为：要求沿着正十二而体的棱，怎样跑遍正则 多面体上的所有顶点，而最后又能回到起点的问题。 图1 1 此后，由于这个游戏的缘故，人们就称这一类图为哈密尔顿图。其实，哈密尔 顿图的由来可以追溯到更早时期。在1 7 1 8 世纪时，欧洲宫庭及一些贵族很喜欢玩 西洋象棋，西洋象棋中的骑士( k n i g h t ) 是对应我们中困象棋的“马”，而它通常是 刻成一个马头，跑法也是和中国象棋的“马”一样，走“日”线即从f | 的一角 沿着对角线跃到另一角。 在1 7 7 年，就有一位名叫范德蒙( a v a n d e r m o n d e ) 的法国数学家，写了一篇 文章研究所谓“棋赫的骑士问题”。这问题是这样：在8 x 8 的棋盘格的随意一个位 置上，放一个骑士，然后想法子使他跑遍棋盘的所有的格子，走过的不许再走，能 不能使骑士最后回到原来的位置? 第一章哈密尔顿图的由来 这个问题并不简单，许多象棋爱好者及数学家曾坐下来研究这个问题。我这里 列出一个情形的解( 见表1 1 ) ，将棋盘的左下角的格选为起始位置，把它定为l ， 大家可以验证根据表1 1 的跑法，骑士最后是能跑回1 的。 5 64 l5 83 55 03 96 0 3 3 4 74 45 54 05 93 45 13 8 4 25 74 64 93 65 33 26 1 4 5 4 84 3 5 43 l 6 2 3 75 2 2 053 06 32 21 11 6 1 3 2 96 42 141 71 42 5 l o 61 922 782 31 21 5 l 2 871 8 32 692 4 表1 1“棋盘骑士问题”的一个解法 1 8 世纪的大数学家欧拉( e u l e r ) ，在1 7 5 9 年曾系统地研究过这个问题，也得到 了些结果。以后德国数学家高斯也曾对这问题发生兴趣，花过一些时间研究它及 另外一个棋盘的“皇后问题”。 我们现在把棋盘上的格子对应在一个平面上的一个小圆点，这样我们在平面上 就有6 4 个小圆点。从一个格子用骑士的走法我们可以抵达不同数目的格子：如果是 处在棋盘的四个角，只能有两种跑法；在其他边缘的格子就有三种跑法：一般当中 的格子，就有四种可能的跑法。我们把平面上的点用弧线连接，两个点有一条弧线 连接，当且仅当( i fa n do n l yi f ) 我们可以从它们所对应的格子将骑士移动。这 样，我们得到了一个图( g r a p h ) 。该图经过所有的点一次且仅一次，这样的图就是 众所周知的哈密尔顿图。 哈密尔顿图的应用 第二章哈密尔顿图的有关概念 包含图中每个顶点的路称为哈密尔顿路：通过图中每个顶点一次且仅一次的通 路称为哈密尔顿通路：通过图中每个顶点一次且仅一次的回路称为哈密尔顿回路； 一个图若含有哈密尔顿回路，则称这个图是哈密尔顿图”。 v 5 ( 2 ) 幽2 1 在图中取一个顶点v ，如果我们有一个弧线把它和另外一个点v ：联起来，我们 就用( v ，v ：) 来表示这个弧线。假定我有一系列点v 。，v ：，v n ，其中没有两个相 同以及一序列的弧线存在( v 、，v 2 ) ，( v ：，v 。) ，( v 。，v 。) ，( v 。，v 、) ，使到我从 v 。出发可以经过v 。，v 。，v 。，最后由v 。回到v 。我就说这些弧线组成个回路 ( c i r c u i t ) ，为了方便，我们用下面的记号表示这回路：( v ，v ：，v 。v ) z - 3 。 如果有一个图g 有n 个顶点( v e r t i c e s ) v ，v ：，v 。) ，而我能找到一个吲 路( v ，v 。，v 。，v ) ，那么我们就说这个图是哈密尔顿图( h a m i l t o ng r a p h ) ，这 个回路称为哈密尔顿回路( h a m i i t o nc i r c u i t ) 5 - 6 o 由定义可知：十二面体含有一 条哈密尔顿回路，故十二面体是哈密尔顿图。 一个图的哈密尔顿回路与欧拉回路是很相似的，但差别在于哈密尔顿回路是环 游图中所有的顶点，而欧拉回路是环游图中所有的边。对于一个图是否存在欧拉环 游，存在一个非常简洁的判别法。那么判别一个图是否存在哈密尔顿回路是否也存 在这样一个非常简洁的判别法吗? 遗憾的是直到目前为止，还没找到哈密尔顿图的 充分必要条件，事实上，寻找哈密尔顿图的充分必要条件几乎是无望的。但是人们 希望找到哈密尔顿图的简明有效的的充分条件，这就是图论中一个著名的问题：哈 密尔顿图的问题。“棋盘的骑士问题”实际上就是要判断它所对应的图是否是哈密 尔顿图的问题。 箜三主堕童玺塑堕塑型塞 - _ _ _ _ _ _ _ - _ - 一一 第三章哈密尔顿图的的判定 给你一个图，你怎么知道它是否是哈密尔顿图呢? 当然如果图的顶点不多，你 可以用最古老的“尝试和错瀑”的方法试试找哈密尔顿回路就可以解决和判断。但 是数学家并不满意这样的碰得焦头烂额后才找到真理的方法。是否存在一组必要和 充分的条件，使得我们能简单轻易地判断一个图是否哈密尔顿图? 许多聪明人去试 过了，遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件。虽然 有些充分非必要，或必要非充分条件，但在大部分情况下，还是采用尝试的办法。 不过这些条件也非常有用。 我们先给出一个简单而有用的必要条件叽 定理1 ：设无向图g = ( v ，e ) 是哈密尔顿图，v 。是v 的任意的非空子集，则：p ( g 一- v t ) j v ，j 。 其中，p ( g v 1 ) 为从g 中删除v ( 删除v 中各顶点及关联的边) 后所得图的连通分 支数。 证明：设c 为g 中的一条哈密尔顿回路。 ( 1 ) 若v 中的顶点在c 上彼此相邻，则 p ( c v ，) = 1 l v ( 2 ) 设v ，中的顶点在c 上存在r ( 2 r l v ，f ) 个互不相邻，则 一般说来，v 中的顶点在c 上既有相邻的，又有不相邻的，因而总有 又因为c 是g 的生成子图，故 p ( gv ) p ( c v ，) i v 哈密尔顿图的应用 图3 1 图3 1 中，虽然对任意的结点集合v ，都满足p ( gv ) lv ，但它仍然不是哈 密尔顿图。由此可见，定理l 有时可以用来证明某一特定的图是非哈密尔顿图，可 是，这个方法并不总是有效的。 现在我们讨论哈密尔顿图的充分条件刚o ： 由于一个图是哈密尔顿图，当且仅当它的基础简单图是哈密尔顿图，所以我们 只考虑简甲图。 最早的结果是英a 狄拉克( d i r a c ) 在1 9 5 2 年给出一个充分条件使得一个图是 哈密尔顿图。围数学家g a 狄拉克( d i r a c ) 在1 9 5 2 年给出一个充分条件使得一 个图是哈密尔顿图。他的定理是只要检查每一个顶点x ，看它的上而有多少个弧通过， 把这个数目用d ( x ) 来表示，只要每一个点的c l ( x ) 是相当大的话，这个图就会是 哈密尔顿图。 定理2 ( 狄拉克定理) ：给定一个图g ，如果其顶点集v 的元素数是n 3 ， 而 且d ( x ) ，那么g 一定是哈密尔顿图。 由于我们可以看到以下的两个图g 。，g 。都是哈密尔顿图( 见图3 2 ) 。 在g 中，每个点x 有d ( x ) ：3 ，明显3 昙。在g ，中，每个点有【j ( x ) = 4 ，明显 4 旦。 第三章哈密尔顿圈的判定 4 s e 图3 2 到了1 9 6 0 年，美国著名的图论专家奥斯坦奥勒( o y s t e i no r e ) 推广狄拉克 的工作，得到以下的结果。 定理3 ( 奥勒定理)给定一个图g ，如果其顶点集v 是有n 3 点，而对于任 意两点x ，y 我们有d ( x ) + d ( y ) n ，那么g 一定是哈密尔顿图。 在1 9 6 2 年，匈牙利有一个名叫博萨( p o s a ) 少年发表了一篇只有一页长的论文， 他的结果却是推广了以上奥勒的定理，他的工作非常重要，引起了许多人谈论，并 且在图论的教科书上刊登了他的证明。以后几年来许多人想要改进这： 作，最后才 由一个捷克青年数学家得到比他更好的结果。 为了能更容易看清博萨的结果，我这里引进几个记号：对于每一个图g ，我们用 d ( g ) 来表示序列如( d ( x ) ，d ( x ：) ，d ( x n ) ) ，这里x 。，x 。是g 的所有顶 点，而序列的数是从小排到大排列。 比方说在图3 2 里我们有 d ( g 。) = ( 3 ，3 ，3 ，3 ) d ( g 。) = ( 4 ，4 ，4 ，4 ，4 ，4 ) 假定我们有两个序列具有相同个数的数字： x = ( x 【，x 2 ，x 3 ，x 。) ； y = ( y l ，y 2 ，y 3 ，y 。) 我们用x y 表示当且仅当对于每个i = l ，2 ，n ，我们都有x i y ，。 比方说，x = ( 1 ，2 ，3 ，4 ，5 ) ，y = ( 2 ，3 ，5 ，7 ，9 ) ，z = ( 4 ，2 ，1 ，3 ，5 ) ， 我们就有x y ，而x z 是不对的。 哈密尔顿图的应用 现在对于每个n 3 的整数，我们定义这样的整数序列p ( n ) ( i ) 如果n 是偶数，我们有n 个数按照下面由小到大的排法 p ( n ) = ( 2 ，3 ，4 ，5 ，。一，詈一2 ，詈一，薹，兰，兰) ( 2 ) 如果n 是奇数，我们有n 个数按照下面由, j 唾f j 大的排法 p ( n ) = ( 2 ，引，5 i ，字，雩，字 n l 根据定义我们有 p ( 3 ) = ( 1 ，2 ，2 ) ， p ( 4 ) = ( 2 ，2 ，2 ，2 ) n + 1 2 p ( 6 ) = ( 2 ，3 ，3 ，3 ，3 ，3 ) 以及 ( 读者请注意我们是怎样定义这序列 现在我们可以叙述博萨的重要发现 n4 - 1 2 定理4 ( 博萨定理)如果一个有n 3 个顶点的图，它的d ( g ) 满足不等式 d ( g ) p ( n ) ，那么g 是哈密尔顿图。 让我们看以下的图3 3 ( a ) 及( b ) ，读者很容易地看出 它们都是哈密尔顿图。g 。不满足奥勒的条件，因为 d ( x ) + d ( y ) = 2 + 2 = 4 ，并不大过5 。 可是我们却看到 苎三童堕童堡塑笪堕型星一一 d ( g ：。) = ( 2 ，2 ，3 ，3 ，4 ) ( 2 ，2 ，3 ，3 ，3 ) 2 p ( 5 ) 因此由博萨定理知道它是哈密尔顿图。由这个例子说明了博萨的结果是比奥勒 的强。然而我们却由g 。看到它并不满足博萨的不等式。因此人们尝试想找比博萨更 好的不等式以判别更多的哈密尔顿图。 到目前来说，比较好的工作是捷克青年数学家萨瓦达( v c h v 6 t a l ) 在1 9 7 2 年 的发功1 ，他的结果如下： y 图3 3 定理5 ( 萨瓦达定理) ：如果图g 的顶点数n 是大过2 ，而其d ( g ) ) 满足底下的条件： 对于每个小于兰的正整数i ，两个不等式 a i - 1 ，a 。r l i 最少有一个成立，那么g 一定是哈密尔顿图。 对数学有兴趣的读者可以试证明博萨的结果是包含在萨瓦达定理。我们的g 一图 显示它不满足萨瓦达的条件”，因此我们相信会存在比萨瓦达还要好的条件，这个 问题就留给读者自己去寻找。 下面我们介绍与哈密尔顿图有关的应用问题。 哈密尔顿图的应用 第四章旅行货郎问题 设有n 个城镇，已知每两个城镇之间的距离，一个售货员l 8 某一城镇出发，巡 回售货，问这个售货员应该如何选择路线，能使每个城镇经过一次且仅次，又回 到原出发地，而使总的行：程最短。这个问题称为旅行货郎问题。实际上旅行货郎问 题就是在一个赋权完全图中，找一个具有最小权的哈密顿路，最后又回到原出发地， 就是找。 也就是蜕：如果现在有一个图g ，而这图的每一条弧上都标上一个数字，怎样爿 能找到这图的哈密顿回路具有所有的弧上数字的和是最小值的性质，这个问题就是 数学上大名鼎鼎的难题：“旅行货郎问题”。 这问题在1 9 3 2 年由德国著名数学家k i v i e n g e r 提出【1 7 】，这7 0 多年来一直是许 多人废寝忘食研究的对象。 实际中很多问题都可以归结为旅行货郎问题。如：物资运输路线的设计，汽车 应走怎样的路线使空车路线最短；1 厂里在钢板上一些地方要挖去小圆孔，自动焊 机割咀应该走怎样的路线，使空走的路线最短；城市里在一些地方铺设管道时，管 道应该走怎样的路线，刁使管道的耗费最少等等。 我们在日常生活中也会遇到这问题，比方说： ( 1 ) 你是学校校车的司机，你从学校开车出来，到不同的街道去接孩子，你要怎 样安排才能使走的路程最短，可以按到所有的孩子回到学校去? ( 2 ) 春假到了，你想驾车在北美几个城市旅行，可是现在汽油是这么昂贵，你 想要尽量省用油，汽油的消耗是和路程成正比，因此你想法子找一个回路具有最短 的路程。 ( 3 ) 你为了商业业务，需要乘飞机飞几个城市，不同的飞机公司提供不同的票 价，你要怎样安排行程，使到你能走遍你要去的城市，最后又回来原出发地，而又 能省钱? 这些问题表面上似乎没有关系，而实质上都可以归结为“旅行货郎问题”来解 决。既然这个问题有着如此广泛的应用，那么要找出一个行之有效及能迅速提供解 答的方法，找到一个求解最优哈密顿回路的有效算法就成为一机一件很重要的事。 第四章旅行货郎问题 遗憾的是，到目前为止，还没有一个求最优解的方法。在】963 年，美国的管 理科学( m a n a g e m e n ts c i e n c e ) 中一篇讨论“旅行货郎问题”的文章就说道： “人类由于他的运算能力的限制在解决旅行货郎问题上并不好。”人们现在对于这问 题的实际情形都是借助高速的电子计算机来运算。 所以，人们在不断的寻找以获得相当好的解的方法。1 9 7 9 年1 1 月7 日纽约时 报出现一篇引人注目的文章，它的标题是：苏联的发现震动数学界( s o v i e t d i s c o v e r yr o c k sw o r l do f m a t h e m a t i c s ) ，这文章介绍个本是默默无闻的年青 数学家卡倩( l g k h a c h i a n ) ，他在线性规划理论上的一个发现使到美国数学界为 之轰动a 由于记者在询问一些著名数学家时对数学问题了解不深，文章报导是有 些失实，但由这文章引起的轰动及误导是相当严重。该文中说：“俄国人的发现建议 用电子计算机处理一类和旅行货郎问题( t r a v e l l i n gs a l e s 1 a np r o b l e m ) 有关 的数学上一个著名及难处理的问题。旅行货朗问题目的是决定一个货郎( 或推销 员或销货员) 所要跑的最短路程他要走遍市镇，但是不能再回到走过的地方。 n n 上，这问题看来简单，事实上为了要解决这问题的实际应用，人们需要电子计 算棚来解决。” 在这点上记者是说对了。“旅行货郎问题目前是许多国家( 如西德、日本、苏 联、英国、美国、法国) 的运筹学工作者研究的热门课题。 目前解“旅行货郎问题”有很多种方法，由于大部分要牵涉到较深的数学知识， 因此不在这里介绍a 我在以下会介绍一种直观而又容易明白的树的搜索法来寻找屠 优解。 德国人很喜欢精确的数学，在1 9 7 8 年，波恩大学有一位数学家想要知道在西德 的1 2 0 个有铁路穿过的城市要安排个最短路程的回路，应该怎么样跑。他从铁路 局找到了准确的城市间铁路的长度，整个问题变成一个有7 1 4 0 个变数，1 2 0 个方程 及9 6 个不等式的线性规划问题，用电子计算机去算得到最短的回路是6 9 4 2 公里。( 见 图4 ，1 ) 。 哈密尔顿图的应用 图4 1 德国1 2 0 个城市最短回路的解答 我这里举一个例子说明这个方法，假定我现在有四个城市a ，b ，c ，d ，它们之 间的路程是由下面的表给出( 见图4 2 ) ： 要找从a 出发回到a 的最短回路。 图4 2 第四章旅行货郎问题 我们从a 出发，写：( a ) 0 。0 是表示最初没有出发路线长是0 ，然后我列下所 有可能的下一个站：b ，c ，d ，然后我得到三个节点( n o d e ) ：( a b ) 1 ，( a c ) 3 ，( a d ) 2 。 ( e ) “b c ) ( f ) ( a b c ) 5 “d d ) 8 卜一 j(act(acd)v-i 5 ( m ) 7 ( 。函9 、a 删f “ ( b c d ) 10 ) 2 ( k ) 图4 3 5 纶 凛协 气 孙 r 锄 一 儿 哈密尔顿图的应用 这时就把( a ) 0 划掉，然后找节点具有最小的数值，这里是( a b ) l 。从b 我可 以走的站是c 和d ，就划掉( a b ) l ，用( a b c ) 1 + 4 及( a b d ) 1 + 7 来取代。为什么( a b c ) 旁的数字是i + 4 呢? 因为它是( a b ) 加上( b c ) 的长。( 见图4 3 ) 。 我们把没划掉的节点中有最小长度的找出，这是( a d ) 2 的下一个可能的站是b 和c ，因此我们划掉( a d ) 2 补上两个节点( a d b ) 2 + 7 及( a d c ) 2 + 5 。 我们继续找具有最小长度的节点，这时看到是( a c ) 3 从c 出发可以到达b 或d ， 于是我们划掉( a c ) 3 ，补上( a c b ) 3 + 4 ，( a c d ) 3 + 5 。( 见图4 3 ( e ) ) 我们再搜索有最小长度的节点，看到是( a b c ) 5 ，于是划掉它，补上( a b c d ) 5 + 5 ，得图4 3 ( f ) 。 我们再搜索没有被划的节点，看到有最小长度的是( a c b ) 7 及( a d c ) 7 ，我就 先划掉( a c b ) 7 补上( a c b d ) 7 + 7 ，得图4 3 ( g ) 。 然后我再划掉( a d c ) 7 补上( a d c b ) 7 + 4 得图4 3 ( h ) 。 这时候我看剩下没划线的最小长度的节点是：( a b d ) 8 及( a c d ) 8 ，我划掉了比方说 ( a b d ) 8 ，补上( a b d c ) 8 + 5 。 我再寻找最小长度的节点得( a c b ) 8 ，划掉之后补上了( a c d b ) 8 + 7 ，得图4 3 ( j ) 。 现在变成( a d b ) 9 是最小长度的节点，我们划掉补上( a d b c ) 9 + 4 ，得图4 3 ( k ) ， 我们划去( k ) 的最小长度节点( a b c d ) i o ，补上( a b c d a ) 1 0 + 2 。我们已得到一个 回路了，这时我们把( 1 ) 图中所有长度大过1 2 ，节点全划掉，因为这些节点所产生 的回路肯定要大过1 2 ，我们可以不考虑，我们只剩下( a d c b ) l l ，划掉它之后补上 ( a d c b a ) 1 1 + 1 ，我们得( k ) 。 谢天谢地，到此时再没有什么节点可以划了，我们得到两个回路( a b c d a ) 及 ( a d c b a ) ，它们的长都是1 2 。这种方法在数学上有一个名称叫u n i f o r m c o s ts e a r c h 。 为了说明整个搜索的程序，上面画了许多像树枝分叉的图，实际上大家只需在一个 图上划线及向下发展不必画这么多树。通常哈密尔顿回路找到之后，我们选取最少 的长度，那就是我们所要的答案。 我们前面介绍的方法在城市数目字比方说不超过十个还不显得可怕。如果现在 有2 1 个城市用以上的方法去搜索最短的回路，我们最少要找超过九十万个以上的路 第四章旅行货郎问题 线，这是多么巨大的数字呀! 现在请想一想，如果我们要处理的是五百个城市，或者一千个城市，或者就拿 像中国这么大的国家，这么多的县城，要处理这问题，用目前最快速的电子计算机 来协助，也会使电子计算机挂投降的白旗。前面介绍的树的搜索法是一个比较简单 但并不是太好的方法，多年来，许多人想出一些方法想要改进，希望能找到一个较 理想的方法，可以快速的找到结果。目前来说这样理想的方法还没有找到。 什么样的方法算是理想呢? 我们这里给个粗略的解释：比方说我们要用电子 计算机来帮我们工作，例如处理n 个城市的旅行货郎问题，当我把n 个城市的距离 表喂给电子计算机之后，它就会步一步的去找。如果它要得到答案，所要花费的 步骤数目是可以用n 的函数f ( n ) 来表示。我们说这方法是“理想”，当f ( n ) 是 个n 的多项式。 目前我们的方法都不是理想的。如果你真能找到一个理想的方法，你的成果会 轰动全世界。你的方法可以转化用来解决许多数学的难题及电子计算机理论的一些 著名难题。 旅行货郎问题是许多国家的运筹学研究中心的工作者深入研究的问题。在美国 的华籍数学工作者在这方面有很好的结果的有l i ns h e n 及h o n gs a m a n 等人。在1 9 7 7 年h o n g 先生和p a d b e r g 合作用电子计算机处理有3 1 8 个城市的“旅行货郎问 题” 1 2 - 1 3 ，这个问题化成线性规划问题就要处理有5 0 4 0 3 个变数( v a r i a b l e s ) 的方 程式，及不等式，如果不借助电子计算机的快速计算，我想就是请一位能笔算及心 算很快的数学家，让他穷十年的时间也是不能解决。以上的问题他们用i b m3 7 0 1 6 8 式的电子计算机，只花2 8 3 8 分钟就得到个最优解。 “玩物丧志”，这是以前老一辈的人骂儿童或少年不读书只喜欢游戏所爱用的一 句话。其实游戏和玩具可以引导大发现。如果有青少年肯对哈密尔顿图及旅行货郎 问题下点苦功研究，我会说他们是“玩物立志”，很可能以后会出一些在这些问题上 作出大贡献的中国人。 堕矍堡塑鬯塑堕望 _ _ - 一一 第五章建模案例：最佳灾情巡视路线”印”7 1 这里介绍1 9 9 8 年全国大学生数学模型竞赛b 题中的两个问题。 一、问题的提出 1 9 9 8 年夏天，我国部分地区遭受水灾，为考察灾情、组织自救，某县领导决定， 带领有关部门负责人到全县各乡( 镇) 、村巡视。巡视路线指从县政府所在地出发， 走遍各乡( 镇) 、村，又回到县政府所在地。 全县乡镇、村的公路网示意图见图5 1 ，公路边的数字为该路段的距离，单位为 k m 。 图5 1 1 若分三组( 路) 巡视，试设计总路程最短且各组尽可能均衡的路线。 2 假定巡视人员在各乡( 镇) 停留时间t = 2 小时，在各村停留时间t - - 1 小时， 汽车行驶速度v = 3 5 公里j 、时。要在2 4 小时内完成巡视，至少应分几组；给出这种 分组下最佳的巡视路线。 第五章建模寨例：最佳灾情巡视路线 间 二、假设 1 该县虽然受到水灾，但公路仍然畅通； 2 汽车在路上的速度总是定，不会出现抛锚等现象 3 每个小组的汽车行驶速度完全一样 4 可以经过同条路线； 5 巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时 6 分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外 7 驾驶员能持续作业，不影响平均速度 8 邻县村、镇不需要巡视。 三、模型的建立与求解 将公路网图中，每个多( 镇) 或村看作图中的一个节点，各乡( 镇) 、村之间的 公路看作图中对应节点问的边，各条公路的长度( 或行驶时间) 看作对应边上的权， 所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定 点o 出发，行遍所有顶点至少一次再回到o 点，使得总权( 路程或时间) 最小，此 即最佳推销员回路问题。 在加权图g 中求最佳推销员回路问题是n p 一完全问题，我们采用一种近似算法 求出该问题的一个近似最优解，来代替最优解，算法如下 1 4 - 1 7 】： 算法一求加权图g ( v ，e ) 的最佳推销员回路的近似算法： 1 用图论软件包求出o 中任意两个顶点间的最短路，构造出完备图g ( 矿，e ) ， v ( x ，y ) ee ，埘g ，y ) = m i n d g 0 ，y ) ； 2 输入图g 的一个初始h 圈： 3 用对角线完全算法( 见 2 3 ) 产生一个初始h 圈； 4 随机搜索出g 中若干个h 圈，例如2 0 0 0 个： 1 q 哈密尔顿图的应用 5 对第2 、3 、4 步所得的每个h 圈，用二边逐次修正法进行优化，得到近似最 佳h 圈； 6 在第5 步求出的所有h 圈中，找出权最小的一个，此即要找的最佳h 圈的 近似解。 由于二边逐次修正法的结果与初始圈有关，故本算法第2 、3 、4 步分别用三种方 法产生初始圈，以保证能得到较优的计算结果。 问题一若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线。 此问题是多个推销员的最佳推销员回路问题即在加权图g 中求顶点集v 的划分 h ，吒，将g 分成n 个生成子图c a l o v j 科k 】，使得 ( 1 ) 顶点o ( 2 ) 0r ，：y ( g ) ( 3 ) 竺兰! 竺! ! ：! 兰：! ；。，其中c ，为k 的导出子图g 眈 中的最佳推销员回路， m a xc o i f 1 珊( c 。) 为c 。的权，i ，j = l ，2 ，3 n ( 4 ) 兰。( c ，) ：m i 一 定义 称! ! 篁i 竺：竺! ! ：竺：笙：! 为该分组的实际均衡度口为最大容许均衡 “o m a x ( c ，) 度。 显然0 1 ，越小，说明分组的均衡性越好取定一个口后，与口满足 条件( 3 ) 的分组是一个均衡分组条件( 4 ) 表示总巡视路线最短。 此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路，即 为单个推销员的最佳推销员问题。 由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多个 推销员的问题也不存在多项式时间内的精确算法而图中节点数较多，为5 3 个，我们 只能去寻求一种较合理的划分准则，对图5 1 进行初步划分后，求出各部分的近似最 佳推销员回路的权，再进一步进行调整，使得各部分满足均衡性条件( 3 ) 。 笙墨主垄垡窒型! 垦堡壅堕坐塑堕垡 图5 20 点到任意点的最短路图( 单位：公里) 从0 点出发去其它点，要使路程较小应尽量走0 点到该点的最短路。故用图论 软件包求出0 点到其余顶点的最短路，这些最短路构成一棵0 为树根的树，将从0 点出发的树枝称为千枝，见图11 一l0 ，从图中可以看出，从0 点出发到其它点共 有6 条干枝，它们的名称分别为，。 根据实际工作的经验及上述分析，在分组时应遵从以下准则： 准则一：尽量使同一千枝上及其分枝上的点分在同一组； 准则二：应将相邻的干枝上的点分在同一组； 准则三：尽量将长的干枝与短的干枝分在同一组。 由上述分组准则，我们找到两种分组形式如下： 分组一：( ，) ，( ，) ，( ，) 分组二：( ，) ，( ，) ，( ，) 显然分组一的方法极不均衡，故考虑分组二。 对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路线。 使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图5 2 中树上的边的 h 圈作为其第2 步输入的初始圈。 哈密尔顿图的应用 分组二的近似解见表5 1 。 表5 1 ( 单位：公里) 小组名称路线总路线长度路线的总长度 o p 2 8 2 7 2 6 n 2 4 2 3 2 2 1 7 1 6 一i i1 9 1 1 1 5 一i 1 8 k 2 l 一2 0 2 5 m 一0 0 2 - 5 6 一l 一1 9 一j 1 1 一g 1 3 1 4 一h 一1 2 - 1 12 4 1 95 5 85 f 1 0 一f 一9 一e ，7 e 一8 4 一d 3 c o r - 2 9 - q - 3 0 3 2 3 1 - 3 3 3 5 3 4 - a - i l l1 2 55 b 一1 o 表5 2 ( 单位：公里) 路线路线总 编号路线 长度长度 o p 一2 8 2 7 2 6 一n 2 4 2 3 2 2 一1 7 i1 9 11 1 6 i 一1 5 一卜一1 8 一k 一2 1 2 0 _ 2 5 一m 一0 o 一2 5 6 7 一e 一8 e 一9 _ f l0 一f 一 i i1 2 一h 1 4 1 3 一g 一1 1 一j 一1 9 一l 一6 52 1 6 45 9 9 8 2 一o 0 一r 一2 9 一q 一3 0 3 2 3 1 3 3 3 5 3 4 一 1 1 1 1 9 2 3 a 一1 一b c 一3 d 一4 一d 一3 2 一o 第五章建模案例：最佳灾情巡视路线 因为该分组的均衡度= 竺坚12 二竺坚! ! ：丝! ：! 二! 翌：! ：5 4 2 m a x l c ，) 2 4 1 9 所以此分法的均衡性很差。 为改善均衡性，将第1 i 组中的顶点c ，2 ，3 ，d ，4 分给第1 i i 组( 顶点2 为这两 组的公共点) ，重新分组后的近似最优解见表2 。 因该分组的均衡度2 竺蒌羹云器字= 型掣= t 所以这种分法的均衡性较好。 问题二当巡视人员在各乡( 镇) 、村的停留时间一定，汽车的行驶速度一定 要在2 4 小时内完成巡视，至少要分几组及最佳的巡视路线。 由于t = 2 小时，t = l 小时，v = 3 5 公里仆时，需访问的乡镇共有1 7 个，村共有 3 5 个计算出在乡( 镇) 及村的总停留时间为17 x 2 + 3 5 = 6 9 小时，要在2 4 小时内完 成巡回，若不考虑行走时间，有：6 9 2 4 ( f 为分的组数) 得i 最小为4 ，故至少要 f 分4 组。 由于该网络的乡( 镇) 、村分布较为均匀，故有可能找出停留时问尽量均衡的分 组，当分4 组时各组停留时间大约为旦：1 7 2 5 小时，则每组分配在路途上的时间大 约为2 4 1 72 5 = 6 7 5 小时而前面讨论过，分三组时有个总路程5 9 9 8 公里的巡视路线， 分4 组时的总路程不会比5 9 9 8 公里大太多，不妨以5 9 9 ，8 公里来计算路上时间约为 _ 5 9 9 8 ：1 7 小时，若平均分配给4 个组，每个组约需旦： 小时 小时，故分 、蚌a 42 5 67 5 成4 组是可能办到的。 现在尝试将顶点分为4 组分组的原则：除遵从前面准则一、二、三外，还应遵 从以下准则： 准则四：尽量使各组的停留时间相等。 用上述原则在图5 2 上将图分为4 组，同时计算各组的停留时间，然后用算法一算 出各组的近似最佳推销员巡回，得出路线长度及行走时间，从而得出完成巡视的近 哈密尔顿图的应用 似最佳时间用算法一计算时，初始圈的输入与分三组时同样处理。 这4 组的近似最优解见表5 3 。 表5 3 ( 路程单位：公里；时间单位：小时) 路线停留行走完成巡视 组名 路线 总长度 时间时问的总时间 o 一2 5 6 7 一e 一8 一誊一 i 1 1 一g 一1 2 一h 一孽k f 一1