22 格尼斯堡七桥问题.ppt

* * * * * * * 2.2 格尼斯堡七桥问题 * * 1.七桥漫步 格尼斯堡城是由条顿骑士团在1308年建立，曾作为东普鲁士的首府。第二次世界大战后，成为前苏联最大的海军基地。现在的格尼斯堡位于立陶宛和波兰之间。 在第二次世界大战时，法军经这里入侵波兰。后来苏军也从这里打进德国，所以格尼斯堡是一座名城。同时这里也诞生过许多伟大人物，其中包括18世纪著名的唯心主义哲学家康德和19世纪的大数学家希尔伯特。 但是，最早给这座城市带来声誉的横跨布列格尔河，把格尼斯堡连成一体的七座桥梁。 * 这一别致的桥群，引来了众多的游人，同时还引发了数学史上一项重要的研究。 * 一天又一天，这七座桥上走过了无数的行人，脚下的七桥触发了人们的灵感，一个有趣的问题在民间传开“能否在一次散步中每座桥都走一次，而且只能走一次，最后又回到原来的出发点？” 这个问题看似简单，人人都乐意去测试一下自己的智力，可是把全城人的智力加在一起，也没有找到一条合适的路线。这个问题传开以后，许多欧洲有学问的人也参与思考，同样是一筹莫展。就这样，格尼斯堡这个“七桥问题”给人们提供了丰富的乐趣和数学兴味，因而使得这座波罗的海的海滨古城闻名遐迩。 * 2.欧拉与格尼斯堡七桥问题 1735年有几名大学生写信给当时正在俄国彼得堡科学院任职的天才数学家欧拉，请他帮助解决。欧拉并未轻视生活中的小问题，他似乎看到了其中隐藏某种新的数学方法。 事实上，要走遍七座桥的所有走法有 种，要想一一试验是不可能的，只能另找一种新方法。欧拉依靠他深厚的数学功底，运用娴熟的变换技巧，经过一年的研究，于1936年，29岁的欧拉向彼得堡科学院提交了一份为《格尼斯堡七桥》的论文，圆满的解决了这一问题。欧拉不仅解决了七桥问题，而且他提出飞思想导致了一门新的数学分支——“图论”的诞生。 * 欧拉是如何解决七桥问题的？又是如何证明要想一次走过七座桥是不可能的呢？欧拉的方法十分巧妙： （1）不考虑4个地区的大小、形状，不妨将它们看成是链接桥梁的4个点； （2）不考虑桥梁的曲直、长短，不妨将它们看成连接4个点的7条线。 于是一座仪态万千的格尼斯堡古城在欧拉笔下就变成了一个结构简单是几何图形。 * 于是七桥问题就变成了用笔不重复的（笔不离开纸面）画出这个几何图形的问题，即“一笔画”问题。如果可以画出来，则必有一个起点和一个终点，如果这两点不重合，则与起点或终点相交的线必为奇数条（称为奇点），如果起点与终点重合，则与之相交的线必为偶数条（称为偶点），而除了起点与终点外，其他点也必为偶点。据以上分析，如果一个图形可以一笔画出来，则必须满足两个条件： （1）图形必须是连通的，即任一点通过一些线一定能达到其他任意点。（2）图中的奇点数只能是0或2. 回头来看七桥问题，4个点全为奇点，故七桥问题无解。 欧拉当时发表这一结果时，震惊了当时的数学界。 * 3.引申与推广 欧拉解决七桥问题的方法并不深奥，但他的新颖之处不仅在于另辟蹊径的解题思路，更在于“一笔画”问题虽然是一个几何问题，可是这种几何问题却是欧几里得几何里没有研究过的。 在“一笔画”问题里，长度、角度、面积、体积都没有了，四大块陆地变成了四个点；连线的长短曲直、交点的方位都无关紧要，要紧的只是点线之间的相关位置或相互连接的情况，如下两图都没有改变七桥问题“一笔画”的性质。 * 后来布勒格尔河上又架起第八座桥来——铁路桥，这又使人们想起了那有趣的问题。虽然一次不重复走遍七座桥不可能，那八座桥呢？从图中可以已看出，“奇点”只有两个（D、C），所以可以一次不重复走遍八座桥。 * 下图是国际奥林匹克运动会的会标，也可以“一笔画”。 其中一条线路可以是: A-B-A-BC-D-C-E-F-E-G-H-G-H-F-D-A * 4.新学科的形成 欧拉对七桥问题的解决之所以著名，不仅是因为它 的趣味性和欧拉解题思路的巧妙，更重要的是这个问题的解决开创了一个新的数学分支——图论。 图论就是运用直观的图形和数学方法来研究组和关系的一门新兴学科，原是组和数学的一个重要课题，由于发展迅速，现已成为一个独立的数学分支。它把被研究系统中的各个元素作为点，元素之间的关系作为线，然后画成图，通过对图形的研究，找出解决问题的办法。 * 图论为研究任何一类离散事物的关系结构提供了一种本质的框架，在经济、心理、社会、遗传、运筹、计算机、网络