欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    离散数学第15章学习教案.pptx

    • 资源ID:17442020       资源大小:6.02MB        全文页数:31页
    • 资源格式: PPTX        下载积分:9金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要9金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

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

    离散数学第15章学习教案.pptx

    会计学1离散数学第离散数学第15章章第一页,共31页。2而无欧拉回路的图.n几点说明(shumng):n规定平凡图为欧拉图.n欧拉通路是生成的简单通路,欧拉回路是生成的简单回路.n环不影响图的欧拉性.第1页/共31页第二页,共31页。3上图中,上图中,(1) ,(4) 为欧拉图,为欧拉图,(2),(5)为半欧拉图,为半欧拉图,(3),(6)既不是欧拉图,也不是半欧拉图既不是欧拉图,也不是半欧拉图. 在在(3),(6)中各至少加几条边才能中各至少加几条边才能(cinng)成为欧拉图?成为欧拉图? 欧拉图实例欧拉图实例(shl)第2页/共31页第三页,共31页。4. n由vi 的任意性,结论为真. n充分性 对边数m做归纳法(第二数学归纳法).n(1) m=1时,G为一个环,则G为欧拉图.n(2) 设mk(k1)时结论为真,m=k+1时如下证明:第3页/共31页第四页,共31页。5PLAY从以上从以上(yshng)证明不难看出:欧拉图是若干个边不重的圈之并,见示意图证明不难看出:欧拉图是若干个边不重的圈之并,见示意图3. 第4页/共31页第五页,共31页。6(dngl)15.1G 因而n存在欧拉回路C,令n=C(u,v)n则为 G 中欧拉通路.第5页/共31页第六页,共31页。7. n本定理的证明类似于定理15.1. n定理15.5 G是非平凡(pngfn)的欧拉图当且仅当G是连通的且为若干n个边不重的圈之并. n可用归纳法证定理15.5. 第6页/共31页第七页,共31页。8上图中,上图中,(1),(2)两图都是欧拉图,均从两图都是欧拉图,均从A点出发,如何点出发,如何(rh)一次成功地走出一条欧拉回路来?一次成功地走出一条欧拉回路来? (1) (2)第7页/共31页第八页,共31页。9的桥. n(3) 当 (2)不能再进行时,算法停止.n可以证明算法停止时所得简单通路 Pm = v0e1v1e2emvmn(vm=v0)为G 中一条欧拉回路. n用Fleury算法走出上一页图(1),(2)从A出发(其实从任何一点n出发都可以)的欧拉回路各一条. 第8页/共31页第九页,共31页。10 (1) (2) 第9页/共31页第十页,共31页。11n.n哈密顿通路是初级(chj)通路,哈密顿回路是初级(chj)回路.n环与平行边不影响哈密顿性.n哈密顿图的实质是能将图中的所有顶点排在同一个圈上第10页/共31页第十一页,共31页。12第11页/共31页第十二页,共31页。13证证 设设C为为G中一条中一条(y tio)哈密顿回路哈密顿回路(1) p(CV1) |V1|(2) p(GV1) p(CV1) |V1| (因为(因为CG)推论推论 设无向图设无向图G=是半哈密顿图,对于任意的是半哈密顿图,对于任意的V1 V且且V1均有均有 p(G V1) |V1|+1证证 令令 uv为为G中哈密顿通路,令中哈密顿通路,令G = G (u,v),则,则G 为哈密顿图为哈密顿图. 于是于是 p(G V1) = p(GV1 (u,v) |V1|+1第12页/共31页第十三页,共31页。14若G中有割点或桥,则G不l是哈密顿图.l证 设v为割点,则 p(Gv) 2|v|=1.l K2有桥,它显然不是哈密顿图. 除K2外,其他有桥的图(连通的)均有割点.l其实,本例对非简单连通图也对.第13页/共31页第十四页,共31页。15. n(3) 否则,证G 中存在过上所有顶点的圈C,由(1) 知C外顶n点存在与C上某顶点相邻顶点,从而得比更长的路径(ljng),重n复(2) (3) ,最后得G中哈密顿通路. 第14页/共31页第十五页,共31页。16 否则,设否则,设v1与与 上上 相邻,则相邻,则k 2 (否则由极大路径端点性质及否则由极大路径端点性质及( ),会得到,会得到d(v1)+d(vl) 1+l 24,由定理,由定理(dngl)15.6可知图中无哈密顿回路可知图中无哈密顿回路.在国际象棋盘上跳马有解,试试看在国际象棋盘上跳马有解,试试看. 第22页/共31页第二十三页,共31页。24设设GG,称称 为为G 的权,并记作的权,并记作W(G ),即,即 ) ()(GEeeW定义定义(dngy)15.3 给定图给定图G = ,(G为无向图或有向图为无向图或有向图),设,设W:ER (R为实数集为实数集),对,对G中任意边中任意边e = (vi,vj) (G为有向图为有向图时,时,e = ),设,设W(e) = wij,称实数,称实数wij 为边为边e上的权,并将上的权,并将wij标注在边标注在边e上,称上,称G为带权图,此时常将带权图为带权图,此时常将带权图G记作记作 . 15.3 最短路最短路(dunl)问题与货郎担问题问题与货郎担问题第23页/共31页第二十四页,共31页。25n(1) Kn(n1)! 密顿回路(定义意义下)n(2) 完全带权图中有(n1)! 条不同的哈密顿回路n(3) 用穷举法解货郎担问题算法的复杂度为(n1)!,当n较大时,计算量惊人地大第24页/共31页第二十五页,共31页。26nW(C3)=9n可见(kjin)C3 (见图中(2) 是最短的,其权为9. 例例6 求图中求图中(1) 所示带权图所示带权图K4中最短哈密顿回路中最短哈密顿回路(hul). (1) (2) 第25页/共31页第二十六页,共31页。27n图的定义. n会用哈密顿图的必要条件判断某些图不是哈密顿图. n会用充分条件判断某些图是哈密顿图. 要特别(tbi)注意的是,不能将必要条件当作充分条件,也不要将充分条件当必要条件. 第26页/共31页第二十七页,共31页。281. 设设G为为n(n2)阶无向欧拉图,证明)阶无向欧拉图,证明(zhngmng)G中无桥中无桥(见例见例1思考题思考题)方法二:反证法方法二:反证法. 利用欧拉图无奇度顶点及握手定理的推论利用欧拉图无奇度顶点及握手定理的推论. 否则,设否则,设e=(u,v)为为G中桥,则中桥,则G e产生两个连通分支产生两个连通分支G1, G2,不妨设,不妨设u在在G1中,中,v在在G2中中. 由于由于(yuy)从从G中删除中删除e时,只改变时,只改变u,v 的度数的度数(各减各减1),因而,因而G1与与G2中均只含一个奇度顶点,这与握手定理推论矛盾中均只含一个奇度顶点,这与握手定理推论矛盾.练习练习(linx)1方法一:直接证明法方法一:直接证明法. 命题命题 (*):设:设C为任意简单回路,为任意简单回路,e为为C上任意一条边,则上任意一条边,则C e连通连通. 证证 设设C为为G中一条欧拉回路,任意的中一条欧拉回路,任意的e E(C),可知可知C e是是G e的子图,由的子图,由( )知知 C e 连通,所以连通,所以e不为桥不为桥. 第27页/共31页第二十八页,共31页。292. 证明下图不是证明下图不是(b shi)哈密顿图哈密顿图. (破坏必要条件破坏必要条件)方法一方法一. 利用利用(lyng)定理定理15.6,取取 V1 = a, c, e, h, j, l,则,则 p(GV1) = 7 |V1| = 6 练习练习(linx) 2方法二方法二. G为二部图,互补顶点子集为二部图,互补顶点子集 V1 = a, c, e, h, j, l, V2 = b, d, f, g, i, k, m, |V1| = 6 7 = |V2|. 方法三方法三. 利用可能出现在哈密顿回路上的边至少有利用可能出现在哈密顿回路上的边至少有n(n为阶数为阶数)条条这也是哈密顿图的一个必要条件,记为(这也是哈密顿图的一个必要条件,记为( ). 此图中,此图中,n = 13,m = 21. 由于由于h, l, j 均为均为4度顶点,度顶点,a, c, e为为3度顶点,且它们关联边互不相同度顶点,且它们关联边互不相同. 而在哈密顿回路上,而在哈密顿回路上,每个顶点准确地关联两条边,于是可能用的边至多有每个顶点准确地关联两条边,于是可能用的边至多有21 (3 2+3 1) = 12. 这达不到(这达不到( )的要求)的要求. 第28页/共31页第二十九页,共31页。303某次国际会议某次国际会议8人参加,已知每人至少与其余人参加,已知每人至少与其余7人中人中(rnzhng)的的4人有共同语言,问服务员能否将他们安排在同一张圆桌就座,使得每个人都与两边的人交谈?人有共同语言,问服务员能否将他们安排在同一张圆桌就座,使得每个人都与两边的人交谈?解解 图是描述事物之间关系的最好的手段之一图是描述事物之间关系的最好的手段之一. 做无向图做无向图G=, 其中其中 V=v| v为与会者为与会者, E=(u,v) | u,vV且且u与与v有共同语言,且有共同语言,且u v. 易知易知G为简单为简单(jindn)图且图且vV, d(v)4,于是,于是,u,vV, 有有d(u)+d(v) 8,由定理,由定理15.7 的推论可知的推论可知G为哈密顿图为哈密顿图. 服务员在服务员在G中找一条哈密顿回路中找一条哈密顿回路C,按,按C中相邻关系安排座位即可中相邻关系安排座位即可. 练习练习(linx) 3由本题想到的:哈密顿回图的实质是能将图中所有的顶点排在同一个圈中由本题想到的:哈密顿回图的实质是能将图中所有的顶点排在同一个圈中.第29页/共31页第三十页,共31页。314. 距离距离(公里公里(n l) 如图所示如图所示. 他如何走行程最短?他如何走行程最短? 最短的路为最短的路为ABCDA,距离为,距离为36公里,其余公里,其余(qy)两条各为多少?两条各为多少?第30页/共31页第三十一页,共31页。

    注意事项

    本文(离散数学第15章学习教案.pptx)为本站会员(知****量)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

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




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开