离散数学E图和H.ppt

上传人:小飞机 文档编号:6326501 上传时间:2023-10-17 格式:PPT 页数:38 大小:452.50KB
返回 下载 相关 举报
离散数学E图和H.ppt_第1页
第1页 / 共38页
离散数学E图和H.ppt_第2页
第2页 / 共38页
离散数学E图和H.ppt_第3页
第3页 / 共38页
离散数学E图和H.ppt_第4页
第4页 / 共38页
离散数学E图和H.ppt_第5页
第5页 / 共38页
点击查看更多>>
资源描述

《离散数学E图和H.ppt》由会员分享,可在线阅读,更多相关《离散数学E图和H.ppt(38页珍藏版)》请在三一办公上搜索。

1、2023/10/17,离散数学,1,第八章 E图和H图,2023/10/17,离散数学,2,8.1 七桥问题与E图,七桥问题:有四块陆地与连结它们的七座桥,问能否从这四块陆地中的任意一块出发,经过每一座桥恰好一次,最后回到原地?,2023/10/17,离散数学,3,一笔画,该问题等价于“能否一笔画出下图?”,Euler证明了,七桥问题是无解的。,图中:顶点表示陆地,边表示陆地之间的桥。,2023/10/17,离散数学,4,E图,定义:设G是一个图,经过G 的每一条边的链称为E链;闭的E链称为E闭链。如果G中存在E链,称G为半E图;如果G中存在E闭链,称G为E图。下面的讨论中设G是非平凡的连通图

2、。,2023/10/17,离散数学,5,无奇点的连通图是E图,引理:连通图G中无奇点,则G是E图。证明:设G是无奇点的连通图且G不是E图。在所有连通无奇点的非E图中,选一个边最少的图G。因G的每个顶点的度至少是2,从而G必含闭链。,为什么?,若G不含回路,则G是树。我们知道树中至少有两个悬挂点(奇点)。矛盾,所以G中一定含有回路。而回路就是闭链。如果回路之间有重复出现的边,我们可以去掉重复者,使每条边仅出现一次,这样就得到了一条闭链。所以G中必含闭链。,设C是G中最长的闭链,由假设C不是E闭链,于是G E(C)中必含非平凡连通分支G且G中无奇点,显然q(G)q(G)。,为什么?,故G必是E图(

3、由G和C的选法)。于是G有一条E闭链C。因G连通,C和C必有公共点v,以v作为CC的起、终点,于是CC是G的一条闭链且长度大于C的长度,这与C的假设矛盾。故G是E图。,因G不是E图。G无奇点且C无奇点。,2023/10/17,离散数学,6,C,C,G,v,G,G中含闭链图示,CC是一条闭链图示,2023/10/17,离散数学,7,E图是无奇点的连通图,引理8.1.1:E图是无奇点的连通图。证明:设G是E图,C是G的一条E闭链。由于G连通且C是含G的每边恰一次的闭链,因此,C中的每个点都既是起点也是终点。于是,从C上的任一点u出发,每经过一个顶点v,就有两条与v关联的边出现(一进一出)。这样,C

4、上的每个顶点,也即G的每个顶点的度均为偶数,故G中无奇点。由引理和8.1.1,我们有:,定理:连通图G是E图当且仅当G中无奇点。,2023/10/17,离散数学,8,半E图中最多有两个奇点,推论:G是半E图当且仅当G中最多有两个奇点。证明:(必要性)设G是半E图,C是G的一条E链。除起点与终点外,C中每个顶点的度均为偶数。又因G连通,故G最多有两个奇点。(充分性)设G最多只有两个奇点。若G无奇点,则由定理知,G为E图,亦为半E图;若G有两个奇点,设为u和v,则在G中加入e=uv的边,使G中无奇点。由定理知,G+e为E图,即G+e含E闭链C,于是Ce构成G的一条E链,所以G是半E图。,2023/

5、10/17,离散数学,9,哥尼斯城堡桥不是E图,半E图,2023/10/17,离散数学,10,8.2 周游世界问题与H图,周游世界问题:用一个正十二面体的二十个顶点来代表二十个城市,要求从其中任一顶点出发,沿着这个正十二面体的棱走遍这二十个顶点,且每个城市只经过一次,最后回到起点。该问题等价于“能否从下图找一条含所有顶点的回路?”,2023/10/17,离散数学,11,H图,定义:设G是一个图,含G 的每个顶点的通路称为H通路;起点与终点重合的H通路称为H回路;如果G中存在H回路,称G为H图;若G中存在H通路,称G为半H图;说明:H图必是半H图,反之不然。,?,2023/10/17,离散数学,

