离散数学E图和H.ppt
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是非平凡的连通图。,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图(由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上的每个顶点，也即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/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,离散数学,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回路）,定理证明图示,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(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，从而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)+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.如此反复加边，直到所有满足(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中无满足条件的边可加,如图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(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)/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是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是中不邻接且度数和为最大的两个点，不妨假设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的度数序列以递增顺序排列，所以：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,离散数学,32,8.3 应用,旅行推销员问题设有n个城市C1,Cn,某推销员从C1出发推销产品，每个城市都要走到一次，最后回到C1。已知每两个城市之间的距离，问怎样安排行程才能使总路程最短？等价的图论语言描述在赋权完全图中求权最小的H回路，简称为最优回路。,2023/10/17,离散数学,33,求最优回路,最优回路是可解的。最简单的方法就是穷举法，即找出KP的所有H回路，然后从中选出最小者即可。可是对n(4)个顶点的完全图，所有权可能不等的H回路共有(n1)!种，其时间复杂度为O(n!)。所以当N较大时，用穷举法求解是不可想象的。如何用较快的算法来求最优回路，是人们正在研究且尚未最终解决的问题。人们开始转而求其次，即寻找一种算法能较快地求出一种较优的但不一定是最优的解。,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+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(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是一个比较好的近似解.,
