欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    哥尼斯堡七桥问题和欧拉回路ppt课件.ppt

    • 资源ID:1321921       资源大小:325KB        全文页数:17页
    • 资源格式: PPT        下载积分:16金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要16金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    哥尼斯堡七桥问题和欧拉回路ppt课件.ppt

    知道一笔画问题的提法掌握段道图能否一笔画的判断方法会用添弧的方法求最优解最优投递路线的求法,教学目标,重点和难点,6.4.1 哥尼斯堡七桥问题,哥尼斯堡七桥问题:如何不重复地走完七桥后回到起点?,一笔画问题如何将此图一笔画出?,欧拉的推理,凡是一笔画中出现的交点处,线一出一进总应该通过偶数条(偶点),只有作为起点和终点的两点才有可能通过奇数条(奇点)。,结论:凡是奇点个数多于两个的平面图都不能一笔画出。,七桥问题中有四个奇点,故不能一笔画出,欧拉这种处理问题的方法标志着图论的诞生,6.4.2 欧拉和欧拉回路,欧拉,欧拉(L.Euler,1707.4.15- 1783.9.18)著名的数学家。生于瑞士的巴塞尔,卒于彼得堡。大部分时间在俄国和德国度过。他早年在数学天才贝努里赏识下开始学习数学, 17岁获得硕士学位,毕业后研究数学,是数学史上最高产的作家。在世发表论文700多篇,去世后还留下100多篇待发表。其论著几乎涉及所有数学分支。,欧拉在数学、物理、天文、建筑以至音乐、哲学方面都取得了辉煌的成就。在数学的各个领域,常常见到以欧来命名的公式、定理、和重要常数。课本上常见的如、i、e、sin、cos、tg、x、f(x)等,都是他创立并推广的。欧拉还首先完成了月球绕地球运动的精确理论,创立了分析力学、刚体力学等力学学科,深化了望远镜、显微镜的设计计算理论。关键词:惊人的记忆力 杰出的智慧 顽强的毅力 孜孜不倦的奋斗精神 高尚的科学道德,欧拉回路,经过图中所有边一次,且访问每个顶点至少一次的一个回路,称为欧拉回路。 具有欧拉回路的图称为欧拉图。 注意:通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。 具有欧拉通路而无欧拉回路的图称为半欧拉图。,例1:下列平面图哪些能一笔画出,哪些不可以?哪些有欧拉回路?,6.4.3 中国邮递员问题,中国邮递员问题(Chinese Postman Problem, CPP)是由我国管梅谷教授于1962年首先提出并发表的例如:观察下列段道图 :从邮局出发,走遍邮区的所有街道至少一次再回到邮局,按照什么样的路线投递邮件才能使总的路程最短?,图(1),图(2),问题,投递路线 一笔画 欧拉回路 最理想的投递路线,就是该段道图是一条欧拉回路。图(2)的投递路线如下图(3)。 含有奇点的段道图不能一笔画出,有些道路需要重复走两次的都要添上一条弧。图(1)添弧后如图(4)。,6.4.4邮递员的投递路线的选择,定理1 一个能够不重复的一笔画出的连通图中,所以的点一定都是偶点。定理2 没有奇点的连通图一定能够从任意一点开始不重复的一笔画出。最优投递路线 重复的路最短 添弧的总长度最短添弧最短的条件(1)没有重叠的添弧(2)每一个圈上添弧的总长度不超过圈长的一半最短的一组添弧称为最优解。,例2:找出下列段道图的最优解,3,3,3,3,2,2,2,1,1,3,3,4,先分奇偶点,奇点对对连; 连线不重叠,重叠要改变; 圈上连线长,不得过半圈。,先分奇偶点,奇点对对连; 连线不重叠,重叠要改变; 圈上连线长,不得过半圈。,3,3,3,2,1,先分奇偶点,奇点对对连; 连线不重叠,重叠要改变; 圈上连线长,不得过半圈。,3,3,2,2,3,最优解,先分奇偶点,奇点对对连; 连线不重叠,重叠要改变; 圈上连线长,不得过半圈。,案例:西北大学的洒水车要给主要路面洒水,该如何确定行车路线?,洒水车要给主要路面洒水,也就意味着行车路线必需经过图示所有的路面至少一次。这类似于邮路问题。类似的还有送奶工送奶问题。,

    注意事项

    本文(哥尼斯堡七桥问题和欧拉回路ppt课件.ppt)为本站会员(牧羊曲112)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开