- 1、本文档共62页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
五欧拉图与哈密顿图
问题的提出 作业 P303 . . . 例2 下列各图中 是否有哈密顿回路、哈密顿通路? (1) 带1度顶点的图无哈密顿回路; (2) 若图中有2度顶点,则关联这个顶点的两条边属于任意一条哈密顿回路; (3) 当构造哈密顿回路且该回路经过某一顶点时除了回路所用的两条边,不用再考虑这个顶点关联的其它边; (4) 哈密顿回路不能包含更小的回路; (5) 若图中某些必须出现在哈密顿回路中的边已构成回,而图中尚有不在该回路中的点,则此图不是哈密顿图。 说 明: 从定义可以看出,哈密顿通路是图中生成的初 级通路,而哈密顿回路是生成的初级回路. 判断一个图是否为哈密顿图,就是判断能否将 图中所有顶点都放置在一个初级回路(圈)上, 但这不是一件易事. 与判断一个图是否为欧拉图不一样,到目前为止, 人们还没有找到哈密顿图简单的充分必要条件. 下面给出的定理都是哈密顿通路(回路)的必要 条件或充分条件. 二、哈密顿图与半哈密顿图的 一些必要与充分条件 定理15.6设无向图G = V, E 是哈密顿图, 对于任意 均有 其中,p(G-V1) 为 G-V1 的连通分支数. 必要条件 证: 设C为G中任意一条哈密顿回路,易知, 当V1中顶点在C上均不相邻时,p(C-V1)达到最 大值|V1|,而当V1中顶点在C上有彼此相邻的情 况时,均有 所以有 而C是G的生成子图,所以,有 可验证彼得松图 满足定理中的条件, 但它不是哈密顿图. 当然,若一个图不满足定理中的条件,它 一定不是哈密顿图. 定理15.6的条件是哈密顿图的必要条件,但不是充分条件. 常用它判断一个图不是哈密顿图。 推论 设无向图G = V, E 是半哈密顿图,对于 任意的 均有 证: 设P是G中起于 u 终于 v 的哈密顿通路, 令G= G∪(u ,v)(在G的顶点 u, v 之间加新边), 易知G为哈密顿图, 由定理15.6可知, 而有 例15.3 在图15.6中给出的三个图都是二部图. 它们中的那些是哈密顿图?哪些是半哈密顿图? 为什么? 图15.6 解 在(1)中,易知互补顶点子集 设此二部图为G1, 则 由定理15.6及其推论可知,G1不是哈密顿图, 也不是半哈密顿图. 设(2)中图为G2,则 其中 易知, 由定理15.6可知, G2不是哈密顿图,但G2是半哈密顿图,其实, 为G2中一条哈密顿通路. 设(3)中图为G3. 其中 G3中存在哈密顿 回路(演示),如 所以G3是哈密顿图. 通过本例,清楚地看出,哈密顿通路是经过 图中所有顶点的一条初级通路,而哈密顿回路 是经过图中所有顶点的初级回路. 例15.4 设G是 n 阶无向连通图. 证明: 若G中有割点或桥,则G不是哈密顿图. 对于二部图还能得出下面结论: 一般情况下,设二部图G=V1,V2,E, 由定理15.6及其推论可以得出下面结论: (2)若G是半哈密顿图,则|V2|=|V1|+1. (3)若|V2|≥|V1|+2,则G不是哈密顿图, 也不是半哈密顿图. (1)若G是哈密顿图,则|V1|=|V2|. 定理15.7 设G是n阶无向简单图,若对于G中 任意不相邻的顶点 vi , vj,均有 d( vi )+ d( vj )≥ n-1
您可能关注的文档
最近下载
- 河北对口单招第十类职业适应性测试(计算机)-第七章演示文稿软件应用课件ppt.pptx VIP
- 亚硫酸氢钠安全技术说明书.docx VIP
- 疾控大学习《病原微生物实验室生物安全风险识别和控制》习题答案.docx
- 四年级上册数学三位数乘两位数竖式计算题练习150道.pdf
- 医院公开招聘简章.pdf
- XX银行A分行业务人员培训效果评估.pdf VIP
- 思维导图在高中化学学习中的应用教学研究开题报告教学研究课题报告.docx
- GB 50937-2013 选煤厂管道安装工程施工与验收规范.docx
- 第四章 控制及其设计 课件-2023-2024学年高中通用技术苏教版(2019)必修《技术与设计2》.pptx VIP
- 学习贯彻党的二十届三中全会精神测试题三套(含答案).docx VIP
文档评论(0)