6、12,Herschel 图,该图是半H图。,因为它是一个具有奇数个顶点的二分图。所以不可能有H回路。,?,因为二分图中的回路一定是偶数条边。(定理5.5.2),2023/10/17,离散数学,13,H图的一个必要条件,定理 如果G是一个H图,则对V(G)的任何非空真子集 S,均成立:(G S)|S|(8.1)证明:设C是G的H回路(G的所有顶点都在C上),则显然有(C S)|S|成立,其中 SV(G)。由于C S是G S的生成子图,C S的 连通分支数不比G S的少,因此:(G S)(C S)|S|故(8.1)式成立。,2023/10/17,离散数学,14,G(H图),C(H回路),定理证明图

7、示,2023/10/17,离散数学,15,一个非H图的判定,取S为红色点集。|S|=5。,(G S)=6|S|,根据定理,此图不是H图。,2023/10/17,离散数学,16,注意:这只是必要条件,注意定理只是判断H图的必要条件,有的图虽然满足条件,却不是H图。如右边的Peterson图不是H图。可是它却满足定理的条件。,Peterson图,Peterson图是半H图而不是H图。,2023/10/17,离散数学,17,H图的一个充分条件,定理:设G是p(3)阶简单图。如果G中任何两个不邻接的顶点u和v均满足:d(u)+d(v)p(8.2)则G是H图。证明:若满足(8.2)的简单图不是H图,令G

8、(p,q)是其中边数最多的一个图。显然,GKp。,?,因为Kp 一定是H图。,设u,v是G 中不邻接的两个顶点。由G的假设可知,G+uv是H图,且其中的H回路必含uv。于是,G中存在从u到v的H通路P:v1v2vp,其中u=v1,v=vp。,2023/10/17,离散数学,18,H图的一个充分条件,证明:H通路P:v1v2vp,其中u=v1,v=vp。,令 S=vi|v1viE(G),T=vi|vi-1vpE(G)。(S是邻接u的点的集合,T是位于邻接v的顶点的后面的顶点的集合),由G是简单图知,|S|=d(u),|T|=d(v)。,又由v1与vp不邻接有S v2,vp1以及 T v3,vp,

9、从而ST v2,v3,vp,|ST|p。,2023/10/17,离散数学,19,H图的一个充分条件,证明:|ST|p。,而 ST=。,若不然,设viST,则 存在v1v2 vi1vp vp1vi v1将是G的H回路。此与G不是H图的假设相矛盾。,u=v1,v2,vi-1,vi,vi+1,vp-1,vp=v,G+uv中的H回路,G中的H回路,2023/10/17,离散数学,20,H图的一个充分条件,定理:设G是p(3)阶简单图。如果G中任何两个不邻接的顶点u和v均满足:d(u)+d(v)p(8.2)则G是H图。证明:|S|=d(u),|T|=d(v),|ST|p,ST=,,于是,p d(v1)+

10、d(vp)=|S|+|T|=|ST|p,此为矛盾。故结论成立。,2023/10/17,离散数学,21,定理的条件不是必要的,例如下图是H图但任意两顶点度之和为4,而P=5,2023/10/17,离散数学,22,H图的又一个充分条件,推论 设G是 p(3)阶简单图,如果(G)P/2,则G是H图。证明:任取u,v V(G),由题设均有 d(u)+d(v)p/2+p/2=p 因此,由定理知,G是H图。,2023/10/17,离散数学,23,图的闭包,定义:设A是 p 阶图,对A中满足:d(u)+d(v)p(8.3)的顶点u,v,若uvE(A),则将边uv加入到A中,得到A+uv.如此反复加边,直到所

