格尼斯堡七桥问题课件

1、格尼斯堡七桥问题12.2 2.2 格尼斯堡七桥问题格尼斯堡七桥问题格尼斯堡七桥问题21.1.七桥漫步七桥漫步 格尼斯堡城是由条顿骑士团在格尼斯堡城是由条顿骑士团在13081308年建立，曾作为东普鲁年建立，曾作为东普鲁士的首府。第二次世界大战后，成为前苏联最大的海军基地。士的首府。第二次世界大战后，成为前苏联最大的海军基地。现在的格尼斯堡位于立陶宛和波兰之间。现在的格尼斯堡位于立陶宛和波兰之间。 在第二次世界大战时，法军经这里入侵波兰。后来苏军也在第二次世界大战时，法军经这里入侵波兰。后来苏军也从这里打进德国，所以格尼斯堡是一座名城。同时这里也诞生从这里打进德国，所以格尼斯堡是一座名城。同时这

2、里也诞生过许多伟大人物，其中包括过许多伟大人物，其中包括1818世纪著名的唯心主义哲学家康德世纪著名的唯心主义哲学家康德和和1919世纪的大数学家希尔伯特。世纪的大数学家希尔伯特。 但是，最早给这座城市带来但是，最早给这座城市带来声誉的横跨布列格尔河，把格尼声誉的横跨布列格尔河，把格尼斯堡连成一体的七座桥梁。斯堡连成一体的七座桥梁。格尼斯堡七桥问题3 这一别致的桥群，引来了众多的游人，同时还引发了数学这一别致的桥群，引来了众多的游人，同时还引发了数学史上一项重要的研究。史上一项重要的研究。格尼斯堡七桥问题4 一天又一天，这七座桥上走过了无数的行人，脚下的七桥一天又一天，这七座桥上走过了无数的行

3、人，脚下的七桥触发了人们的灵感，一个有趣的问题在民间传开触发了人们的灵感，一个有趣的问题在民间传开“能否在一次能否在一次散步中每座桥都走一次，而且只能走一次，最后又回到原来的散步中每座桥都走一次，而且只能走一次，最后又回到原来的出发点出发点？” 这个问题看似简单，人人都乐意去测试一下自己的智力，这个问题看似简单，人人都乐意去测试一下自己的智力，可是把全城人的智力加在一起，也没有找到一条合适的路线。可是把全城人的智力加在一起，也没有找到一条合适的路线。这个问题传开以后，许多欧洲有学问的人也参与思考，同样是这个问题传开以后，许多欧洲有学问的人也参与思考，同样是一筹莫展。就这样，格尼斯堡这个一筹莫展

4、。就这样，格尼斯堡这个“七桥问题七桥问题”给人们提供了给人们提供了丰富的乐趣和数学兴味，因而使得这座波罗的海的海滨古城闻丰富的乐趣和数学兴味，因而使得这座波罗的海的海滨古城闻名遐迩。名遐迩。格尼斯堡七桥问题52.2.欧拉与格尼斯堡七桥问题欧拉与格尼斯堡七桥问题 17351735年有几名大学生写信给当时正在俄国彼得堡科学院任年有几名大学生写信给当时正在俄国彼得堡科学院任职的天才数学家欧拉，请他帮助解决。欧拉并未轻视生活中的职的天才数学家欧拉，请他帮助解决。欧拉并未轻视生活中的小问题，他似乎看到了其中隐藏某种新的数学方法。小问题，他似乎看到了其中隐藏某种新的数学方法。 事实上，要走遍七座桥的所有走

5、法有事实上，要走遍七座桥的所有走法有 种，要想一一试验是不可能的，只能另找一种新方法。欧拉依种，要想一一试验是不可能的，只能另找一种新方法。欧拉依靠他深厚的数学功底，运用娴熟的变换技巧，经过一年的研究，靠他深厚的数学功底，运用娴熟的变换技巧，经过一年的研究，于于19361936年，年，2929岁的欧拉向彼得堡科学院提交了一份为岁的欧拉向彼得堡科学院提交了一份为格尼斯格尼斯堡七桥堡七桥的论文，圆满的解决了这一问题。欧拉不仅解决了七的论文，圆满的解决了这一问题。欧拉不仅解决了七桥问题，而且他提出飞思想导致了一门新的数学分支桥问题，而且他提出飞思想导致了一门新的数学分支“图图论论”的诞生。的诞生。7

