代数结构与图论.ppt

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

第十五章 欧拉图与哈密顿图 主要内容 欧拉图 哈密顿图 带权图与货郎担问题 欧拉图定义 定义15.1 (1) 欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路. (2) 欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路. (3) 欧拉图——具有欧拉回路的图. (4) 半欧拉图——具有欧拉通路而无欧拉回路的图. 几点说明: 规定平凡图为欧拉图. 欧拉通路是生成的简单通路,欧拉回路是生成的简单回路. 环不影响图的欧拉性. 无向欧拉图的判别法 定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点. 证 若G 为平凡图无问题. 下设G为 n 阶 m 条边的无向图. 必要性 设C 为G 中一条欧拉回路. (1) G 连通显然. (2) ?vi?V(G),vi在C上每出现一次获2度,所以vi为偶度顶点. 由vi 的任意性,结论为真. 充分性 对边数m做归纳法(第二数学归纳法). (1) m=1时,G为一个环,则G为欧拉图. (2) 设m?k(k?1)时结论为真,m=k+1时如下证明: 欧拉图的判别法 定理15.2 无向图G是半欧拉图当且仅当G 连通且恰有两个奇 度顶点. 证 必要性简单. 充分性(利用定理15.1) 设u,v为G 中的两个奇度顶点,令 G ? =G?(u,v) 则G ? 连通且无奇度顶点,由定理15.1知G ?为欧拉图,因而 存在欧拉回路C,令 ?=C?(u,v) 则? 为 G 中欧拉通路. 有向欧拉图的判别法 定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶 点的入度都等于出度. 本定理的证明类似于定理15.1. 定理15.4 有向图D是半欧拉图当且仅当D是单向连通的,且 D中恰有两个奇度顶点,其中一个的入度比出度大1,另一个 的出度比入度大1,而其余顶点的入度都等于出度. 本定理的证明类似于定理15.1. 定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干 个边不重的圈之并. 可用归纳法证定理15.5. 例题 例1 设G是欧拉图,但G不是平凡图,也不是一个环,则 ?(G)?2. 证 只需证明G中不可能有桥(如何证明?) Fleury算法 算法: (1) 任取v0?V(G),令P0=v0. (2) 设Pi = v0e1v1e2…eivi 已经行遍,按下面方法从 E(G)?{e1,e2,…,ei }中选取ei+1: (a) ei+1与vi 相关联; (b) 除非无别的边可供行遍,否则ei+1不应该为 Gi = G?{e1,e2,…,ei }中的桥. (3) 当 (2)不能再进行时,算法停止. 可以证明算法停止时所得简单通路 Pm = v0e1v1e2…emvm (vm=v0)为G 中一条欧拉回路. 用Fleury算法走出上一页图(1),(2)从A出发(其实从任何一点 出发都可以)的欧拉回路各一条. 15.2 哈密顿图 历史背景:哈密顿周游世界问题与哈密顿图 哈密顿图与半哈密顿图 定义15.2 (1) 哈密顿通路——经过图中所有顶点一次仅一次的通路. (2) 哈密顿回路——经过图中所有顶点一次仅一次的回路. (3) 哈密顿图——具有哈密顿回路的图. (4) 半哈密顿图——具有哈密顿通路且无哈密顿回路的图. 几点说明: 平凡图是哈密顿图. 哈密顿通路是初级通路,哈密顿回路是初级回路. 环与平行边不影响哈密顿性. 哈密顿图的实质是能将图中的所有顶点排在同一个圈上 实例 在上图中, (1),(2) 是哈密顿图; (3)是半哈密顿图; (4)既不是哈密顿图,也不是半哈密顿图,为什么? 无向哈密顿图的一个必要条件 定理15.6 设无向图G=V,E是哈密顿图,对于任意V1?V且 V1??,均有 p(G?V1) ? |V1| 几点说明 定理15.6中的条件是哈密顿图的必要条件,但不是充分条件(彼得松图) 由定理15.6立刻可知,Kr,s当s?r+1时不是哈密顿图. 易知Kr,r(r?2)时都是哈密顿图,Kr,r+1都是半哈密顿图. 常利用定理15.6判断某些图不是哈密顿图. 例2 设G为n阶无向连通简单图,若G中有割点或桥,则G不 是哈密顿图. 证 设v为割点,则 p(G?v) ? 2|{v}|=1. K2有桥,它显然不是哈密顿图. 除K2外,其他有桥的图(连通的)均有割点. 其实,本例对非简单连通图也对. 无向哈密顿图的一个充分条件 定理15.7 设G是n阶无向简单图,若对于任意不相邻的顶点vi

文档评论(0)

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

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

1亿VIP精品文档

相关文档