离散数学第15章.pptx

上传人:莉*** 文档编号:80092087 上传时间:2023-03-22 格式:PPTX 页数:31 大小:3.45MB
返回 下载 相关 举报
离散数学第15章.pptx_第1页
第1页 / 共31页
离散数学第15章.pptx_第2页
第2页 / 共31页
点击查看更多>>
资源描述

《离散数学第15章.pptx》由会员分享,可在线阅读,更多相关《离散数学第15章.pptx(31页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1欧拉图定义定义15.1 (1)欧拉通路经过图中每条边一次且仅一次行遍所有顶点的通路.(2)欧拉回路经过图中每条边一次且仅一次行遍所有顶点的回路.(3)欧拉图具有欧拉回路的图.(4)半欧拉图具有欧拉通路而无欧拉回路的图.几点说明:规定平凡图为欧拉图.欧拉通路是生成的简单通路,欧拉回路是生成的简单回路.环不影响图的欧拉性.第1页/共31页2上图中,(1),(4)为欧拉图,(2),(5)为半欧拉图,(3),(6)既不是欧拉图,也不是半欧拉图.在(3),(6)中各至少加几条边才能成为欧拉图?欧拉图实例第2页/共31页3无向欧拉图的判别法定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点.证

2、若G 为平凡图无问题.下设G为 n 阶 m 条边的无向图.必要性 设C 为G 中一条欧拉回路.(1)G 连通显然.(2)viV(G),vi在C上每出现一次获2度,所以vi为偶度顶点.由vi 的任意性,结论为真.充分性 对边数m做归纳法(第二数学归纳法).(1)m=1时,G为一个环,则G为欧拉图.(2)设mk(k1)时结论为真,m=k+1时如下证明:第3页/共31页4PLAY从以上证明不难看出:欧拉图是若干个边不重的圈之并,见示意图3.第4页/共31页5欧拉图的判别法定理15.2 无向图G是半欧拉图当且仅当G 连通且恰有两个奇度顶点.证 必要性简单.充分性(利用定理15.1)设u,v为G 中的两

3、个奇度顶点,令 G =G(u,v)则G 连通且无奇度顶点,由定理15.1知G 为欧拉图,因而存在欧拉回路C,令 =C(u,v)则 为 G 中欧拉通路.第5页/共31页6有向欧拉图的判别法定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.4 有向图D是半欧拉图当且仅当D是单向连通的,且D中恰有两个奇度顶点,其中一个的入度比出度大1,另一个的出度比入度大1,而其余顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并.可用归纳法证定理15.5.第6页/共3

4、1页7例题例1 设G是欧拉图,但G不是平凡图,也不是一个环,则(G)2.证 只需证明G中不可能有桥(如何证明?)上图中,(1),(2)两图都是欧拉图,均从A点出发,如何一次成功地走出一条欧拉回路来?(1)(2)第7页/共31页8Fleury算法算法:(1)任取v0V(G),令P0=v0.(2)设Pi=v0e1v1e2eivi 已经行遍,按下面方法从 E(G)e1,e2,ei 中选取ei+1:(a)ei+1与vi 相关联;(b)除非无别的边可供行遍,否则ei+1不应该为 Gi=Ge1,e2,ei 中的桥.(3)当(2)不能再进行时,算法停止.可以证明算法停止时所得简单通路 Pm=v0e1v1e2

5、emvm(vm=v0)为G 中一条欧拉回路.用Fleury算法走出上一页图(1),(2)从A出发(其实从任何一点出发都可以)的欧拉回路各一条.第8页/共31页915.2 哈密顿图历史背景:哈密顿周游世界问题与哈密顿图 (1)(2)第9页/共31页10哈密顿图与半哈密顿图定义15.2 (1)哈密顿通路经过图中所有顶点一次仅一次的通路.(2)哈密顿回路经过图中所有顶点一次仅一次的回路.(3)哈密顿图具有哈密顿回路的图.(4)半哈密顿图具有哈密顿通路且无哈密顿回路的图.几点说明:平凡图是哈密顿图.哈密顿通路是初级通路,哈密顿回路是初级回路.环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点

6、排在同一个圈上第10页/共31页11实例在上图中,(1),(2)是哈密顿图;(3)是半哈密顿图;(4)既不是哈密顿图,也不是半哈密顿图,为什么?第11页/共31页12无向哈密顿图的一个必要条件定理15.6 设无向图G=是哈密顿图,对于任意V1V且V1,均有 p(GV1)|V1|证 设C为G中一条哈密顿回路(1)p(C V1)|V1|(2)p(G V1)p(C V1)|V1|(因为C G)推论 设无向图G=是半哈密顿图,对于任意的V1 V且V1均有 p(G V1)|V1|+1证 令 uv为G中哈密顿通路,令G =G(u,v),则G 为哈密顿图.于是 p(G V1)=p(G V1(u,v)|V1|

7、+1第12页/共31页13几点说明l定理15.6中的条件是哈密顿图的必要条件,但不是充分条件(彼得松图)l由定理15.6立刻可知,Kr,s当sr+1时不是哈密顿图.易知Kr,r(r2)时都是哈密顿图,Kr,r+1都是半哈密顿图.l常利用定理15.6判断某些图不是哈密顿图.例2 设G为n阶无向连通简单图,若G中有割点或桥,则G不 是哈密顿图.证 设v为割点,则 p(Gv)2|v|=1.K2有桥,它显然不是哈密顿图.除K2外,其他有桥的图(连通的)均有割点.其实,本例对非简单连通图也对.第13页/共31页14无向哈密顿图的一个充分条件定理15.7 设G是n阶无向简单图,若对于任意不相邻的顶点vi,

8、vj,均有 d(vi)+d(vj)n1 ()则G 中存在哈密顿通路.证明线索:(1)由()证G连通(2)=v1v2vl 为G中极大路径.若l=n,证毕.(3)否则,证G 中存在过上所有顶点的圈C,由(1)知C外顶点存在与C上某顶点相邻顶点,从而得比更长的路径,重复(2)(3),最后得G中哈密顿通路.第14页/共31页15证明证(着重关键步骤)(1)由()及简单图的性质,用反证法证明G连通.(2)=v1v2vl 为极大路径,l n,若l=n(结束).下面讨论ln的情况,即要证G中存在过上所有顶点的圈.若(v1,vl)在G中,则(u,v)为G中圈 否则,设否则,设v1与与 上上 相邻,则相邻,则k

9、 2(否则由极大路径端点性质否则由极大路径端点性质及及(),会得到,会得到d(v1)+d(vl)1+l 24,由定理15.6可知图中无哈密顿回路.在国际象棋盘上跳马有解,试试看.第22页/共31页23设GG,称 为G 的权,并记作W(G),即定义15.3 给定图G=,(G为无向图或有向图),设W:ER(R为实数集),对G中任意边e=(vi,vj)(G为有向图时,e=),设W(e)=wij,称实数wij 为边e上的权,并将wij标注在边e上,称G为带权图,此时常将带权图G记作.15.3 最短路问题与货郎担问题第23页/共31页24货郎担问题设G=为一个n阶完全带权图Kn,各边的权非负,且有的边的

10、权可能为.求G中的一条最短的哈密顿回路,这就是货郎担问题的数学模型.完全带权图Kn(n3)中不同的哈密顿回路数(1)Kn中有(n1)!条不同的哈密顿回路(定义意义下)(2)完全带权图中有(n1)!条不同的哈密顿回路(3)用穷举法解货郎担问题算法的复杂度为(n1)!,当n较大时,计算量惊人地大第24页/共31页25 解 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)第25页/共31页26第十五章 习题课 主要内容

11、l欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法l哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图l带权图、货郎担问题基本要求l深刻理解欧拉图、半欧拉图的定义及判别定理l深刻理解哈密顿图、半哈密顿图的定义.l会用哈密顿图的必要条件判断某些图不是哈密顿图.l会用充分条件判断某些图是哈密顿图.要特别注意的是,不能将必要条件当作充分条件,也不要将充分条件当必要条件.第26页/共31页271.设G为n(n 2)阶无向欧拉图,证明G中无桥(见例1思考题)方法二:反证法.利用欧拉图无奇度顶点及握手定理的推论.否则,设e=(u,v)为G中桥,则G e产生两个连通分支G1,G2,不妨设u在G1中,v在G2中.由于

12、从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不为桥.第27页/共31页282.证明下图不是哈密顿图.(破坏必要条件)方法一.利用定理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

13、|.方法三.利用可能出现在哈密顿回路上的边至少有n(n为阶数)条这也是哈密顿图的一个必要条件,记为().此图中,n=13,m=21.由于h,l,j 均为4度顶点,a,c,e为3度顶点,且它们关联边互不相同.而在哈密顿回路上,每个顶点准确地关联两条边,于是可能用的边至多有21(3 2+3 1)=12.这达不到()的要求.第28页/共31页293某次国际会议8人参加,已知每人至少与其余7人中的4人有共同语言,问服务员能否将他们安排在同一张圆桌就座,使得每个人都与两边的人交谈?解 图是描述事物之间关系的最好的手段之一.做无向图G=,其中 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由本题想到的:哈密顿回图的实质是能将图中所有的顶点排在同一个圈中.第29页/共31页304.距离(公里)如图所示.他如何走行程最短?练习 4最短的路为ABCDA,距离为36公里,其余两条各为多少?第30页/共31页31感谢您的观看!第31页/共31页

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 应用文书 > PPT文档

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

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