6、77!5040A 格尼斯堡七桥问题6 欧拉是如何解决七桥问题的？又是如何证明要想一次走过欧拉是如何解决七桥问题的？又是如何证明要想一次走过七座桥是不可能的呢？欧拉的方法十分巧妙：七座桥是不可能的呢？欧拉的方法十分巧妙： （1 1）不考虑）不考虑4 4个地区的大小、形状，不妨将它们看成是链接个地区的大小、形状，不妨将它们看成是链接桥梁的桥梁的4 4个点；个点； （2 2）不考虑桥梁的曲直、长短，不妨将它们看成连接）不考虑桥梁的曲直、长短，不妨将它们看成连接4 4个点个点的的7 7条线。条线。 于是一座仪态万千于是一座仪态万千的格尼斯堡古城在欧拉的格尼斯堡古城在欧拉笔下就变成了一个结构笔下就变成了

7、一个结构简单是几何图形。简单是几何图形。格尼斯堡七桥问题7 于是七桥问题就变成了用笔不重复的（笔不离开纸面）画于是七桥问题就变成了用笔不重复的（笔不离开纸面）画出这个几何图形的问题，即出这个几何图形的问题，即“一笔画一笔画”问题。如果可以画出来，问题。如果可以画出来，则必有一个起点和一个终点，如果这两点不重合，则与起点或则必有一个起点和一个终点，如果这两点不重合，则与起点或终点相交的线必为奇数条（称为奇点），如果起点与终点重合，终点相交的线必为奇数条（称为奇点），如果起点与终点重合，则与之相交的线必为偶数条（称为偶点），而除了起点与终点则与之相交的线必为偶数条（称为偶点），而除了起点与终点外，

8、其他点也必为偶点。据以上分析，如果一个图形可以一笔外，其他点也必为偶点。据以上分析，如果一个图形可以一笔画出来，则必须满足两个条件：画出来，则必须满足两个条件： （1 1）图形必须是连通的图形必须是连通的，即任一点通过一些线一定能达，即任一点通过一些线一定能达到其他任意点。（到其他任意点。（2 2）图中的奇点数只能是图中的奇点数只能是0 0或或2 2. . 回头来看七桥问题，回头来看七桥问题，4 4个点全为奇点，故七桥问题无解。个点全为奇点，故七桥问题无解。 欧拉当时发表这一结果时，震惊了当时的数学界。欧拉当时发表这一结果时，震惊了当时的数学界。格尼斯堡七桥问题83.3.引申与推广引申与推广

9、欧拉解决七桥问题的方法并不深奥，但他的新颖之处不仅欧拉解决七桥问题的方法并不深奥，但他的新颖之处不仅在于另辟蹊径的解题思路，更在于在于另辟蹊径的解题思路，更在于“一笔画一笔画”问题虽然是一个问题虽然是一个几何问题，可是这种几何问题却是欧几里得几何里没有研究过几何问题，可是这种几何问题却是欧几里得几何里没有研究过的。的。 在在“一笔画一笔画”问题里，长度、角度、面积、体积都没有问题里，长度、角度、面积、体积都没有了，四大块陆地变成了四个点；连线的长短曲直、交点的方位了，四大块陆地变成了四个点；连线的长短曲直、交点的方位都无关紧要，要紧的只是点线之间的相关位置或相互连接的情都无关紧要，要紧的只是点

10、线之间的相关位置或相互连接的情况，如下两图都没有改变七桥问题况，如下两图都没有改变七桥问题“一笔画一笔画”的性质。的性质。格尼斯堡七桥问题9 后来布勒格尔河上又架起第八座桥来后来布勒格尔河上又架起第八座桥来铁路桥，这又使铁路桥，这又使人们想起了那有趣的问题。虽然一次不重复走遍七座桥不可能，人们想起了那有趣的问题。虽然一次不重复走遍七座桥不可能，那八座桥呢？从图中可以已看出，那八座桥呢？从图中可以已看出，“奇点奇点”只有两个（只有两个（D D、C C），），所以可以一次不重复走遍八座桥。所以可以一次不重复走遍八座桥。格尼斯堡七桥问题10下图是国际奥林匹克运动会的会标，也可以下图是国际奥林匹克运动

