欢迎来到163文库! | 帮助中心 精品课件PPT、教案、教学设计、试题试卷、教学素材分享与下载!
163文库
全部分类
  • 办公、行业>
  • 幼教>
  • 小学>
  • 初中>
  • 高中>
  • 中职>
  • 大学>
  • 各类题库>
  • ImageVerifierCode 换一换
    首页 163文库 > 资源分类 > DOCX文档下载
    分享到微信 分享到微博 分享到QQ空间

    《应用数学基础》教案4.2 欧拉图及其应用.docx

    • 文档编号:4601040       资源大小:189.29KB        全文页数:5页
    • 资源格式: DOCX        下载积分:15文币     交易提醒:下载本文档,15文币将自动转入上传用户(momomo)的账号。
    微信登录下载
    快捷注册下载 游客一键下载
    账号登录下载
    二维码
    微信扫一扫登录
    下载资源需要15文币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    优惠套餐(点此详情)
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、试题类文档,标题没说有答案的,则无答案。带答案试题资料的主观题可能无答案。PPT文档的音视频可能无法播放。请谨慎下单,否则不予退换。
    3、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者搜狗浏览器、谷歌浏览器下载即可。。

    《应用数学基础》教案4.2 欧拉图及其应用.docx

    1、长沙民政职业技术学院教案课程名称数学应用基础课题欧拉图及其应用授课课时2课型新授课教案编号 4-2 教学目标(知识、技能、素质):1、 知识目标:掌握欧拉路、欧拉回路及欧拉图、半欧拉图的概念和判定方法;掌握欧拉图的应用;Fleury算法;2、技能目标:分析解决问题的能力和严谨的逻辑思维能力3、素质目标:培养学生理性的思维方式和数学应用意识教学重点: 欧拉路、欧拉回路及欧拉图的判定;欧拉图的应用;利用 Fleury算法寻找欧拉回路;教学难点:欧拉图的判定及其应用主要教学方法:启发引导式、讲授法教学环节与内容一、问题引入引例1 (设计区间公交车路线)某运输管理部门在设计一个新的区间公交系统,来运送

    2、城市商业区的顾客,具体地图如图4-10所示,为了提高公交车的运行效率,他们希望能够设计一条恰好通过商业区每条道路一次的运行路线,并且最终回到初始位置。图4-10 商业区地图为此,首先将每一个道路交叉口用一个顶点表示,连接两个交叉口的道路用一条边表示,这样我们就可以将地图模拟成图4-11所示。图4-11 商业区模拟图从而将问题转化为在图4-11中找到一条从顶点A出发,走遍图中每条边一次且仅一次的回路。二、新课讲授定义1 经过图中所有边一次且仅一次的路称为欧拉路。起点和终点是同一顶点的欧拉路称为欧拉回路。包含欧拉回路的图称为欧拉图,包含欧拉路但不包含欧拉回路的图称为半欧拉图。例如,在图4-12中,

    3、路径ABCDEFBEA包含了图中的所有边,并且路径中没有重复的边,所以路径 ABCDEFBEA是一条长度为8的欧拉路,它也是一条欧拉回路,因为它的起点和终点都在同一个顶点。图4-12注意:欧拉图肯定包含欧拉路和欧拉回路,半欧拉图只包含欧拉路而不包含有欧拉回路。定义2 一个顶点所关联的边(即以该顶点为端点的边)的条数,称为该顶点的度数。例如,在图4-13中,顶点A、B、D、E、F的度数均为2,因为与这些顶点关联的边都是两条。类似地,因为与顶点C、G相连的边为3条,所以顶点C、G的度数为3。图4-13定义3 度数为奇数的顶点称为奇顶点,度数为偶数的顶点为偶顶点。如,在图4-13中,顶点A、B、D、

    4、E、F是偶顶点,顶点C、G是奇顶点。案例1 判断图4-13能否在笔不离纸的情况下一笔画出来。解 在画图的过程中,采取走过一条边就擦掉这条边的方式,如果能把所有边都擦掉,那么这个图肯定就能够一笔画出来。也就是说,图中所有顶点的度数都要变为0,因为如果还存在度数不为0的顶点,那么肯定还有边没被擦掉。假设从顶点C出发,沿着边CD走到顶点D,并把边CD擦掉,如图4-14(a),顶点C和顶点D的度数都减少了1。接着,从顶点D出发到达顶点A,顶点D的度数又减少了1,故顶点D的度数变为0,如图4-14(b),我们已走的路是CDA。图4-14事实上,在一笔画过程中,每经过一个顶点,该顶点的度数都要减2,因此,

    5、不管经过顶点几次,经过的顶点的奇偶性不变,即偶顶点还是偶顶点,奇顶点还是奇顶点。一个图能否被一笔画出来,只需要看各顶点是否都是偶顶点(出发点和结束点除外)。在本例中,我们继续从A出发,经过B点,到达顶点C,此时所走的路是CDABC。然后,从C点出发依次经过顶点G、F、E,再回到G点,所走的路为CDABCGFEG。至此,图中所有边都被擦掉了,图4-13能够一笔画出来。欧拉图判定定理 一个图G是欧拉图的充分必要条件是图G是连通图且无奇顶点。半欧拉图判断定理 一个图G是半欧拉图的充分必要条件是图G是连通图且刚好有两个奇顶点。半欧拉图对应的欧拉路必定以两个奇顶点为端点。案例2 (蚂蚁比赛问题)甲、乙两

    6、只蚂蚁分别位于顶点A、B处。假设图中边的长度是相等的,甲、乙进行比赛,从它们所在顶点出发,走遍图中的所有边,最后到达顶点C。如果它们的速度相同,请问谁先到达目的地?图4-16 蚂蚁比赛图解 图4-16中仅有两个奇顶点A、C,根据半欧拉图判定定理,存在从A到C的欧拉路,蚂蚁甲走到C只需要走一条欧拉路,边数为9条。而蚂蚁乙要想走完所有的边到达C,至少要先走一条边到达A,再走一条欧拉路,故蚂蚁乙至少要走10条边才能到达C点,因此,在速度相同的情况下,蚂蚁甲先到达目的地。现在我们已经能确定图4-11是一个欧拉图,因此,公交车路线设计问题中管理部门希望的设计路线一定是存在的,剩下的事情就只需要在图中找到

    7、这样一条路线即可。我们如何在一个比较复杂的图中找到一条欧拉回路呢?Fleury(弗罗莱)给出了一个系统寻找欧拉回路的算法。Fleury算法 在一个欧拉图中,我们可以按照下面的步骤寻找欧拉回路:从图中任意一个顶点开始,运用下面的规则连续地通过各边:(1)经过一条边后,把它擦掉。如果一个顶点的所有边都被擦掉,那么也将这个顶点擦掉。(2)当且仅当没有其他的选择时经过一座桥。例10 利用Fleury算法在图4-11中寻找到一条欧拉回路。解 第一步:从顶点A开始,走过边AH,并把它擦掉。如图4-17所示。第二步:经过边HG和GF,到达F点。擦掉边HG和GF,而且所有连接顶点G的边都被擦掉了,所以把顶点G

    8、也擦掉。目前的路是AHGF。如图4-18所示。第三步:经过边FE、ED、DC,并擦去它们和顶点E, 此时到达顶点C的路是AHGFEDC,如图4-19所示。第四步:现在边CB是一座桥,但是除了它没有别的选择,沿着边CB连续通过BD、DI、IF、FH、HI、IB、BA回到顶点A,最终的回路是AHGFEDCBDIFHIBA。如果运输管理部门沿着这条回路来设计公交车的运行路线,就可以每条路只走一次来提高运行效率。图4-17 图4-18 图4-19例11 一个邮递员投递信件要走的街道如图4-20所示,图中的数字表示各条街道的千米数,他从邮局A出发,要走遍各街道,最后回到邮局。怎样走才能使所走的行程最短?

    9、全程多少千米?图4-20 街道示意图解 图中顶点B、D、E、F、G、H、I、J、K、L均是奇顶点,根据欧拉图判定定理,图4-20不是欧拉图。因此,邮递员要想把每条街道只走一遍然后回到邮局是不可能实现的,他必须重复走一些街道。如果邮递员想要行程最短,他重复走的街道数越少越好、越短越好。因为欧拉回路是一条通过图中每条边一次且仅一次的路,不存在行程的长短,所以问题转化为如何在图4-20中添加边,使添加的边的长度之和最短,且消除图4-20中所有的奇顶点。图4-20有10个奇顶点,至少添加5条边,故一个使长度之和最短的添加边的方案如图4-21所示。 图4-21接下来,我们可利用Fleury算法在图4.21中找到一条欧拉回路,比如ABCDJMLKNGHK LIHIJDEBEFGFA,这是一条邮递员行程最短的回路,最短行程为34千米。课后小记


    注意事项

    本文(《应用数学基础》教案4.2 欧拉图及其应用.docx)为本站会员(momomo)主动上传,其收益全归该用户,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!




    Copyright@ 2017-2037 Www.163WenKu.Com  网站版权所有  |  资源地图   
    IPC备案号:蜀ICP备2021032737号  | 川公网安备 51099002000191号


    侵权投诉QQ:3464097650  资料上传QQ:3464097650
       


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

    163文库