《一笔画和最短路线问题》由会员分享,可在线阅读,更多相关《一笔画和最短路线问题(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. 旋转法,