离散数学E图和H.ppt

《离散数学E图和H.ppt》由会员分享，可在线阅读，更多相关《离散数学E图和H.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、点，则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图(由G和C的选法)。于是G有一条E闭链C。因G连通，C和C必有公共点v,以v作为CC的起

3、、终点，于是CC是G的一条闭链且长度大于C的长度，这与C的假设矛盾。故G是E图。因G不是E图。G无奇点且C无奇点。4/20/20235离散数学CCGvGG中含闭链图示中含闭链图示CC是一条闭链图示是一条闭链图示4/20/20236离散数学E图是无奇点的连通图引理8.1.1：E图是无奇点的连通图。证明：设G是E图，C是G的一条E闭链。由于G连通且C是含G的每边恰一次的闭链，因此，C中的每个点都既是起点也是终点。于是，从C上的任一点u出发，每经过一个顶点v，就有两条与v关联的边出现(一进一出)。这样，C上的每个顶点，也即G的每个顶点的度均为偶数，故G中无奇点。由引理和8.1.1，我们有：定理定理：

4、连通图：连通图G是是E图图当且仅当当且仅当G中无奇点中无奇点。4/20/20237离散数学半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图。4/20/20238离散数学哥尼斯城堡桥不是哥尼斯城堡桥不是E图图

5、半半E图图4/20/20239离散数学8.2 周游世界问题与H图周游世界问题周游世界问题:用一个正十二面体的二十个顶点来代表二十个城市，要求从其中任一顶点出发，沿着这个正十二面体的棱走遍这二十个顶点，且每个城市只经过一次，最后回到起点。该问题等价于“能否从下图找一条含所有顶点的回路？”4/20/202310离散数学H图定义：设G是一个图，含G 的每个顶点的通路称为H通路；起点与终点重合的H通路称为H回路；如果G中存在H回路，称G为H图；若G中存在H通路，称G为半H图；说明：H图必是半H图，反之不然。?4/20/202311离散数学Herschel 图该图是半H图。因为它是一个具有奇数个顶点的二

6、分图。所以不可能有H回路。？因为二分图中的回路一定是偶数条边。(定理5.5.2)4/20/202312离散数学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)式成立。4/20/202313离散数学G(H图图)C(H回路）回路）定理证明图示定理证明图示4/20/202314离散数学一个非H图的判定取S为红色点集。|S|=5。(

7、G S)=6|S|根据定理，此图不是H图。4/20/202315离散数学注意：这只是必要条件注意定理只是判断H图的必要条件，有的图虽然满足条件，却不是H图。如右边的Peterson图不是H图。可是它却满足定理的条件。Peterson图Peterson图是半H图而不是H图。4/20/202316离散数学H图的一个充分条件定理定理：设G是p(3)阶简单图。如果G中任何两个不邻接的顶点u和v均满足：d(u)+d(v)p (8.2)则G是H图。证明：若满足(8.2)的简单图不是H图，令G(p,q)是其中边数最多的一个图。显然，GKp。？因为Kp 一定是H图。设u，v是G 中不邻接的两个顶点。由G的假设

8、可知，G+uv是H图，且其中的H回路必含uv。于是，G中存在从u到v的H通路P:v1v2vp，其中u=v1,v=vp。4/20/202317离散数学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，从而ST v2,v3,vp，|ST|p。4/20/202318离散数学H图的一个充分条件证明：|ST|p。而 ST=。若不然，设viST,则

9、 存在v1v2 vi1vp vp1vi v1将是G的H回路。此与G不是H图的假设相矛盾。u=v1v2vi-1vivi+1vp-1vp=vG+uv中的H回路G中的H回路4/20/202319离散数学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)+d(vp)=|S|+|T|=|ST|p，此为矛盾。故结论成立。4/20/202320离散数学定理的条件不是必要的定理的条件不是必要的例如下图是H图但任意两顶点度之和为4,而P=54/

10、20/202321离散数学H图的又一个充分条件推论推论 设G是 p(3)阶简单图，如果(G)P/2,则G是H图。证明：任取u,v V(G),由题设均有 d(u)+d(v)p/2+p/2=p 因此，由定理知，G是H图。4/20/202322离散数学图的闭包定义：设A是 p 阶图，对A中满足：d(u)+d(v)p (8.3)的顶点u,v,若uvE(A),则将边uv加入到A中，得到A+uv.如此反复加边，直到所有满足(8.3)的点都邻接，最后所得的图称为A的闭包，记为 。由于一个图的闭包是唯一的，所以求闭包时加边的顺序可以任意。4/20/202323离散数学求一个图的闭包例：求右图的闭包。v1v2v

