ImageVerifierCode 换一换
格式:PPT , 页数:20 ,大小:1.09MB ,
文档编号:4968143      下载积分:19 文币
快捷下载
登录下载
邮箱/手机:
温馨提示:
系统将以此处填写的邮箱或者手机号生成账号和密码,方便再次下载。 如填写123,账号和密码都是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

优惠套餐
 

温馨提示:若手机下载失败,请复制以下地址【https://www.163wenku.com/d-4968143.html】到电脑浏览器->登陆(账号密码均为手机号或邮箱;不要扫码登陆)->重新下载(不再收费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  
下载须知

1: 试题类文档的标题没说有答案,则无答案;主观题也可能无答案。PPT的音视频可能无法播放。 请谨慎下单,一旦售出,概不退换。
2: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
3: 本文为用户(晟晟文业)主动上传,所有收益归该用户。163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

1,本文(哥尼斯堡七桥问题学习资料课件.ppt)为本站会员(晟晟文业)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!

哥尼斯堡七桥问题学习资料课件.ppt

1、哥尼斯堡七桥问题知道一笔画问题的提法掌握段道图能否一笔画的判断方法会用添弧的方法求最优解最优投递路线的求法教学目标教学目标重点和难点重点和难点5欧拉的解法 哥尼斯堡七桥问题引起了大数学家欧拉的兴趣。他知道,如果沿着所有可能的路线都走一次的话,一共要走5040次。就算是一天走一次,也需要13年多的时间。实际上,欧拉只用了几天的时间就解决了七桥问题。6 欧拉的想法是:两岸的陆地与河中的小岛,都是桥梁的连接点,它们的大小、形状均与问题本身无关。因此,不妨把它们看作是4个点。7座桥是7条必须经过的路线,它们的长短、曲直,也与问题本身无关。因此,不妨任意画7条线来表示它们。就这样,欧拉将七桥问题抽象成了

2、一个“一笔画”问题,从而否定了问题的答案。7七七 桥桥 问问 题题 哥尼斯堡七桥哥尼斯堡七桥问题:如何不重复地走完七桥后回到起点?一笔画问题一笔画问题如何将此图一笔画出?欧拉的推理欧拉的推理 凡是一笔画中出现的交点处,线一出一进总凡是一笔画中出现的交点处,线一出一进总应该通过偶数条(偶点),只有作为起点和终点应该通过偶数条(偶点),只有作为起点和终点的两点才有可能通过奇数条(奇点)。的两点才有可能通过奇数条(奇点)。欧拉这种处理问题的方法标志着图论图论的诞生 欧拉(L.Euler,1707.4.15-1783.9.18)著名的数学家。生于瑞士的巴塞尔,卒于彼得堡。大部分时间在俄国和德国度过。他

3、早年在数学天才贝努里赏识下开始学习数学,17岁获得硕士学位,毕业后研究数学,是数学史上最高产的作家。在世发表论文700多篇,去世后还留下100多篇待发表。其论著几乎涉及所有数学分支。欧拉在数学、物理、天文、建筑以至音乐、哲学方面都取得了辉煌的成就。在数学的各个领域,常常见到以欧来命名的公式、定理、和重要常数。课本上常见的如、i、e、sin、cos、tg、x、f(x)等,都是他创立并推广的。欧拉还首先完成了月球绕地球运动的精确理论,创立了分析力学、刚体力学等力学学科,深化了望远镜、显微镜的设计计算理论。观察下列图形,完成统计表观察下列图形,完成统计表 图7图5图1图8图6图4图3图2可以一笔画的

4、图形 不能一笔画的图形 图形序号 奇点个数偶点个数图形序号 奇点个数偶点个数不连通的图形不能一笔画不连通的图形不能一笔画 连通的图连通的图形形有可能有可能一笔画一笔画 全都是偶点的连全都是偶点的连通图可以一笔画通图可以一笔画 奇点个数超过两个的连通图奇点个数超过两个的连通图形不能一笔画形不能一笔画 画时以任一点为起点,最后仍回画时以任一点为起点,最后仍回到该点到该点 画时以一个奇点为起点,另一个画时以一个奇点为起点,另一个奇点为终点奇点为终点有两个奇点的连有两个奇点的连通图可以一笔画通图可以一笔画 欧拉回路 经过图中经过图中所有边所有边一次,且访问每个顶点一次,且访问每个顶点至少至少一一次的一

5、个次的一个回路回路,称为欧拉回路。,称为欧拉回路。具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图。注意:通过图中所有边一次且仅一次行遍所有通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。顶点的通路称为欧拉通路。判断下列图形能否一笔画判断下列图形能否一笔画图5图4图3图2图6图1下图是一个公园的平面图,要使游人走遍每一条路不重复,出口和入口应设在哪儿?中国邮递员问题中国邮递员问题 中国邮递员问题中国邮递员问题(Chinese Postman Problem,Chinese Postman Problem,CPPCPP)是由我国管梅谷教授于是由我国管梅谷教授于19621962年首先

6、提出并年首先提出并发表的发表的 例如:观察下列段道图例如:观察下列段道图 从邮局出发,走遍邮区的所有街道至少从邮局出发,走遍邮区的所有街道至少一次再回到邮局,按照什么样的路线投一次再回到邮局,按照什么样的路线投递邮件才能使总的路程最短?递邮件才能使总的路程最短?图(1)图(2)投递路线 一笔画 欧拉回路 最理想的投递路线,就是该段道图是一条欧拉回路。图最理想的投递路线,就是该段道图是一条欧拉回路。图(2 2)的投递路线如下图()的投递路线如下图(3 3)。)。含有奇点的段道图不能一笔画出,有些道路需要重复走含有奇点的段道图不能一笔画出,有些道路需要重复走两次的都要添上一条弧。图(两次的都要添上

7、一条弧。图(1 1)添弧后如图()添弧后如图(4 4)。)。图(3)图(4)定理定理1 1 一个能够不重复的一笔画出的连通图中一个能够不重复的一笔画出的连通图中,所以的点一定都是偶点。,所以的点一定都是偶点。定理定理2 2 没有奇点的连通图一定能够从任意一点没有奇点的连通图一定能够从任意一点开始不重复的一笔画出。开始不重复的一笔画出。最优投递路线最优投递路线 重复的路最短重复的路最短 添弧的总长添弧的总长度最短度最短 添弧最短的条件(1)没有重叠的添弧(2)每一个圈上添弧的总长度不超过圈长的一半 最短的一组添弧称为最优解。案例:西北大学的洒水车要给主要路案例:西北大学的洒水车要给主要路面洒水,该如何确定行车路线?面洒水,该如何确定行车路线?洒水车要给主要路面洒水,也就意味着行车路线必需经过图示所有的路面至少一次。这类似于邮路问题。类似的还有送奶工送奶问题。

侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|