《一笔画和最短路线问题》由会员分享，可在线阅读，更多相关《一笔画和最短路线问题（60页珍藏版）》请在金锄头文库上搜索。
1、,最短路线与一笔画,18世纪风景秀丽的哥尼斯堡（位于立陶宛与波兰之间，现属俄罗斯）中有一条河，河的中间有两个小岛，河的两岸与两岛之间共建有七座桥（如图），城中的居民经常沿河过桥散步，不知从什么时候起，脚下的桥梁触发了人们的灵感，一个有趣的问题在居民中传开了：谁能够一次走遍所有的座桥，而且每座桥都只通过一次？最后是否仍能回到出发点？ 这就是数学史上著名的七桥问题。,七桥问题,A,B,C,D,这个问题看起来是这样的简单，人人都乐意是尝试，但没有找到合适的路线。问题传开后，许多欧洲有学问的人也参与思考，同样是一筹莫展，有人想到了当时正在俄国圣彼得堡科学院任职的天才数学家欧拉，请他帮助解决。欧拉依靠他
2、深厚的数学功底，运用娴熟的变换技巧，经过一年的研究，于1736年递交了一份题为哥尼斯堡七座桥的论文，圆满地解决了这一问题。,欧拉,（Leonhard Euler 公元1707-1783年）,数学名家,欧拉出生在牧师家庭，自幼受到父亲的教育。13岁时入读巴塞尔大学，15岁大学毕业，16岁获得硕士学位。欧拉是18世纪数学界最杰出的人物之一，他不但为数学界作出贡献，更把数学推至几乎整个物理的领域。此外，他是数学史上最多产的数学家，圣彼得堡科学院为了整理他的著作，足足忙碌了四十七年。欧拉著作的惊人多产并不是偶然的，他可以在任何不良的环境中工作，他常常抱着孩子在膝上完成论文，也不顾孩子在旁边喧哗他那顽强
3、的毅力和孜孜不倦的治学精神，使他在双目失明以后， 也没有停止对数学的研究，在失明后的17年间，他还口述了几本书和400篇左右的论文19世纪伟大数学家高斯（Gauss，1777-1855年）曾说：“研究欧拉的著作永远是了解数学的最好方法“,欧拉解决这个问题的方法非常巧妙。他认为：人们关心的只是一次不重复地走遍这七座桥，而并不关心桥的长短和岛的大小，因此，岛和岸都可以看作一个点，,建立数学模型,A,B,而桥则可以看成是连接这些点的一条线。这样，一个实际问题就转化为一个几何图形（如下图）能否一笔画出的问题了。,一笔画问题,什么叫一笔画？什么样的图可以一笔画出？,所谓图的一笔画，指的是：从图的一点出发
4、，笔不离纸，每条边都只画一次，不准重复。,偶点:与偶数条边相连的点叫偶点。,奇点:与奇数条边相连的点叫奇点。,知识积累,能够一笔画的图形必须是连通图形。,图形,奇点个数,偶点个数,能否一笔画,0,4,能,能,0,7,能,不能,4,0,5,1,操作体验,归纳与猜想,1、奇点个数为0的连通图是一笔画图形。,可任选一点为起点，起点和终点为同一点。,观察操作,实践出真知,（）,（）,（）,下面哪些图形可以一笔画出?,（7）,图形,奇点个数,偶点个数,能否一笔画,能,不能,能,能,2,2,2,4,3,2,5,操作体验,1,归纳与猜想,2、奇点数为，偶点数为任意的连通 图是一笔画图形。,可选其中一个奇点做
5、起点，而终点一定是另一个奇点，即一笔画后不可以回到出发点。,实践运用,现在七桥问题可以解决了吗？,A,B,四个点都是奇点,观察下面的图形，说明哪些图可以一笔画完，哪些不能，为什么？对于可以一笔画的图形，指明画法.,练习1,练习题答案,（1）图：不能一笔画，因为此图不是连通图。（2）图：不能一笔画，因图中有四个奇点：A、B、C、D。（3）图：可以一笔画，因为没有奇点；画法可以是：ABCDEFGHBICEJFHA。 （4）图：不能一笔画出，因为图中有八个奇点。,独立完成练习1、2、3、4,一笔画原理：一个图如果可以一笔画成，那么这个图中奇数顶点的个数不是0就是2。,在七桥问题中，如果允许你再架一座
6、桥，能否不重复地一次走遍这八座桥？这座桥应该架在哪里？请你试一试！,拓展创新,见12,用什么方法变“不能一笔画”改成“一笔画”？,把“奇点”改成“偶点”，剩2个奇点或0个奇点。,,甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从A点出发，乙从B点出发，最后都回到邮局（C）。如果要选择最短的线路，谁先回到邮局？,1.图中有两个奇点：A和C.2.以A、C两点分别作为起点和 终点而一笔画成3. 甲可以从A出发， 不重复地走遍所有的街道， 最后到达C,生活中的“一笔画”问题,需要顺便提到的是：既然可由一笔画画成的脉络，其奇点个数应不多于两个，那么，两笔划或多笔划能够画成的脉络，其奇点个数应有
7、怎样的限制呢？我想，聪明的读者完全能自行回答这个问题。,生活中的“一笔画”问题,生活中的“一笔画”问题,例3,练习9,一般地，我们有： 含有2n(n0)个奇点的脉络，需要n笔划画成。,生活中的“一笔画”问题,练习10、11,练习17、18,橡皮膜上的几何学,在哥尼斯堡七桥问题中，读者已经看到了一种只研究图形各部分位置的相对次序，而不考虑它们尺寸大小的新几何学。莱布尼兹(Leibniz，16461716)和欧拉为这种“位置几何学”的发展奠定了基础。如今这一新的几何学，已经发展成一门重要的数学分支拓扑学,拓扑学研究的课题是极为有趣的。 在拓扑学中人们感兴趣的只是图形的位置而不是它的大小。有人把拓扑
8、学说成是橡皮膜上的几何学是很恰当的。因为橡皮膜上的图形，随着橡皮膜的拉动，其长度、曲直、面积等等都将发生变化。此时谈论“有多长？”、“有多大？”之类的问题，是毫无意义的!,不过，在橡皮膜几何里也有一些图形的性质保持不变。例如点变化后仍然是点；线变化后依旧为线；相交的图形绝不因橡皮的拉伸和弯曲而变得不相交! 拓扑学正是研究诸如此类，使图形在橡皮膜上保持不变性质的几何学,请大家思考：“串”、“田”两字，在橡皮膜上可变为什么图形,拓扑学是在19世纪末兴起并在20世纪蓬勃发展的数学分支，与近世代数、近代分析共同成为数学的三大支柱。拓扑学已在物理、化学、生物一些工程技术中得到越来越广泛的应用。拓扑学主要
9、研究几何图形在一对一的双方连续变换下不同的性质，这种性质称为“拓扑性质”。以下我们将复杂的拓扑学知识应用到简单的游戏中，使观众在游戏中了解拓扑学的特性，并学习到相关知识。,“内部”与“外部”,一条头尾相连且自身不相交的封闭曲线，把橡皮膜分成两个部分。如果我们把其中有限的部分称为闭曲线的“内部”，那么另一部分便是闭曲线的“外部”。从闭曲线的内部走到闭曲线的外部，不可能不通过该闭曲线。因此，无论你怎样拉扯橡皮膜，只要不切割、不撕裂、不折叠、不穿孔，那么闭曲线的内部和外部总是保持不变的!,“内部”与“外部”是拓扑学中很重要的一组概念 以下有趣的故事，将增加你对这两个概念的理解：,传说古波斯穆罕默德的
10、继承人哈里发，有一位才貌双全的女儿。姑娘的智慧和美貌，使许多聪明英俊的小伙子为之倾倒，致使求婚者的车马络绎不绝。哈里发决定从中挑选一位才智超群的青年为婿。于是便出了一道题目，声明说：谁能解出这道题，便将女儿嫁给谁！,哈里发的题目是这样的：请用线把下图中写有相同数字的小圆圈连接起来，但所连的线不许相交，也不许与图中的线相交,上述问题的解决，似乎不费吹灰之力。但实际上求婚者们全都乘兴而来，败兴而去！ 据说后来哈里发终于醒悟，发现自己所提的问题是不可能实现的，因而后来又改换了题目。也有的说，哈里发固执已见，美丽的公主因此终生未嫁。事情究竟如何，现在自然无从查考。,哈里发的失算，却是可以用拓扑学的知识
11、加以证明的。其所需之概念，只有“内部”与“外部”两个。事实上，我们很容易用线把一、一连起来。明眼的读者可能已经发现：我们得到了一条简单的闭曲线，这条曲线把整个平面分为内部(阴影部分)和外部两个区域。其中一个在内部区域，而另一个却在外部区域，要想从闭曲线内部的，画一条弧线与外部的相连，而与已画的闭曲线不相交，这是不可能的！这正是哈里发悲剧之所在。,点A,是在内部还是外部,不分内外的“克莱因瓶”,例5、假如直线AB是一条公路，在路两侧有甲、乙两个村子，现在要在公路上修一个公共汽车站，让这两个村的人到车站的路线之和最短。问车站应修建在什么地方？,三角形的两边之和大于第三边,连接两点的所有线中，直线段
12、最短,公理是从实践中总结出来的任何人都承认的原始道理。当然，有同学会想：“你那个公理我不承认行不行呢?”那可不行，比如图（1）中，有一只鸡在B点觅食，你在A点处放一些米，那么鸡一定会沿直线AB跑过来吃食，决没有一只蠢鸡沿BCA或沿BDA的线路跑过来。这表明：公理不但人类公认，连动物界也都遵循它。,将军饮马问题:,古希腊一位将军要从A地出发到河边L去饮马，然后再回到驻地B. 显然有许多走法 问怎样选择饮马地点， 才能使路程最短?,L,我们看看海伦是怎么解决的。海伦发现这是一个求折线和最短的问题。已知两点间直线段最短。那么，显然要把折线变成直线再解。如果直接连AB，与l不会相交。怎么办呢？,将军饮
13、马问题,原来海伦解决本问题时，是利用作对称点把折线问题转化成直线问题求解的。后来这一方法已形成了思想，它在解决许多问题中都在起作用。现在人们把凡是用对称点来实现解题的思想方法叫对称原理。（拉直方法）,独立完成5、6,第5题是把对称原理连续使用了两次,较复杂的最短路线问题,独立完成14、13,如图, A,B两地在一条河的两岸, 现要在河上造一座桥MN, 桥造在何处才能使从A到B的路径AMNB最短?(假定河的两岸是平行的直线,桥要与河垂直),造桥选址问题:,平行且相等的原理,利用勾股定理 求解几何体的最短路线长,例1、如图，是一个三级台阶，它的每一级的长、宽和高分别等于5cm，3cm和1cm，A和
14、B是这个台阶的两个相对的端点，A点上有一只蚂蚁，想到B点去吃可口的食物.请你想一想，这只蚂蚁从A点出发，沿着台阶面爬到B点，最短线路是多少？,B,A,5,3,1,5,12,一、台阶中的最值问题, AB2=AC2+BC2=169, AB=13.,三、正方体中的最值问题,例3、如图，边长为1的正方体中，一只蚂蚁从顶点A出发沿着正方体的外表面爬到顶点B的最短距离是（ ）.（A）3 （B） 5 （C）2 （D）1,分析： 由于蚂蚁是沿正方体的外表面爬行的，故需把正方体展开成平面图形（如图）.,C,小 结：把几何体适当展开成平面图形，再利用“两点之间线段最短”，或点到直线“垂线段最短”等性质来解决问题。,例4、如图，一只蚂蚁从实心长方体的顶点A出发，沿长方体的表面爬到对角顶点C1处（三条棱长如图所示），问怎样走路线最短？最短路线长为多少？,分析: 根据题意分析蚂蚁爬行的路线有三种情况(如图 ),由勾股定理可求得图1中AC1爬行的路线最短.,四、长方体中的最值问题,解决“最短”问题的总思路：,化曲为平，化折为直,解决 “最短” 问题的方法：,1. 轴对称法 2. 平行四边形法 3. 旋转法,
