离散数学 E图和H图

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

2、证明：设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无奇点。8/28/20225CCGvGG中含闭链图示CC是一条闭链图示8/28/20226E图是无奇点的连通图引理8.1.1：E图是无奇点的连通图。证明：设G是E图，C是G的一条E闭链。由于G连通且C是含G的每边恰一次的闭链，因此，C中的每个点都既是起点也是终点。于是，从C上的任一点u出发，每经过一个顶点v，就有两条与v关联的边出现(一进一出) 。这样，C上的每个顶点，也即G的每个顶点的度均为偶数，故G中无奇点。由引理8.1.1和8.1.1，我们有：定理8.1.1：连通图G是E图当且仅当G中无奇点。8

4、/28/20227半E图中最多有两个奇点推论8.1.1： G是半E图当且仅当G中最多有两个奇点。证明：(必要性) 设G是半E图，C是G的一条E链。除起点与终点外， C中每个顶点的度均为偶数。又因G连通，故G最多有两个奇点。 (充分性)设G最多只有两个奇点。若G无奇点，则由定理8.1.1知，G为E图，亦为半E图；若G有两个奇点，设为u和v, 则在G中加入e=uv的边，使G中无奇点。由定理8.1.1知，G+e为E图，即G+e含E闭链C，于是Ce构成G的一条E链，所以G是半E图。8/28/20228哥尼斯城堡桥不是E图半E图8/28/202298.2 周游世界问题与H图周游世界问题: 用一个正十二面

5、体的二十个顶点来代表二十个城市，要求从其中任一顶点出发，沿着这个正十二面体的棱走遍这二十个顶点，且每个城市只经过一次，最后回到起点。该问题等价于“能否从下图找一条含所有顶点的回路？”8/28/202210H图定义8.2.1： 设G是一个图，含G 的每个顶点的通路称为H通路；起点与终点重合的H通路称为H回路；如果G中存在H回路，称G为H图；若G中存在H通路，称G为半H图；说明：H图必是半H图，反之不然。?8/28/202211Herschel 图该图是半H图。 因为它是一个具有奇数个顶点的二分图。所以不可能有H回路。？因为二分图中的回路一定是偶数条边。(定理5.5.2)8/28/202212H图

6、的一个必要条件定理8.2.1 如果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)式成立。8/28/202213G(H图)C(H回路）定理8.2.1证明图示8/28/202214一个非H图的判定取S为红色点集。|S| = 5。(G S) = 6 |S|根据定理8.2.1，此图不是H图。 8/28/202215注意：这只是必要条件注意

7、定理8.2.1只是判断H图的必要条件，有的图虽然满足条件，却不是H图。如右边的Peterson图不是H图。可是它却满足定理8.2.1的条件。Peterson图Peterson图是半H图而不是H图。8/28/202216H图的一个充分条件定理8.2.2：设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中存

8、在从u到v的H通路P: v1v2vp， 其中u=v1, v=vp 。8/28/202217H图的一个充分条件证明：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。8/28/202218H图的一个充分条件证明： | ST | p。而 ST = 。 若不然，设viST

9、, 则 存在v1v2 vi1vp vp1vi v1将是G的H回路。此与G不是H图的假设相矛盾。u=v1v2vi-1vivi+1vp-1vp=vG+uv中的H回路G中的H回路8/28/202219H图的一个充分条件定理8.2.2：设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， 此为矛盾。故结论成立。8/28/202220定理8.2.2的条件不是必要的例如下

10、图是H图但任意两顶点度之和为4,而P=58/28/202221H图的又一个充分条件推论8.2.1 设G是 p (3) 阶简单图，如果(G) P/2 ,则G是H图。证明：任取u ,v V(G) ,由题设均有 d(u) + d(v) p/2 + p/2 = p 因此，由定理8.2.2知，G是H图。8/28/202222图的闭包定义8.2.2：设A是 p 阶图，对A中满足： d(u) + d(v) p (8.3) 的顶点u , v,若uvE(A) , 则将边uv加入到A中，得到A+uv .如此反复加边，直到所有满足(8.3)的点都邻接，最后所得的图称为A的闭包，记为 。由于一个图的闭包是唯一的，所以

11、求闭包时加边的顺序可以任意。8/28/202223求一个图的闭包例：求右图的闭包。v1v2v3v4v5v6d(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。G8/28/202224H图的充要条件引理8.2.1 设G是p阶简单图，u与v是G中两个不邻接的顶点

12、且满足： 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 。8/28/202225H图的充要条件证明： 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)+

13、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 8/28/20222

14、6H图的充要条件证明：顶点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)vpv1vij1vij+1vijv1(u)G+uv的H回路 G的H回路 P-1是G的最大度8/28/202227A是H图当且仅当是H图定理8.2.3：p阶简单图A是H图当且仅当是H图。证明：设图A是H图，则显然

15、也是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图，由引理8.2.1知 et 仍是H图，反复应用该引理，可知A是H图。 8/28/202228用顶点度序列判断H图定理8.2.4：设p(3)阶简单图G的各顶点度数序列为 d1d2 dp，于是，若对任何m m，或者dpm p m，则G是H图。证明: 我们将证明 =Kp，从而由定理8.2.3有G是H图。(由推论8.2.1知Kp是H图) 假设 Kp ，用d(v)

16、记中v的度数。设u和v是中不邻接且度数和为最大的两个点，不妨假设d(u) d(v)。由于uv E()，因此由闭包的定义有 d(u)+d(v)p，于是d(u)p/2。 取m=d(u) p/2。 8/28/202229用顶点度序列判断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个顶点的度数不

17、大于m，又因为G的度数序列以递增顺序排列，所以：dm m。8/28/202230用顶点度序列判断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

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

19、究且尚未最终解决的问题。人们开始转而求其次，即寻找一种算法能较快地求出一种较优的但不一定是最优的解。8/28/202233逐次改进法逐次改进法这是一种近似解法。 先找赋权完全图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为止。逐次改进法不一定得到最优回路。8/28/202234图示：逐次改进法任意一条H回路C如图所示。v1vj1vj2vivi+1vi1vjvj+1v2vn 现在找到w(vi1vj1)+w(vivj) w(vi1vi)+w(vj1vj) 于是将C改进为Cij .显然改进后的回路仍然是H回路且权值较低。8/28/202235求下图的最优回路首先选C =v1v2v3v4v5v6v1 w(C)=14+15