格尼斯堡七桥问题.ppt

《格尼斯堡七桥问题.ppt》由会员分享，可在线阅读，更多相关《格尼斯堡七桥问题.ppt（15页珍藏版）》请在装配图网上搜索。

1、2.2格尼斯堡七桥问题,1,2,1.七桥漫步,格尼斯堡城是由条顿骑士团在1308年建立，曾作为东普鲁士的首府。第二次世界大战后，成为前苏联最大的海军基地。现在的格尼斯堡位于立陶宛和波兰之间。,在第二次世界大战时，法军经这里入侵波兰。后来苏军也从这里打进德国，所以格尼斯堡是一座名城。同时这里也诞生过许多伟大人物，其中包括18世纪著名的唯心主义哲学家康德和19世纪的大数学家希尔伯特。,但是，最早给这座城市带来声誉的横跨布列格尔河，把格尼斯堡连成一体的七座桥梁。,3,这一别致的桥群，引来了众多的游人，同时还引发了数学史上一项重要的研究。,4,一天又一天，这七座桥上走过了无数的行人，脚下的七桥触发了人

2、们的灵感，一个有趣的问题在民间传开“能否在一次散步中每座桥都走一次，而且只能走一次，最后又回到原来的出发点？”,这个问题看似简单，人人都乐意去测试一下自己的智力，可是把全城人的智力加在一起，也没有找到一条合适的路线。这个问题传开以后，许多欧洲有学问的人也参与思考，同样是一筹莫展。就这样，格尼斯堡这个“七桥问题”给人们提供了丰富的乐趣和数学兴味，因而使得这座波罗的海的海滨古城闻名遐迩。,5,2.欧拉与格尼斯堡七桥问题,1735年有几名大学生写信给当时正在俄国彼得堡科学院任职的天才数学家欧拉，请他帮助解决。欧拉并未轻视生活中的小问题，他似乎看到了其中隐藏某种新的数学方法。事实上，要走遍七座桥的所有

3、走法有种，要想一一试验是不可能的，只能另找一种新方法。欧拉依靠他深厚的数学功底，运用娴熟的变换技巧，经过一年的研究，于1936年，29岁的欧拉向彼得堡科学院提交了一份为格尼斯堡七桥的论文，圆满的解决了这一问题。欧拉不仅解决了七桥问题，而且他提出飞思想导致了一门新的数学分支“图论”的诞生。,6,欧拉是如何解决七桥问题的？又是如何证明要想一次走过七座桥是不可能的呢？欧拉的方法十分巧妙：（1）不考虑4个地区的大小、形状，不妨将它们看成是链接桥梁的4个点；（2）不考虑桥梁的曲直、长短，不妨将它们看成连接4个点的7条线。,于是一座仪态万千的格尼斯堡古城在欧拉笔下就变成了一个结构简单是几何图形。,7,于是

4、七桥问题就变成了用笔不重复的（笔不离开纸面）画出这个几何图形的问题，即“一笔画”问题。如果可以画出来，则必有一个起点和一个终点，如果这两点不重合，则与起点或终点相交的线必为奇数条（称为奇点），如果起点与终点重合，则与之相交的线必为偶数条（称为偶点），而除了起点与终点外，其他点也必为偶点。据以上分析，如果一个图形可以一笔画出来，则必须满足两个条件：（1）图形必须是连通的，即任一点通过一些线一定能达到其他任意点。（2）图中的奇点数只能是0或2.回头来看七桥问题，4个点全为奇点，故七桥问题无解。欧拉当时发表这一结果时，震惊了当时的数学界。,8,3.引申与推广,欧拉解决七桥问题的方法并不深奥，但他的新

5、颖之处不仅在于另辟蹊径的解题思路，更在于“一笔画”问题虽然是一个几何问题，可是这种几何问题却是欧几里得几何里没有研究过的。在“一笔画”问题里，长度、角度、面积、体积都没有了，四大块陆地变成了四个点；连线的长短曲直、交点的方位都无关紧要，要紧的只是点线之间的相关位置或相互连接的情况，如下两图都没有改变七桥问题“一笔画”的性质。,9,后来布勒格尔河上又架起第八座桥来铁路桥，这又使人们想起了那有趣的问题。虽然一次不重复走遍七座桥不可能，那八座桥呢？从图中可以已看出，“奇点”只有两个（D、C），所以可以一次不重复走遍八座桥。,10,下图是国际奥林匹克运动会的会标，也可以“一笔画”。,其中一条线路可以是

6、:A-B-A-BC-D-C-E-F-E-G-H-G-H-F-D-A,11,4.新学科的形成,欧拉对七桥问题的解决之所以著名，不仅是因为它的趣味性和欧拉解题思路的巧妙，更重要的是这个问题的解决开创了一个新的数学分支图论。图论就是运用直观的图形和数学方法来研究组和关系的一门新兴学科，原是组和数学的一个重要课题，由于发展迅速，现已成为一个独立的数学分支。它把被研究系统中的各个元素作为点，元素之间的关系作为线，然后画成图，通过对图形的研究，找出解决问题的办法。,12,图论为研究任何一类离散事物的关系结构提供了一种本质的框架，在经济、心理、社会、遗传、运筹、计算机、网络、信息论、控制论、逻辑学、语言学、

7、物理学、化学、微电子技术、通讯科学、系统科学等方面都有广泛的应用。值得一提的是，对七桥问题的研究后来演变为对多面体的研究，得到了著名的欧拉公式：V+F=E+2，其中V、E、F分布是多面体的定点数、棱数和面数。这就是高中关于凸多面体的欧拉定理。这个定理是拓扑学的第一个定理，其使我们看到了几何问题更深刻的内涵性质。拓扑学已成为当前最为丰富多彩的一个数学分支。,13,5.最短邮路问题,最短邮路问题邮递员每天要走遍自己投递范围的大街小巷，怎样选择路线才能使邮路最短？我们把投递单位看做点，路线化作线，就可以用图论来解决了。右图为投递街道图，如果能一笔画，就能找到最短投递路线；如果一笔画不出来，问题就变成在不得不重复的情况下，寻找最短路线，这比一笔画问题更深入了。,14,如果一张图中奇点数大于2，并且是2的n倍，则该图至少需要n笔才能画成。如下图所示。,15,最短邮路问题是1960年由我国山东师范大学管梅谷教授提出并解决的，因此国际上称为“中国邮路问题”。,回头来看邮路图，其中有6个奇点，故至少要3笔才能画成，重复部分应该选择最短的邮路区间，故以下三种方案中，第三个方案最好。,