格尼斯堡七桥问题课件

格尼斯堡七桥问题课件121.七桥漫步七桥漫步 格尼斯堡城是由条顿骑士团在格尼斯堡城是由条顿骑士团在1308年建立，曾作为东普鲁士年建立，曾作为东普鲁士的首府。第二次世界大战后，成为前苏联最大的海军基地。现的首府。第二次世界大战后，成为前苏联最大的海军基地。现在的格尼斯堡位于立陶宛和波兰之间。在的格尼斯堡位于立陶宛和波兰之间。在第二次世界大战时，法军经这里入侵波兰。后来苏军也从这在第二次世界大战时，法军经这里入侵波兰。后来苏军也从这里打进德国，所以格尼斯堡是一座名城。同时这里也诞生过许里打进德国，所以格尼斯堡是一座名城。同时这里也诞生过许多伟大人物，其中包括多伟大人物，其中包括18世纪著名的唯心主义哲学家康德和世纪著名的唯心主义哲学家康德和19世纪的大数学家希尔伯特。世纪的大数学家希尔伯特。但是，最早给这座城市带来声誉的横跨布列格尔河，把格尼但是，最早给这座城市带来声誉的横跨布列格尔河，把格尼斯堡连成一体的七座桥梁。斯堡连成一体的七座桥梁。21.七桥漫步 格尼斯堡城是由条顿骑士团在13023 这一别致的桥群，引来了众多的游人，同时还引发了数学史上这一别致的桥群，引来了众多的游人，同时还引发了数学史上一项重要的研究。一项重要的研究。3 这一别致的桥群，引来了众多的游人，同时还引发34 一天又一天，这七座桥上走过了无数的行人，脚下的七桥触发一天又一天，这七座桥上走过了无数的行人，脚下的七桥触发了人们的灵感，一个有趣的问题在民间传开了人们的灵感，一个有趣的问题在民间传开“能否在一次散步中能否在一次散步中每座桥都走一次，而且只能走一次，最后又回到原来的出发点每座桥都走一次，而且只能走一次，最后又回到原来的出发点？”这个问题看似简单，人人都乐意去测试一下自己的智力，可是这个问题看似简单，人人都乐意去测试一下自己的智力，可是把全城人的智力加在一起，也没有找到一条合适的路线。这个把全城人的智力加在一起，也没有找到一条合适的路线。这个问题传开以后，许多欧洲有学问的人也参与思考，同样是一筹问题传开以后，许多欧洲有学问的人也参与思考，同样是一筹莫展。就这样，格尼斯堡这个莫展。就这样，格尼斯堡这个“七桥问题七桥问题”给人们提供了丰富的给人们提供了丰富的乐趣和数学兴味，因而使得这座波罗的海的海滨古城闻名遐迩。乐趣和数学兴味，因而使得这座波罗的海的海滨古城闻名遐迩。4 一天又一天，这七座桥上走过了无数的行人，脚下452.欧拉与格尼斯堡七桥问题欧拉与格尼斯堡七桥问题 1735年有几名大学生写信给当时正在俄国彼得堡科学院任职年有几名大学生写信给当时正在俄国彼得堡科学院任职的天才数学家欧拉，请他帮助解决。欧拉并未轻视生活中的小的天才数学家欧拉，请他帮助解决。欧拉并未轻视生活中的小问题，他似乎看到了其中隐藏某种新的数学方法。问题，他似乎看到了其中隐藏某种新的数学方法。事实上，要走遍七座桥的所有走法有事实上，要走遍七座桥的所有走法有 种，要想一种，要想一一试验是不可能的，只能另找一种新方法。欧拉依靠他深厚的一试验是不可能的，只能另找一种新方法。欧拉依靠他深厚的数学功底，运用娴熟的变换技巧，经过一年的研究，于数学功底，运用娴熟的变换技巧，经过一年的研究，于1936年，年，29岁的欧拉向彼得堡科学院提交了一份为格尼斯堡七桥的岁的欧拉向彼得堡科学院提交了一份为格尼斯堡七桥的论文，圆满的解决了这一问题。欧拉不仅解决了七桥问题，而论文，圆满的解决了这一问题。欧拉不仅解决了七桥问题，而且他提出且他提出的的思想导致了一门新的数学分支思想导致了一门新的数学分支“图论图论”的诞生。的诞生。52.欧拉与格尼斯堡七桥问题 1735年有几名大56 欧拉是如何解决七桥问题的？又是如何证明要想一次走过七座欧拉是如何解决七桥问题的？又是如何证明要想一次走过七座桥是不可能的呢？欧拉的方法十分巧妙：桥是不可能的呢？欧拉的方法十分巧妙：（1）不考虑）不考虑4个地区的大小、形状，不妨将它们看成是链接桥个地区的大小、形状，不妨将它们看成是链接桥梁的梁的4个点；个点；（2）不考虑桥梁的曲直、长短，不妨将它们看成连接）不考虑桥梁的曲直、长短，不妨将它们看成连接4个点的个点的7条线。条线。于是一座仪态万千的格于是一座仪态万千的格尼斯堡古城在欧拉笔下尼斯堡古城在欧拉笔下就变成了一个结构简单就变成了一个结构简单是几何图形。是几何图形。6 欧拉是如何解决七桥问题的？又是如何证明要想一67 于是七桥问题就变成了用笔不重复的（笔不离开纸面）画出这于是七桥问题就变成了用笔不重复的（笔不离开纸面）画出这个几何图形的问题，即个几何图形的问题，即“一笔画一笔画”问题。如果可以画出来，则必问题。如果可以画出来，则必有一个起点和一个终点，如果这两点不重合，则与起点或终点有一个起点和一个终点，如果这两点不重合，则与起点或终点相交的线必为奇数条（称为奇点），如果起点与终点重合，则相交的线必为奇数条（称为奇点），如果起点与终点重合，则与之相交的线必为偶数条（称为偶点），而除了起点与终点外，与之相交的线必为偶数条（称为偶点），而除了起点与终点外，其他点也必为偶点。据以上分析，如果一个图形可以一笔画出其他点也必为偶点。据以上分析，如果一个图形可以一笔画出来，则必须满足两个条件：来，则必须满足两个条件：（1）图形必须是连通的图形必须是连通的，即任一点通过一些线一定能达到其，即任一点通过一些线一定能达到其他任意点。（他任意点。（2）图中的奇点数只能是图中的奇点数只能是0或或2.回头来看七桥问题，回头来看七桥问题，4个点全为奇点，故七桥问题无解。个点全为奇点，故七桥问题无解。欧拉当时发表这一结果时，震惊了当时的数学界。欧拉当时发表这一结果时，震惊了当时的数学界。7 于是七桥问题就变成了用笔不重复的（笔不离开纸78 一笔画1、一笔画游戏：下图是一个奥运五环标志，你能不能一笔画出来？动手试一试。（要求：笔中途不能离开纸，每条线只能画一次不能重复。）2、你能试着用一笔把下列图形画出来吗？如果可以，说说你是怎样画的？3、下图中，说一说哪些点是偶点，哪些点是奇点，再画一画看看它们能不能一笔画出？8 894、下列图形能一笔画成吗？为什么？并试着画一画。5、下面的图形都不能一笔画成，你能否在图中填上一条线段，使它能一笔画成。6、下图是商场的平面图，小明的妈妈想不重复的走遍商场的每条通道，节省逛街的时间，她能做到吗？如果不能，请说明理由；如果能，请你帮她设计一条行走路线（可以从A、B、C、D、E、F、H、I任意门进出商场）。94、下列图形能一笔画成吗？为什么？并试着画一画。5、下面的9107、下图中的每一个图形，最少需要几笔画出？107、下图中的每一个图形，最少需要几笔画出？10113.引申与推广引申与推广 欧拉解决七桥问题的方法并不深奥，但他的新颖之处不仅在于欧拉解决七桥问题的方法并不深奥，但他的新颖之处不仅在于另辟蹊径的解题思路，更在于另辟蹊径的解题思路，更在于“一笔画一笔画”问题虽然是一个几何问问题虽然是一个几何问题，可是这种几何问题却是欧几里得几何里没有研究过的。题，可是这种几何问题却是欧几里得几何里没有研究过的。在在“一笔画一笔画”问题里，长度、角度、面积、体积都没有了，四问题里，长度、角度、面积、体积都没有了，四大块陆地变成了四个点；连线的长短曲直、交点的方位都无关大块陆地变成了四个点；连线的长短曲直、交点的方位都无关紧要，要紧的只是点线之间的相关位置或相互连接的情况，如紧要，要紧的只是点线之间的相关位置或相互连接的情况，如下两图都没有改变七桥问题下两图都没有改变七桥问题“一笔画一笔画”的性质。的性质。113.引申与推广 欧拉解决七桥问题的方法并不深1112 后来布勒格尔河上又架起第八座桥来后来布勒格尔河上又架起第八座桥来铁路桥，这又使人们铁路桥，这又使人们想起了那有趣的问题。虽然一次不重复走遍七座桥不可能，那想起了那有趣的问题。虽然一次不重复走遍七座桥不可能，那八座桥呢？从图中可以已看出，八座桥呢？从图中可以已看出，“奇点奇点”只有两个（只有两个（D、C），所），所以可以一次不重复走遍八座桥。以可以一次不重复走遍八座桥。12 后来布勒格尔河上又架起第八座桥来铁路桥1213下图是国际奥林匹克运动会的会标，也可以下图是国际奥林匹克运动会的会标，也可以“一笔画一笔画”。其中一条线路可以是其中一条线路可以是:A-B-A-BC-D-C-E-F-E-G-H-G-H-F-D-A13下图是国际奥林匹克运动会的会标，也可以“一笔画”。其中一13144.新学科的形成新学科的形成 欧拉对七桥问题的解决之所以著名，不仅是因为它欧拉对七桥问题的解决之所以著名，不仅是因为它 的趣味的趣味性和欧拉解题思路的巧妙，更重要的是这个问题的解决开创了性和欧拉解题思路的巧妙，更重要的是这个问题的解决开创了一个新的数学分支一个新的数学分支图论。图论。图论就是运用直观的图形和数学方法来研究组和关系的一门图论就是运用直观的图形和数学方法来研究组和关系的一门新兴学科，由于发展迅速，现已成为一个独立的数学分支。它新兴学科，由于发展迅速，现已成为一个独立的数学分支。它把被研究系统中的各个元素作为点，元素之间的关系作为线，把被研究系统中的各个元素作为点，元素之间的关系作为线，然后画成图，通过对图形的研究，找出解决问题的办法。然后画成图，通过对图形的研究，找出解决问题的办法。144.新学科的形成 欧拉对七桥问题的解1415 图论为研究任何一类离散事物的关系结构提供了一种本质的图论为研究任何一类离散事物的关系结构提供了一种本质的框架，在经济、心理、社会、遗传、运筹、计算机、网络、信框架，在经济、心理、社会、遗传、运筹、计算机、网络、信息论、控制论、逻辑学、语言学、物理学、化学、微电子技术、息论、控制论、逻辑学、语言学、物理学、化学、微电子技术、通讯科学、系统科学等方面都有广泛的应用。通讯科学、系统科学等方面都有广泛的应用。值得一提的是，对七桥问题的研究后来演变为对多面体的研值得一提的是，对七桥问题的研究后来演变为对多面体的研究，得到了著名的欧拉公式：究，得到了著名的欧拉公式：V+F=E+2，其中，其中V、E、F分布是分布是多面体的定点数、棱数和面数。这就是高中关于凸多面体的欧多面体的定点数、棱数和面数。这就是高中关于凸多面体的欧拉定理。这个定理是拓扑学的第一个定理，其使我们看到了几拉定理。这个定理是拓扑学的第一个定理，其使我们看到了几何问题更深刻的内涵性质。拓扑学已成为当前最为丰富多彩的何问题更深刻的内涵性质。拓扑学已成为当前最为丰富多彩的一个数学分支。一个数学分支。15 图论为研究任何一类离散事物的关系结15165.最短邮路问题最短邮路问题 最短邮路问题最短邮路问题邮递员每天要邮递员每天要走遍自己投递范围的大街小巷，怎走遍自己投递范围的大街小巷，怎样选择路线才能使邮路最短？我们样选择路线才能使邮路最短？我们把投递单位看做点，路线化作线，把投递单位看做点，路线化作线，就可以用图论来解决了。就可以用图论来解决了。右图为投递街道图，如果能一笔右图为投递街道图，如果能一笔画，就能找到最短投递路线；如果画，就能找到最短投递路线；如果一笔画不出来，问题就变成在不得一笔画不出来，问题就变成在不得不重复的情况下，寻找最短路线，不重复的情况下，寻找最短路线，这比一笔画问题更深入了。这比一笔画问题更深入了。165.最短邮路问题 最短邮路问题邮递员每1617如果一张图中奇点数大于如果一张图中奇点数大于2，并且是，并且是2 的的n倍，则该图至少需要倍，则该图至少需要n笔才能画成。如下图所示。笔才能画成。如下图所示。17如果一张图中奇点数大于2，并且是2 的n倍，则该图至少需1718最短邮路问题是最短邮路问题是1960年由我国山东师范大学管梅谷教授提出并年由我国山东师范大学管梅谷教授提出并解决的，因此国际上称为解决的，因此国际上称为“中国邮路问题中国邮路问题”。回头来看邮路图，其中有回头来看邮路图，其中有6个奇点，故至少要个奇点，故至少要3笔才能画成，笔才能画成，重复部分应该选择最短的邮路区间，故以下三种方案中，第重复部分应该选择最短的邮路区间，故以下三种方案中，第三个方案最好。三个方案最好。18最短邮路问题是1960年由我国山东师范大学管梅谷教授提出18