11、3v4v5v6d(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中无满足条件的边可加,如图G。G4/20/202324离散数学H图的充要条件引理引理 设G是p阶简单图，u与v是G中两个不邻接的顶点且满足：d(u)+d(v)p 于是，G是H图当且仅当G+uv是H图。证明证明：设G是H图，则G+uv显然也是H图。反之，

12、假设G+uv是H图，如果其中一条H回路不含uv，则G必是H图；如果G+uv 中所有H回路均含边uv，设其中有一条回路为 C：v1v2 v3v4 vp v1 ,其中v1=u,v2=v。4/20/202325离散数学H图的充要条件证明：C：v1v2 vp v1，其中v1=u，v2=v。记；d(u)=dG+uv(u)=dG(u)+1，d(v)=dG+uv(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个顶点 v

13、i1+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)/2 4/20/202326离散数学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+

14、1，此与(8.4)矛盾。因此，C =v1vij vij 1 v3v2vij+1 vpv1就是G的一条H回路(C 恰不包含边uv)。即G为H图。v2(v)vpv1vij1vij+1vijv1(u)G+uv的H回路 G的H回路 P-1是G的最大度4/20/202327离散数学A是H图当且仅当是H图定理：p阶简单图A是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图，反复应用

15、该引理，可知A是H图。4/20/202328离散数学用顶点度序列判断H图定理：设p(3)阶简单图G的各顶点度数序列为 d1d2 dp，于是，若对任何m m，或者dpm p m，则G是H图。证明:我们将证明=Kp，从而由定理有G是H图。(由推论知Kp是H图)假设 Kp，用d(v)记中v的度数。设u和v是中不邻接且度数和为最大的两个点，不妨假设d(u)d(v)。由于uv E()，因此由闭包的定义有 d(u)+d(v)p，于是d(u)p/2。取m=d(u)p/2。4/20/202329离散数学用顶点度序列判断H图证明：m=d(u)p/2。设为中不与v邻接的顶点数，则 d(v)=(p1)，即=(p1)

16、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的度数序列以递增顺序排列，所以：dm m。4/20/202330离散数学用顶点度序列判断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)

17、0，即d(u)pm。从而G中共有(pm1)+1=pm个顶点的度数均小于pm，即dpmpm。这说明存在mp/2使得dm m 和dpmpm 都成立，此与已知条件矛盾，于是=Kp。定理得证.d(v)+d(u)p，且d(u)=m个顶点加上顶点u4/20/202331离散数学8.3 应用旅行推销员问题设有n个城市C1,Cn,某推销员从C1出发推销产品，每个城市都要走到一次，最后回到C1。已知每两个城市之间的距离，问怎样安排行程才能使总路程最短？等价的图论语言描述在赋权完全图中求权最小的H回路，简称为最优回路。4/20/202332离散数学求最优回路最优回路是可解的。最简单的方法就是穷举法，即找出KP的所

18、有H回路，然后从中选出最小者即可。可是对n(4)个顶点的完全图，所有权可能不等的H回路共有(n1)!种，其时间复杂度为O(n!)。所以当N较大时，用穷举法求解是不可想象的。如何用较快的算法来求最优回路，是人们正在研究且尚未最终解决的问题。人们开始转而求其次，即寻找一种算法能较快地求出一种较优的但不一定是最优的解。4/20/202333离散数学逐次改进法逐次改进法这是一种近似解法。先找赋权完全图G的一条H回路，记为 C=v1v2vnv1,如果 w(vi1vj1)+w(vivj)w(vi1vi)+w(vj1vj)(8.6)则用H回路Cij=v1v2vi1vj1vj2vi+1vivjvj+1 vn

19、v1代替C。反复应用，直到找不出满足(8.6)式的Cij为止。逐次改进法不一定得到最优回路。4/20/202334离散数学图示：逐次改进法任意一条H回路C如图所示。v1vj1vj2vivi+1vi1vjvj+1v2vn 现在找到w(vi1vj1)+w(vivj)w(vi1vi)+w(vj1vj)于是将C改进为Cij.显然改进后的回路仍然是H回路且权值较低。4/20/202335离散数学求下图的最优回路首先选C=v1v2v3v4v5v6v1 w(C)=14+15+8+13+1+5=56v5v6v1v2v3v41381514517651191381210 w(v2v5)+w(v1v4)w(v1v2

20、)+w(v4v5)用C14=v1v4v3v2v5v6v1代替C.(绕过v1v2 和v4v5)w(v2v4)+w(v1v3)w(v1v4)+w(v2v3)用C13=v1v3v4v2v5v6v1代替C14.(绕过v1v4 和v2v3)w(C14)=45w(C13)=354/20/202336离散数学推销员问题的解的评估我们可用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)的下界估计式。4/20/202337离散数学对下图的解的评估我们已经求出一个解 w(C13)=35，即C13=v1v3v4v2v5v6v1 ，现在求Gv2的最优树T。v5v6v1v2v3v41381514517651191381210G 可得w(T)=22 而与v2关联的边中权最小的两条为v2v5和v2v6 .所以，33=22+5+6=w(T)+w(v2v5)+w(v2v6)w(C)35,即 C13是一个比较好的近似解.4/20/202338离散数学