11、会的会标，也可以“一笔画一笔画”。其中一条线路可以是其中一条线路可以是: :A-B-A-BC-D-C-E-F-E-G-H-G-H-F-D-AA-B-A-BC-D-C-E-F-E-G-H-G-H-F-D-A格尼斯堡七桥问题114.4.新学科的形成新学科的形成 欧拉对七桥问题的解决之所以著名，不仅是因为它欧拉对七桥问题的解决之所以著名，不仅是因为它 的趣味性和欧拉解题思路的巧妙，更重要的是这个问题的解决的趣味性和欧拉解题思路的巧妙，更重要的是这个问题的解决开创了一个新的数学分支开创了一个新的数学分支图论。图论。 图论就是运用直观的图形和数学方法来研究组和关图论就是运用直观的图形和数学方法来研究组和

12、关系的一门新兴学科，原是组和数学的一个重要课题，由于发展系的一门新兴学科，原是组和数学的一个重要课题，由于发展迅速，现已成为一个独立的数学分支。它把被研究系统中的各迅速，现已成为一个独立的数学分支。它把被研究系统中的各个元素作为点，元素之间的关系作为线，然后画成图，通过对个元素作为点，元素之间的关系作为线，然后画成图，通过对图形的研究，找出解决问题的办法。图形的研究，找出解决问题的办法。格尼斯堡七桥问题12 图论为研究任何一类离散事物的关系结构提供了一图论为研究任何一类离散事物的关系结构提供了一种本质的框架，在经济、心理、社会、遗传、运筹、计算机、种本质的框架，在经济、心理、社会、遗传、运筹、

13、计算机、网络、信息论、控制论、逻辑学、语言学、物理学、化学、微网络、信息论、控制论、逻辑学、语言学、物理学、化学、微电子技术、通讯科学、系统科学等方面都有广泛的应用。电子技术、通讯科学、系统科学等方面都有广泛的应用。 值得一提的是，对七桥问题的研究后来演变为对多面值得一提的是，对七桥问题的研究后来演变为对多面体的研究，得到了著名的欧拉公式：体的研究，得到了著名的欧拉公式：V+F=E+2V+F=E+2，其中，其中V V、E E、F F分分布是多面体的定点数、棱数和面数。这就是高中关于凸多面体布是多面体的定点数、棱数和面数。这就是高中关于凸多面体的欧拉定理。这个定理是拓扑学的第一个定理，其使我们看

14、到的欧拉定理。这个定理是拓扑学的第一个定理，其使我们看到了几何问题更深刻的内涵性质。拓扑学已成为当前最为丰富多了几何问题更深刻的内涵性质。拓扑学已成为当前最为丰富多彩的一个数学分支。彩的一个数学分支。格尼斯堡七桥问题135.5.最短邮路问题最短邮路问题 最短邮路问题最短邮路问题邮递员每邮递员每天要走遍自己投递范围的大街小巷，天要走遍自己投递范围的大街小巷，怎样选择路线才能使邮路最短？我怎样选择路线才能使邮路最短？我们把投递单位看做点，路线化作线，们把投递单位看做点，路线化作线，就可以用图论来解决了。就可以用图论来解决了。 右图为投递街道图，如果右图为投递街道图，如果能一笔画，就能找到最短投递路线；能一笔画，就能找到最短投递路线；如果一笔画不出来，问题就变成在如果一笔画不出来，问题就变成在不得不重复的情况下，寻找最短路不得不重复的情况下，寻找最短路线，这比一笔画问题更深入了。线，这比一笔画问题更深入了。格尼斯堡七桥问题14如果一张图中奇点数大于如果一张图中奇点数大于2 2，并且是，并且是2 2 的的n n倍，则该图至少需要倍，则该图至少需要n n笔才能画成。如下图所示。笔才能画成。如下图