离散数学第十五章_第1页
离散数学第十五章_第2页
离散数学第十五章_第3页
离散数学第十五章_第4页
离散数学第十五章_第5页
已阅读5页,还剩28页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

离散数学第十五章1第1页,课件共33页,创作于2023年2月第十五章欧拉图与哈密顿图预备知识无向图G=<V,E>d(v),d+(v),d(v)奇度顶点与偶度顶点连通,通路,回路2第2页,课件共33页,创作于2023年2月瑞士数学家,最多产的数学家≥1100书籍论文全集≥75卷13个孩子最后17年失明

ADBCQuestion:如何将左边图所示的七桥问题转换为点和边来描述?一个游人怎样才能不重复地一次走遍七座桥,最后又回到出发点呢?

LinktothevideoLeonhardEuler:1707~1783历史背景3第3页,课件共33页,创作于2023年2月下面哪些图形可以一笔画,哪些图形不能一笔画?试一试:(1)(2)(3)(4)(5)(6)4第4页,课件共33页,创作于2023年2月(2)(2)(2)(2)(3)(3)(4)(4)(2)(2)(3)(2)(3)(2)(3)(4)(3)(1)(1)(1)(3)(4)(2)(2)(2)偶点(1)(3)(2)(2)奇点5第5页,课件共33页,创作于2023年2月●中途点特征:笔沿着某条边进去后,必定沿另一条边出去,于是知道与中途点为端点的边必定是成对出现的,这样中途点必定是偶点。进去出来进去出来如果起点和终点重合,则与他们相连的边是偶数条,所以也是偶点起点和终点不重合,与他们相连的边奇数条,则是都是奇点“一笔画”图形特征:一个图形可以“一笔画”则奇点的个数是0个或2个6第6页,课件共33页,创作于2023年2月欧拉图定义定义15.1(1)欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路.(2)欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路.(3)欧拉图——具有欧拉回路的图.(4)半欧拉图——具有欧拉通路而无欧拉回路的图.几点说明:规定平凡图为欧拉图.欧拉通路是生成的简单通路,欧拉回路是生成的简单回路.环不影响图的欧拉性.7第7页,课件共33页,创作于2023年2月上图中,(1),(4)为欧拉图,(2),(5)为半欧拉图,(3),(6)既不是欧拉图,也不是半欧拉图.在(3),(6)中各至少加几条边才能成为欧拉图?欧拉图实例8第8页,课件共33页,创作于2023年2月无向欧拉图的判别法定理15.1

无向图G是欧拉图当且仅当G连通且无奇度数顶点.证若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时如下证明:9第9页,课件共33页,创作于2023年2月PLAY从以上证明不难看出:欧拉图是若干个边不重的圈之并,见示意图3.10第10页,课件共33页,创作于2023年2月欧拉图的判别法定理15.2

无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点.证必要性简单.充分性(利用定理15.1)设u,v为G中的两个奇度顶点,令

G=G(u,v)则G连通且无奇度顶点,由定理15.1知G为欧拉图,因而存在欧拉回路C,令

=C(u,v)则为G中欧拉通路.11第11页,课件共33页,创作于2023年2月下图是某展览厅的平面图,它由五个展室组成,任两展室之间都有门相通,整个展览厅还有一个进口和一个出口,问游人能否一次不重复地穿过所有的门,并且从入口进,从出口出?AFDCBE练习112第12页,课件共33页,创作于2023年2月下图是一个公园的平面图.要使游客走遍每条路而不重复,问出入口应设在哪里?ABCCDEFGHIJK练习213第13页,课件共33页,创作于2023年2月有向欧拉图的判别法定理15.3

有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.4

有向图D是半欧拉图当且仅当D是单向连通的,且D中恰有两个奇度顶点,其中一个的入度比出度大1,另一个的出度比入度大1,而其余顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.5

G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并.可用归纳法证定理15.5.14第14页,课件共33页,创作于2023年2月查阅有关欧拉图应用研究的文献书面总结:研究动机研究框架关键的发现结论作业15第15页,课件共33页,创作于2023年2月15.2

哈密顿图历史背景:哈密顿周游世界问题与哈密顿图

(1)(2)16第16页,课件共33页,创作于2023年2月17第17页,课件共33页,创作于2023年2月哈密顿图与半哈密顿图定义15.2

(1)哈密顿通路——经过图中所有顶点一次仅一次的通路.(2)哈密顿回路——经过图中所有顶点一次仅一次的回路.(3)哈密顿图——具有哈密顿回路的图.(4)半哈密顿图——具有哈密顿通路且无哈密顿回路的图.几点说明:平凡图是哈密顿图.哈密顿通路是初级通路,哈密顿回路是初级回路.环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上18第18页,课件共33页,创作于2023年2月实例在上图中,(1),(2)是哈密顿图;(3)是半哈密顿图;(4)既不是哈密顿图,也不是半哈密顿图,为什么?19第19页,课件共33页,创作于2023年2月无向哈密顿图的一个必要条件定理15.6