11、有满足(8.3)的点都邻接,最后所得的图称为A的闭包,记为。,由于一个图的闭包是唯一的,所以求闭包时加边的顺序可以任意。,2023/10/17,离散数学,24,求一个图的闭包,例:求右图的闭包。,v1,v2,v3,v4,v5,v6,d(v1)+d(v4)6,连接v1 和v4。,d(v3)+d(v5)6,连接v3 和v5。,d(v3)+d(v6)6,连接v3 和v6。,d(v4)+d(v6)6,连接v4 和v6。,d(v4)+d(v2)6,连接v4 和v2。,d(v5)+d(v2)6,连接v5 和v2。,d(v6)+d(v2)6,连接v6和v2。,存在A=的情形:A=Kp,A中无满足条件的边可加

12、,如图G。,G,2023/10/17,离散数学,25,H图的充要条件,引理 设G是p阶简单图,u与v是G中两个不邻接的顶点且满足:d(u)+d(v)p 于是,G是H图当且仅当G+uv是H图。证明:设G是H图,则G+uv显然也是H图。反之,假设G+uv是H图,如果其中一条H回路不含uv,则G必是H图;如果G+uv 中所有H回路均含边uv,设其中有一条回路为 C:v1v2 v3v4 vp v1,其中v1=u,v2=v。,2023/10/17,离散数学,26,H图的充要条件,证明:C:v1v2 vp v1,其中v1=u,v2=v。记;d(u)=dG+uv(u)=dG(u)+1,d(v)=dG+uv(

13、v)=dG(v)+1,则有 d(u)+d(v)=dG(u)+dG(v)+2 p+2(8.4),假设在顶点v3,v4,vp1中有r个顶点:vi1,vi2,vir与u邻接,则 dG+uv(u)=r+2(u与v2,vp邻接)。于是,顶点v必与r个顶点 vi1+1,vi2+1,vir+1(8.5)中的某个顶点 vij+1邻接。,若p4,且在G中u,v分别只与vp和v3邻接,则dG(u)+dG(v)=2p,与条件矛盾。故要么u与v3,vp-1中的r个顶点邻接,要么v与v4,vp中的r个顶点邻接,且r(p-2)/2.dG(u)=r+1,dG(v)=r+1 dG(u)+dG(v)=2r+2p,故r(p-2)

14、/2,2023/10/17,离散数学,27,H图的充要条件,证明:顶点v必与(8.5)中某顶点vij+1相邻接。,如果v不与(8.5)中的任何顶点邻接,则有 dG+uv(v)(p1)r=(p1)(dG+uv(u)2)因此,dG+uv(v)+dG+uv(u)p+1,此与(8.4)矛盾。,因此,C=v1vij vij 1 v3v2vij+1 vpv1就是G的一条H回路(C 恰不包含边uv)。即G为H图。,v2(v),vp,v1,vij1,vij+1,vij,v1(u),G+uv的H回路,G的H回路,P-1是G的最大度,2023/10/17,离散数学,28,A是H图当且仅当是H图,定理:p阶简单图A

15、是H图当且仅当是H图。证明:设图A是H图,则显然也是H图。反之,设是H图,若A=,则A是H图;若A,则存在eiE(A),i=1,t,t1,使得A+e1+e2+et=。设ei=uv,由闭包的定义知,d(u)+d(v)p,且u与v在A中不邻接,因为 是H图,由引理知 et 仍是H图,反复应用该引理,可知A是H图。,2023/10/17,离散数学,29,用顶点度序列判断H图,定理:设p(3)阶简单图G的各顶点度数序列为 d1d2 dp,于是,若对任何m m,或者dpm p m,则G是H图。证明:我们将证明=Kp,从而由定理有G是H图。(由推论知Kp是H图)假设 Kp,用d(v)记中v的度数。设u和v

16、是中不邻接且度数和为最大的两个点,不妨假设d(u)d(v)。由于uv E(),因此由闭包的定义有 d(u)+d(v)p,于是d(u)p/2。取m=d(u)p/2。,2023/10/17,离散数学,30,用顶点度序列判断H图,证明:m=d(u)p/2。设为中不与v邻接的顶点数,则 d(v)=(p1),即=(p1)d(v)。而 p1 d(u)+d(v),因此,d(u)=m。即中不与v邻接的顶点数至少为m,记为:vi1,vi2,vi(m,u=vi)。其中由u的最大性不妨设d(vi1)d(vi2)d(vi)=m。由于V(G)=V(),因此G中也至少有m个顶点的度数不大于m,又因为G的度数序列以递增顺序

