《哥尼斯堡七桥难题.pdf》由会员分享，可在线阅读，更多相关《哥尼斯堡七桥难题.pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、从“哥尼斯堡七桥问题”谈到“中国邮递员问题”古城哥尼斯堡，景致迷人，碧波荡漾的普瑞格尔河横贯其境。普瑞格尔河的两岸及河中的两个美丽的小岛，由七座桥连接组成了这座秀色怡人的城市（如图）。古往今来，吸引了无数的游人驻足于此。早在十八世纪，哥尼斯堡属于德国东普鲁士(今俄罗斯加里宁格勒。1945 年德国战败根据波茨坦会议的决定将哥尼斯堡连同东普鲁士一部分地区割让给苏联，次年为纪念刚逝世的苏联共产党和苏维埃国家领导人米哈伊尔加里宁，柯尼斯堡更名为加里宁格勒)。那时候，哥尼斯堡市民生活富足。市民们喜欢四处散步，于是便产生这样的问题：是否可以设计一种方案，使得人们从自己家里出发，经过每座桥恰好一次，最后回到
2、家里。这便是著名的“哥尼斯堡七桥问题”。热衷于这个有趣的问题的人们试图解决它，但一段时间内竟然没有人能给出答案。后来，问题传到了瑞士著名数学家欧拉那里，居然也激起了他的兴趣。他从人们寻求路线屡遭失败的教训中敏锐地领悟到，也许这样的方案根本就不存在。欧拉经过悉心的研究，1736年，年方 29 岁的欧拉终于解决了这个问题，并向圣彼得堡科学院递交了一份题为哥尼斯堡的七座桥的论文。论文不仅仅是解决了这一难题，而且引发了一门新的数学分支图论的诞生。论文的核心就是著名的“一笔画原理”：对满足下列两个要求的图就可以一笔画出：i.首先是连通图；ii.其次奇点个数为 0 或 2，当且仅当奇点个数为 0 时，始点
3、和终点重合，形成的一笔画称为欧拉回路，而当奇点个数为 2 时，形成的一笔画称为欧拉迹。我们知道，对于可一笔画出的图，首先必须是连通的；其次对于图中的某点，如果不是始点或终点，那么它必有进有出，即交汇于此点的弧线总是成双成对的，此点必定是偶点。如图，七桥问题的图的奇点的个数为 4，这表明它不是欧拉回路，也不是欧拉迹，因而，不论始点和终点是否重合都不可能找到一条经过七座桥且每座桥只走一次的路线！随着时间的推移，图论不断发展，欧拉回路问题也有所拓广。就这样到了二十世纪，又出现了一个新的问题。一个邮递员，每次送信必须从邮局出发，走遍如图示的投递区域内的所有道路，最终回到邮局（图中路旁各数字分别表示对应
4、路段的长度，单位：华里）。他习惯按路线KHGFEDCBAIABJDEKJIHK投递（图中为邮局）。聪明的读者朋友，你知道他的路线是最短的吗？如果不是，请你帮助这位邮递员设计一条最短路线，并说明最短路线比他的路线少几华里？1959年，我国山东大学管梅谷等一批科研人员把物资调运中的图上作业法与一笔画原理科学地结合起来，解决了这类邮递员投邮路线问题，因此它被数学界称为“中国邮递员问题”。下面，我们一起来分析这个问题：由于网络的奇点必定成双，又图中奇点有 6 个，根据一笔画原理，此图不存在欧拉回路，则必须通过添加弧线，使每个顶点均变成偶点，同时考虑添加的弧线长度总和最短才满足要求。显然两奇点间可直接添
5、弧一条；奇点与偶点间添弧一条且此偶点还须与另一奇点添弧一条；两偶点间不必添弧。添弧时应注意：（1）不能出现重迭添弧。重迭添弧应成对抹去，这样并不改变每一点的奇偶性；（2）每一个圈上的添弧总长不能超过圈长一半。否则应将此圈上的原添弧抹去，而在此圈上原没有添弧的路线上加添弧，这样也不改变每一点的奇偶性。注意了（1）、（2），既保证了不改变每点奇偶性，又保证了添弧总长最短。现在我们看邮递员的投邮路线，如图 1。添弧后的新图形已是不含奇点的脉胳，根据一笔画原理，这个脉胳的全部弧线可构成一条欧拉回路。对照（1）、（2）可知，图中添弧总长不是最短，必须调整。显然在ABJKHI圈中，添弧总长超过了该圈长一半
6、。调整后，如图 2。此时，添弧不重迭并且每一个圈上的添弧总长都不超过本圈长的一半。另外，每点奇偶性相对于图 1 没有改变，全是偶点。全部弧线仍可构成一条欧拉回路，并且这条路线才是最短投邮路线。因此，邮递员的投邮路线并非最短。根据以上分析，最短投邮路线可设计为：KHGFEDCBAIHIJBJDEKJK或KJKHGFEDCBAIHIJBJDEK等等。此时，最短路线比邮递员路线少 0.8 华里。中国邮递员问题的巧妙解决，也使它成为数学知识古为今用的典范。读者朋友，你还记得牛顿的名言吗？“如果我比笛卡尔看得远些，那是因为我站在巨人们的肩上的缘故。”今天我们必须继承前人给我们留下来的宝贵知识财富，认真学习科学文化知识，不断创新，发扬光大，继往开来！