离散数学--第十五章-欧拉图和哈密顿图.ppt
《离散数学--第十五章-欧拉图和哈密顿图.ppt》由会员分享,可在线阅读,更多相关《离散数学--第十五章-欧拉图和哈密顿图.ppt(33页珍藏版)》请在咨信网上搜索。
1、 1第十五章第十五章 欧拉图与哈密顿图欧拉图与哈密顿图主要内容主要内容欧拉图欧拉图哈密顿图哈密顿图带权图与货郎担问题带权图与货郎担问题 215.1 欧拉图欧拉图历史背景:哥尼斯堡七桥问题与欧拉图历史背景:哥尼斯堡七桥问题与欧拉图 3欧拉图定义欧拉图定义定义定义15.115.1 (1)(1)欧拉通路欧拉通路经过图中每条边一次且仅一次行遍所有顶经过图中每条边一次且仅一次行遍所有顶点的通路点的通路.(2)(2)欧拉回路欧拉回路经过图中每条边一次且仅一次行遍所有顶经过图中每条边一次且仅一次行遍所有顶点的回路点的回路.(3)(3)欧拉图欧拉图具有欧拉回路的图具有欧拉回路的图.(4)(4)半欧拉图半欧拉图
2、具有欧拉通路而无欧拉回路的图具有欧拉通路而无欧拉回路的图.几点说明:几点说明:规定平凡图为欧拉图规定平凡图为欧拉图.欧拉通路是生成的简单通路,欧拉回路是生成的简单回路欧拉通路是生成的简单通路,欧拉回路是生成的简单回路.环不影响图的欧拉性环不影响图的欧拉性.4上图中,上图中,(1),(4)(1),(4)为欧拉图,为欧拉图,(2),(5)(2),(5)为半欧拉图,为半欧拉图,(3),(6)(3),(6)既不是欧拉图,也不是半欧拉图既不是欧拉图,也不是半欧拉图.在在(3),(6)(3),(6)中各至少加几条中各至少加几条边才能成为欧拉图?边才能成为欧拉图?欧拉图实例欧拉图实例 5无向欧拉图的判别法无
3、向欧拉图的判别法定理定理15.1 15.1 无向图无向图G G是欧拉图当且仅当是欧拉图当且仅当G G连通且无奇度数顶点连通且无奇度数顶点.证证 :若若G G 为平凡图无问题为平凡图无问题.下设下设G G为为 n n 阶阶 m m 条边的无向图条边的无向图.必要性必要性 设设C C 为为G G 中一条欧拉回路中一条欧拉回路.(1)(1)G G 连通显然连通显然.(2)(2)v vi i V V(G G),v vi i在在C C上每出现一次获上每出现一次获2 2度,所以度,所以v vi i为偶度顶为偶度顶点点.由由v vi i 的任意性,结论为真的任意性,结论为真.充分性充分性 对边数对边数m m
4、做归纳法(第二数学归纳法)做归纳法(第二数学归纳法).(1)(1)m m=1=1时,时,G G为一个环,则为一个环,则G G为欧拉图为欧拉图.(2)(2)设设m m k k(k k 1 1)时结论为真,)时结论为真,m m=k k+1+1时如下证明:时如下证明:6PLAY从以上证明不难看出:欧拉图是若干个边不重的圈之并从以上证明不难看出:欧拉图是若干个边不重的圈之并,见示意图,见示意图3.3.7欧拉图的判别法欧拉图的判别法定理定理15.2 15.2 无向图无向图G G是半欧拉图当且仅当是半欧拉图当且仅当G G 连通且恰连通且恰有两个奇度顶点有两个奇度顶点.证证:必要性简单必要性简单.充分性(利
5、用定理充分性(利用定理15.115.1)设设u u,v v为为G G 中的两个奇度顶点,令中的两个奇度顶点,令 G G =G G(u u,v v)则则G G 连通且无奇度顶点,由定理连通且无奇度顶点,由定理15.115.1知知G G 为欧拉图,因而为欧拉图,因而存在欧拉回路存在欧拉回路C C,令,令 =C C(u u,v v)则则 为为 G G 中欧拉通路中欧拉通路.8有向欧拉图的判别法有向欧拉图的判别法定理定理15.3 15.3 有向图有向图D D是欧拉图当且仅当是欧拉图当且仅当D D是强连通的是强连通的且每个顶点的入度都等于出度且每个顶点的入度都等于出度.本定理的证明类似于定理本定理的证明
6、类似于定理15.1.15.1.定理定理15.4 15.4 有向图有向图D D是半欧拉图当且仅当是半欧拉图当且仅当D D是单向连通的,且是单向连通的,且D D中恰有两个奇度顶点,其中一个的入度比出度大中恰有两个奇度顶点,其中一个的入度比出度大1 1,另一个,另一个的出度比入度大的出度比入度大1 1,而其余顶点的入度都等于出度,而其余顶点的入度都等于出度.本定理的证明类似于定理本定理的证明类似于定理15.1.15.1.定理定理15.5 15.5 G G是非平凡的欧拉图当且仅当是非平凡的欧拉图当且仅当G G是连通的且为若干是连通的且为若干个边不重的圈之并个边不重的圈之并.可用归纳法证定理可用归纳法证
7、定理15.5.15.5.9例题例题例例1 1 设设G G是欧拉图,但是欧拉图,但G G不是平凡图,也不是一个环,则不是平凡图,也不是一个环,则(G G)2.2.证证 只需证明只需证明G G中不可能有桥(如何证明?)中不可能有桥(如何证明?)上图中,上图中,(1),(2)(1),(2)两图都是欧拉图,均从两图都是欧拉图,均从A A点出发,如何一次成功地点出发,如何一次成功地走出一条欧拉回路来?走出一条欧拉回路来?(1)(2)(1)(2)10FleuryFleury算法算法算法:算法:(1)(1)任取任取v v0 0 V V(G G),令,令P P0 0=v v0 0.(2)(2)设设P Pi i
8、=v v0 0e e1 1v v1 1e e2 2e ei iv vi i 已经行遍,按下面方法从已经行遍,按下面方法从 E E(G G)e e1 1,e e2 2,e ei i 中选取中选取e ei i+1+1:(a)(a)e ei i+1+1与与v vi i 相关联;相关联;(b)(b)除非无别的边可供行遍,否则除非无别的边可供行遍,否则e ei i+1+1不应该为不应该为 G Gi i=G G e e1 1,e e2 2,e ei i 中的桥中的桥.(3)(3)当当 (2)(2)不能再进行时,算法停止不能再进行时,算法停止.可以证明算法停止时所得简单通路可以证明算法停止时所得简单通路 P
9、 Pm m =v v0 0e e1 1v v1 1e e2 2e em mv vm m(v vm m=v v0 0)为为G G 中一条欧拉回路中一条欧拉回路.用用FleuryFleury算法走出上一页图算法走出上一页图(1),(2)(1),(2)从从A A出发出发(其实从任何一点出发都可其实从任何一点出发都可以)的欧拉回路各一条以)的欧拉回路各一条.11英国数学家哈密顿于英国数学家哈密顿于18561856年提出周游世界的问题:年提出周游世界的问题:若要周游世界上的二十个名城,且城与城之间只若要周游世界上的二十个名城,且城与城之间只有一条路,则能否把每一个城走且只走一次,最有一条路,则能否把每一
10、个城走且只走一次,最后返回到原地后返回到原地.该问题可以抽象为图论问题:用该问题可以抽象为图论问题:用2020个顶点分别表个顶点分别表示示2020个城市,两个顶点间的连线表示城市间的路,个城市,两个顶点间的连线表示城市间的路,要求找一条从某点出发,经过各个要求找一条从某点出发,经过各个顶点顶点一次且仅一次且仅一次,最后能否返回到出发点的路线一次,最后能否返回到出发点的路线?15.2 15.2 哈密顿图哈密顿图 12 (1)(2)13哈密顿图与半哈密顿图哈密顿图与半哈密顿图定义定义15.215.2 (1)(1)哈密顿通路哈密顿通路经过图中所有顶点一次仅一次的通路经过图中所有顶点一次仅一次的通路.
11、(2)(2)哈密顿回路哈密顿回路经过图中所有顶点一次仅一次的回路经过图中所有顶点一次仅一次的回路.(3)(3)哈密顿图哈密顿图具有哈密顿回路的图具有哈密顿回路的图.(4)(4)半哈密顿图半哈密顿图具有哈密顿通路且无哈密顿回路的图具有哈密顿通路且无哈密顿回路的图.几点说明:几点说明:1 1、平凡图是哈密顿图、平凡图是哈密顿图.2 2、哈密顿通路是初级通路,哈密顿回路是初级回路、哈密顿通路是初级通路,哈密顿回路是初级回路.3 3、环与平行边不影响哈密顿性、环与平行边不影响哈密顿性.4 4、哈密顿图的实质是能将图中的所有顶点排在同一个圈上、哈密顿图的实质是能将图中的所有顶点排在同一个圈上.14实例实
12、例在上图中,在上图中,(1),(2)(1),(2)是哈密顿图是哈密顿图;(3)(3)是半哈密顿图是半哈密顿图;(4)(4)既不是哈密顿图,也不是半哈密顿图,为什么?既不是哈密顿图,也不是半哈密顿图,为什么?15无向哈密顿图的一个必要条件无向哈密顿图的一个必要条件定理定理15.6 15.6 设无向图设无向图G G=是哈密顿图,对于任意是哈密顿图,对于任意V V1 1 V V且且V V1 1,均有,均有 p p(G G V V1 1)|V V1 1|证证 设设C C为为G G中一条哈密顿回路。中一条哈密顿回路。当当V1V1顶点在顶点在C C上均不相邻时,上均不相邻时,p p(C C V V1)1)
13、达到最大值|V V1|1|,而当而当V1中顶点在C上有彼此相邻的情况时,均有p(CV1)|V1|,总之有 p p(C C V V1 1)|V V1 1|.|.而而C C是是G G的生成子图,所以有的生成子图,所以有 p p(G G V V1 1)p p(C C V V1 1)|V V1 1|说明:说明:本定理的条件只是哈密顿图的必要条件,但不是充分条件。本定理的条件只是哈密顿图的必要条件,但不是充分条件。可以验证彼得森图满足定理的条件,但它不是哈密顿图。可以验证彼得森图满足定理的条件,但它不是哈密顿图。16推论推论 设无向图设无向图G G=是半哈密顿图,对于任意的是半哈密顿图,对于任意的V V
14、1 1 V V且且V V1 1均有均有 p p(G G V V1 1)|V V1 1|+1|+1证证:令令P P为为G G中起于中起于u u终于终于v v的哈密顿通路,令的哈密顿通路,令G G =G G(u u,v v),则,则G G 为为哈密顿图,于是哈密顿图,于是 p p(GG V V1)1)|V V1|1|于是于是 p p(G G V V1 1)=)=p p(G G V V1 1(u u,v v)p p(GG V V1)+11)+1|V V1 1|+1|+1 17几点说明几点说明1 1、定理、定理15.615.6中的条件是哈密顿图的必要条件,但不是充分条件中的条件是哈密顿图的必要条件,但
15、不是充分条件(彼得松图)(彼得松图)2 2、常利用定理、常利用定理15.615.6判断某些图不是哈密顿图判断某些图不是哈密顿图.例例2 2 设设G G为为n n阶无向连通简单图,若阶无向连通简单图,若G G中有割点或桥,则中有割点或桥,则G G不不 是哈密顿图是哈密顿图.证证 设设v v为割点,则为割点,则 p p(G G v v)2|2|v v|=1.|=1.K K2 2有桥,它显然不是哈密顿图有桥,它显然不是哈密顿图.除除K K2 2外,其他有桥的图(连通的)外,其他有桥的图(连通的)均有割点均有割点.其实,本例对非简单连通图也对其实,本例对非简单连通图也对.18无向哈密顿图的一个充分条件
16、无向哈密顿图的一个充分条件定理定理15.715.7 设设G G是是n n阶无向简单图,若对于任意不相邻的顶阶无向简单图,若对于任意不相邻的顶v vi i,v vj j,均有均有 d d(v vi i)+)+d d(v vj j)n n 1 1 ()则则G G 中存在哈密顿通路中存在哈密顿通路.证明:证明:(1)(1)由由()证证G G连通连通(2)(2)=v v1 1v v2 2v vl l 为为G G中极大路径中极大路径.若若l l=n n,证毕证毕.(3)(3)否则,证否则,证G G 中存在过中存在过 上所有顶点的圈上所有顶点的圈C C,由,由(1)(1)知知C C外顶外顶点存在与点存在与
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第十五 欧拉图 哈密
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。