设无向图G=<V,E>是哈密顿图,对于任意V1V且V1,均有p(GV1)|V1|证设C为G中一条哈密顿回路(1)p(CV1)|V1|(2)p(GV1)

p(CV1)|V1|(因为CG)推论设无向图G=<V,E>是半哈密顿图,对于任意的V1V且V1均有

p(GV1)|V1|+1证令uv为G中哈密顿通路,令G=G(u,v),则G为哈密顿图.于是

p(GV1)=p(GV1(u,v))|V1|+120第20页,课件共33页,创作于2023年2月(1)若G是哈密顿图,则一定满足上式;(2)满足上式却不一定是哈密顿图;(3)不满足上式一定不是哈密顿图。21第21页,课件共33页,创作于2023年2月定理应用举例利用定理说明下图不是哈密顿图。22第22页,课件共33页,创作于2023年2月解答取S={v1,v4},则:|S|=2p(V-S)=3,不满足:p(V-S)≤|S|不是哈密顿图23第23页,课件共33页,创作于2023年2月几点说明由定理15.6立刻可知,Kr,s当sr+1时不是哈密顿图.易知Kr,r(r2)时都是哈密顿图,Kr,r+1都是半哈密顿图.常利用定理15.6判断某些图不是哈密顿图.例2设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.证设v为割点,则p(Gv)2>|{v}|=1.K2有桥,它显然不是哈密顿图.除K2外,其他有桥的图(连通的)均有割点.其实,本例对非简单连通图也对.24第24页,课件共33页,创作于2023年2月无向哈密顿图的一个充分条件定理15.7

设G是n阶无向简单图,若对于任意不相邻的顶点vi,vj,均有

d(vi)+d(vj)

n1()则G中存在哈密顿通路.推论设G为n(n3)阶无向简单图,若对于G中任意两个不相邻的顶点vi,vj,均有

d(vi)+d(vj)

n

()则G中存在哈密顿回路,从而G为哈密顿图.25第25页,课件共33页,创作于2023年2月几点说明由定理15.7的推论可知,Kn(n3)均为哈密顿图.(1)满足上式一定是哈密顿图;(2)是哈密顿图不一定满足上式;(3)不是哈密顿图一定不满足上式。完全图Kn(n3)中任何两个顶点u,v,均有

d(u)+d(v)=2(n1)

n(n3),所以Kn为哈密顿图.26第26页,课件共33页,创作于2023年2月定理应用举例任意两点的度之和为4n=6不满足d(vi)+d(vj)≥n但却是哈密顿图,也有哈密顿路径。是哈密顿图27第27页,课件共33页,创作于2023年2月n(n2)阶竞赛图中存在哈密顿通路定理15.9

若D为n(n2)阶竞赛图,则D中具有哈密顿通路证明思路:注意,竞赛图的基图是无向完全图.对n(n2)做归纳.只需观察下面两个图.无向哈密顿图的充分条件28第28页,课件共33页,创作于2023年2月设GG,称为G的权,并记作W(G),即定义15.3

给定图G=<V,E>,(G为无向图或有向图),设W:ER

(R为实数集),对G中任意边e=(vi,vj)(G为有向图时,e=<vi,vj>),设W(e)=wij,称实数wij为边e上的权,并将wij标注在边e上,称G为带权图,此时常将带权图G记作<V,E,W>.15.3最短路问题与货郎担问题29第29页,课件共33页,创作于2023年2月例:一位旅客要从A城到B城他希望选择一条途中中转次数最少的路线;他希望选择一条途中所花时间最短的路线;他希望选择一条途中费用最小的路线;v5v4v3v2v1v0

1006030101020

550这些问题均是带权图上的最短路径问题。边上的权表示一站边上的权代表距离边的权代表费用30第30页,课件共33页,创作于2023年2月货郎担问题设G=<V,E,W>为一个n阶完全带权图Kn,各边的权非负,且有的边的权可能为.求G中的一条最短的哈密顿回路,这就是货郎担问题的数学模型.完全带权图Kn(n3)中不同的哈密顿回路数(1)Kn中有(n1)!条不同的哈密顿回路(定义意义下)(2)完全带权图中有(n1)!条不同的哈密顿回路(3)用穷举法解货郎担问题算法的复杂度为(n1)!,当n较大时,计算量惊人地大31第31页,课件共33页,创作于2023年2月

解C1=a

b

c

d

a,W(C1)=10

C2=a

b

d

c

a,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论