数学游戏与数学文化课件 -一笔画.ppt

三、图的应用（1）例1、右图是某展览馆的平面图.每个房间都有一扇门通往馆外，每相邻两个房间之间各有一扇门相通.参观者能不能一次无重复地穿过每一扇门？如不能，关闭哪一扇门后就能无重复地穿过每一扇门了？并问出、入口在哪里？练习下图是蓬莱仙境区某处的地貌图，小河上有15座桥.问能不能设计一条路线，一次不重复地走遍所有的桥？三、图的应用（2）中国邮递员问题一名邮递员每次从邮局出发送信，要走遍他负责投递的范围内的每条街道，完成任务后回到邮局。问他按怎样的路线走，所走的路程最短？——此问题是我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．例2、图1、2表示街道图，图中A是邮局的位置，问邮递员应如何设计他的邮递路线，才能使他所走的路程最短？最优投递路线→重复的路线最短→所添弧线（虚线）的总长度最短为保证总路程最短，连虚线的原则是：（1）连线（虚线）不能有重叠线段；（2）在每个圈上，连线长度之和不能超过圈长的一半。最短的一组连线称为最优解。已知邮递员要投递的街道如图所示，试求最优邮路．练习计算最优邮路方法总结方法1：找出所有奇结点，把奇结点两两配对，在一对奇结点之间连一条虚线当做增添的重复边，奇结点就变成了偶结点，原图变成欧拉图，在此基础上，根据连线原则1、2，不断改进，得到最优。方法2：找出所有奇结点，在图上添线段，使奇点变成偶点。得到所有不同的添法，计算每一种添法对应的总路程，比较得出哪一种添法能使总路程最短，此即最优。上面例题所用的求最优邮路的方法叫“奇偶点图上作业法”．练习某邮递员每天早晨去邮局取邮件，然后走遍他所投递的街道社区，最后回家，问他按何路线投递，可以使他走的路程最短？数学家欧拉简介?莱昂哈德?欧拉（LeonhardEuler公元1707-1783年）瑞士数学家和物理学家。他被一些数学史学者称为历史上最伟大的两位数学家之一（另一位是卡尔?弗里德里克?高斯。）。如果一个图形可以用笔不离纸且每条线都画到并不准重复，则这个图形就叫做一笔画图形.一笔画一、哥尼斯堡七桥问题故事发生在18世纪的东普鲁士哥尼斯堡城.流经那里的一条河中有两个小岛，还有七座桥把这两个小岛与河岸联系起来.那里风景优美，游人众多.在这美丽的地方，人们议论着一个有趣的问题：一个游人怎样才能不重复地一次走遍七座桥，最后又回到出发点呢？问题提出后，很多人对此感兴趣，纷纷进行计算试验，但在相当长的时间里，始终未能解决。而利用普通数学知识，每座桥均走一次，那这七座桥所有的走法一共有5040种，而这么多情况，要一一试验，这将会是很大的工作量。因而形成了著名的“哥尼斯堡七桥问题”。直到1836年，瑞士著名的数学家欧拉才解决了这个问题。当时有人请教了正在俄罗斯的圣彼得堡科学院任职的欧拉，欧拉亲自观察了哥尼斯堡七桥后，认真思考走法。欧拉认为：人们关心的只是一次不重复地走遍这七座桥，而并不关心桥的长短和岛的大小，因此，岛和岸都可以看作一个点，而桥则可以看成是连接这些点的一条线.这样，此问题就转化为一个几何图形能否一笔画出的问题了.什么叫一笔画？是否所有的图都可以一笔画出呢？所谓图的一笔画，指的就是：从图的一点出发，笔不离纸，遍历每条边恰好一次，即每条边都只画一次，不准重复.二、图与一笔画定理能一笔画出的图首先必须是连通图什么样的连通图可以一笔画出？??1736年，欧拉在圣彼得堡科学院作了一次学术报告。在报告中，他给出并证明了哥尼斯堡七桥问题的结论。后来他又给出了鉴别任一图形能否一笔画出的准则，即欧拉定理。由此开创了数学新分支-----图论，他也成为图论的奠基人。他解决问题的思想方法，为后来的数学新分支——拓扑学的建立也奠定了基础。图论以图为研究对象。图论中的图指由点和线段（或弧）组成的图形。作为一个图，其图形还必须满足以下条件：（1）每条边都有两个端点（可以重合）作为结点；（2）各条边之间互不相交。图形中的点叫图的结点，线段（或弧）叫做图的边。一个图完全由它的结点和边的个数以及它们相互连结的情况来确定，而与边的曲直长短无关。在一个图G中，若从顶点vi到顶点vj有路径相连，则称vi和vj是连通的。如果图中任意两点都是连通的（任何两点间都有线连接），那么图被称作连通图。否则称为不连通的。图的连通性是图的基本性质。图中与一个结点相连结的边的条数称为这个结点的度数。度数为偶数的结点叫做偶结点。度数为奇数的结点叫做奇结点。