《离散数学ch15》PPT课件.ppt

  1. 1、本文档共38页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
《离散数学ch15》PPT课件

* 解 C1= a b c d a, W(C1)=10 C2= a b d c a, W(C2)=11 C3= a c b d a, W(C3)=9 可见C3 (见图中(2)) 是最短的,其权为9. 例6 求图中(1) 所示带权图K4中最短哈密顿回路. (1) (2) * 第十五章 习题课 主要内容 欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法 哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图 带权图、货郎担问题 基本要求 深刻理解欧拉图、半欧拉图的定义及判别定理 深刻理解哈密顿图、半哈密顿图的定义. 会用哈密顿图的必要条件判断某些图不是哈密顿图. 会用充分条件判断某些图是哈密顿图. 要特别注意的是,不能将必要条件当作充分条件,也不要将充分条件当必要条件. * 1. 设G为n(n?2)阶无向欧拉图,证明G中无桥(见例1思考题) 方法二:反证法. 利用欧拉图无奇度顶点及握手定理的推论. 否则,设e=(u,v)为G中桥,则G?e产生两个连通分支G1, G2,不妨设u在G1中,v在G2中. 由于从G中删除e时,只改变u,v 的度数(各减1),因而G1与G2中均只含一个奇度顶点,这与握手定理推论矛盾. 练习1 方法一:直接证明法. 命题 (*):设C为任意简单回路,e为C上任意一条边,则C?e连通. 证 设C为G中一条欧拉回路,任意的e?E(C),可知C?e是G?e的子图,由(?)知 C?e 连通,所以e不为桥. * 2. 证明下图不是哈密顿图. (破坏必要条件) 方法一. 利用定理15.6, 取 V1 = {a, c, e, h, j, l},则 p(G?V1) = 7 |V1| = 6 练习 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. 这达不到(?)的要求. * 3.某次国际会议8人参加,已知每人至少与其余7人中的4人有共同语言,问服务员能否将他们安排在同一张圆桌就座,使得每个人都与两边的人交谈? 解 图是描述事物之间关系的最好的手段之一. 做无向图G=V,E, 其中 V={v| v为与会者}, E={(u,v) | u,v?V且u与v有共同语言,且u ? v}. 易知G为简单图且?v?V, d(v)?4,于是,?u,v?V, 有d(u)+d(v) ? 8,由定理15.7 的推论可知G为哈密顿图. 服务员在G中找一条哈密顿回路C,按C中相邻关系安排座位即可. 练习 3 由本题想到的:哈密顿回图的实质是能将图中所有的顶点排在同一个圈中. * 4. 距离(公里) 如图所示. 他如何走行程最短? 练习 4 最短的路为ABCDA,距离为36公里,其余两条各为多少? * * * * * * * * * * * * * * * * * * * * * * * * * 第十五章 欧拉图与哈密顿图 主要内容 欧拉图 哈密顿图 带权图与货郎担问题 * 哥尼斯堡七桥 18世纪初普鲁士的哥尼斯堡,有一条河穿过,河上有两个小岛,有七座桥把两个岛与河岸联系起来(如左图)。有个人提出一个问题:一个步行者怎样才能不重复、不遗漏地一次走完七座桥? 最后回到出发点后来 大数学家欧拉把它转化成一个几何问题(如右图)——一笔画问题。他不仅解决了此问题,且给出了连通图可以一笔画的重要条件是它们是连通的,且奇顶点(通过此点弧的条数是奇数)的个数为0或2. * 15.1 欧拉图 历史背景:哥尼斯堡七桥问题与欧拉图 * 欧拉图定义 定义15.1 (1) 欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路. (2) 欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路. (3) 欧拉图——具有欧拉回路的图. (4) 半欧拉图——具有欧拉通路而无欧拉回路的图. 几点说明: 规定平凡图为欧拉图. 欧拉通路是简单通路,欧拉回路是简单回路. 环不影响图的欧拉性. * 上图中,(1) ,

文档评论(0)

wuyoujun92 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档