17、排列,所以:dm m。,2023/10/17,离散数学,31,用顶点度序列判断H图,证明:dm m。同样,设在中不与u邻接的顶点数为,于是,=(p1)d(u)=(p1)m。设这些顶点分别为vj1,vj2,vj,(v=vj),其中由v的假定可设d(vj1)d(vj2)d(vj)=d(v)pm。又m p/2,所以,m+(mp)0,即d(u)pm。从而G中共有(pm1)+1=pm个顶点的度数均小于pm,即dpmpm。这说明存在mp/2使得dm m 和dpmpm 都成立,此与已知条件矛盾,于是=Kp。定理得证.,d(v)+d(u)p,且d(u)=m,个顶点加上顶点u,2023/10/17,离散数学,3

18、2,8.3 应用,旅行推销员问题设有n个城市C1,Cn,某推销员从C1出发推销产品,每个城市都要走到一次,最后回到C1。已知每两个城市之间的距离,问怎样安排行程才能使总路程最短?等价的图论语言描述在赋权完全图中求权最小的H回路,简称为最优回路。,2023/10/17,离散数学,33,求最优回路,最优回路是可解的。最简单的方法就是穷举法,即找出KP的所有H回路,然后从中选出最小者即可。可是对n(4)个顶点的完全图,所有权可能不等的H回路共有(n1)!种,其时间复杂度为O(n!)。所以当N较大时,用穷举法求解是不可想象的。如何用较快的算法来求最优回路,是人们正在研究且尚未最终解决的问题。人们开始转

19、而求其次,即寻找一种算法能较快地求出一种较优的但不一定是最优的解。,2023/10/17,离散数学,34,逐次改进法,逐次改进法这是一种近似解法。先找赋权完全图G的一条H回路,记为 C=v1v2vnv1,如果 w(vi1vj1)+w(vivj)w(vi1vi)+w(vj1vj)(8.6)则用H回路Cij=v1v2vi1vj1vj2vi+1vivjvj+1 vn v1代替C。反复应用,直到找不出满足(8.6)式的Cij为止。,逐次改进法不一定得到最优回路。,2023/10/17,离散数学,35,图示:逐次改进法,任意一条H回路C如图所示。,v1,vj1,vj2,vi,vi+1,vi1,vj,vj

20、+1,v2,vn,现在找到w(vi1vj1)+w(vivj)w(vi1vi)+w(vj1vj),于是将C改进为Cij.,显然改进后的回路仍然是H回路且权值较低。,2023/10/17,离散数学,36,求下图的最优回路,首先选C=v1v2v3v4v5v6v1 w(C)=14+15+8+13+1+5=56,v5,v6,v1,v2,v3,v4,13,8,15,14,5,1,7,6,5,11,9,13,8,12,10,w(v2v5)+w(v1v4)w(v1v2)+w(v4v5),用C14=v1v4v3v2v5v6v1代替C.(绕过v1v2 和v4v5),w(v2v4)+w(v1v3)w(v1v4)+w

21、(v2v3),用C13=v1v3v4v2v5v6v1代替C14.(绕过v1v4 和v2v3),w(C14)=45,w(C13)=35,2023/10/17,离散数学,37,推销员问题的解的评估,我们可用Kruskal算法给出一个关于旅行员推销问题的解的下界估计式:任选赋权完全图Kn的一个顶点v,用Kruskal算法求出Kn v的最优树T,设C是最优的H回路,显然C v也是Kn v的一个生成树,因此 w(T)w(C v)设e1和e2是Kn中与v关联的边中权最小的两条,于是,w(T)+w(e1)+w(e2)w(C).这就是对w(C)的下界估计式。,2023/10/17,离散数学,38,对下图的解的评估,我们已经求出一个解 w(C13)=35,即C13=v1v3v4v2v5v6v1,现在求Gv2的最优树T。,v5,v6,v1,v2,v3,v4,13,8,15,14,5,1,7,6,5,11,9,13,8,12,10,G,可得w(T)=22,而与v2关联的边中权最小的两条为v2v5和v2v6.,所以,33=22+5+6=w(T)+w(v2v5)+w(v2v6)w(C)35,即 C13是一个比较好的近似解.,

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号