离散数学-E图和H图

第八章

E图和H图3/24/20261离散数学第1页§8.1七桥问题与E图七桥问题：有四块陆地与连结它们七座桥，问能否从这四块陆地中任意一块出发，经过每一座桥恰好一次，最终回到原地？3/24/20262离散数学第2页一笔画该问题等价于“能否一笔画出下列图？”Euler证实了，七桥问题是无解。图中：顶点表示陆地，边表示陆地之间桥。3/24/20263离散数学第3页E图定义8.1.1：设G是一个图，经过G每一条边链称为E链；闭E链称为E闭链。假如G中存在E链，称G为半E图；假如G中存在E闭链，称G为E图。下面讨论中设G是非平凡连通图。3/24/20264离散数学第4页无奇点连通图是E图引理8.1.1：连通图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作为C

∪C起、终点，于是C

∪C是G一条闭链且长度大于C长度，这与C假设矛盾。故G是E图。因G不是E图。G无奇点且C无奇点。3/24/20265离散数学第5页C’CGvGG中含闭链图示C∪C’是一条闭链图示3/24/20266离散数学第6页E图是无奇点连通图引理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中无奇点。3/24/20267离散数学第7页半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，于是C–e组成G一条E链，所以G是半E图。3/24/20268离散数学第8页哥尼斯城堡桥不是E图半E图3/24/20269离散数学第9页§8.2周游世界问题与H图周游世界问题:

用一个正十二面体二十个顶点来代表二十个城市，要求从其中任一顶点出发，沿着这个正十二面体棱走遍这二十个顶点，且每个城市只经过一次，最终回到起点。该问题等价于“能否从下列图找一条含全部顶点回路？”3/24/202610离散数学第10页H图定义8.2.1：

设G是一个图，含G每个顶点通路称为H通路；起点与终点重合H通路称为H回路；假如G中存在H回路，称G为H图；若G中存在H通路，称G为半H图；说明：H图必是半H图，反之不然。?3/24/202611离散数学第11页Herschel图该图是半H图。

因为它是一个含有奇数个顶点二分图。所以不可能有H回路。？因为二分图中回路一定是偶数条边。(定理5.5.2)3/24/202612离散数学第12页H图一个必要条件定理8.2.1假如G是一个H图，则对V(G)任何非空真子集S，均成立：(G–S)|S|(8.1)

证实：设C是GH回路(G全部顶点都在C上)，则显然有(C–S)|S|成立，其中SV(G)。因为C–S是G–S生成子图，C

–S连通分支数不比G–S少，所以：

(G–S)(C–S)|S|故(8.1)式成立。3/24/202613离散数学第13页G(H图)C(H回路）定理8.2.1证实图示3/24/202614离散数学第14页一个非H图判定取S为红色点集。|S|=5。(G–S)=6＞|S|依据定理8.2.1，此图不是H图。3/24/202615离散数学第15页注意：这只是必要条件注意定理8.2.1只是判断H图必要条件，有图即使满足条件，却不是H图。如右边Peterson图不是H图。可是它却满足定理8.2.1条件。Peterson图Peterson图是半H图而不是H图。3/24/202616离散数学第16页H图一个充分条件定理8.2.2：设G是p(3)阶简单图。假如G中任何两个不邻接顶点u和v均满足：d(u)+d(v)p(8.2)

则G是H图。证实：若满足(8.2)简单图不是H图，令G(p,q)是其中边数最多一个图。显然，G≠Kp。？因为Kp一定是H图。

设u，v是G中不邻接两个顶点。由G假设可知，G+uv是H图，且其中H回路必含uv。于是，G中存在从u到vH通路P:v1v2

vp，其中u=v1,v=vp。3/24/202617离散数学第17页H图一个充分条件证实：…H通路P:v1v2

vp，其中u=v1,v=vp。令S={vi|v1vi∈E(G)}，T={vi|vi-1vp∈E(G)}。(S是邻接u点集合，T是位于邻接v顶点后面顶点集合)由G是简单图知，|S|=d(u),|T|=d(v)。又由v1与vp不邻接有S{v2,

,vp–1}以及T{v3,

,vp}，从而S∪T{v2,v3,

,vp}，|S∪T|＜p。3/24/202618离散数学第18页H图一个充分条件证实：……|S∪T|＜p。而S∩T=。若不然，设vi∈S∩T,则存在v1v2

vi–1vpvp–1

viv1将是GH回路。此与G不是H图假设相矛盾。u=v1v2vi-1vivi+1vp-1vp=vG+uv中H回路G中H回路3/24/202619离散数学第19页H图一个充分条件定理8.2.2：设G是p(3)阶简单图。假如G中任何两个不邻接顶点u和v均满足：d(u)+d(v)p(8.2)

则G是H图。证实：……|S|=d(u),|T|=d(v)，|S∪T|＜p，S∩T=，于是p≤d(v1)+d(vp)=|S|+|T|=|S∪T|＜p，此为矛盾。故结论成立。3/24/202620离散数学第20页定理8.2.2条件不是必要例以下列图是H图但任意两顶点度之和为4,而P=53/24/202621离散数学第21页H图又一个充分条件推论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图。3/24/202622离散数学第22页图闭包定义8.2.2：设A是p阶图，对A中满足：d(u)+d(v)

p(8.3)顶点u,v,若uv

E(A),则将边uv加入到A中，得到A+uv.如此重复加边，直到全部满足(8.3)点都邻接，最终所得图称为A闭包，记为Â。因为一个图闭包是唯一，所以求闭包时加边次序能够任意。3/24/202623离散数学第23页求一个图闭包例：求右图闭包。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。G3/24/202624离散数学第24页H图充要条件引理8.2.1设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：v1v2v3v4

vp

v1,其中v1=u,v2=v。3/24/202625离散数学第25页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)+2p+2(8.4)假设在顶点v3,v4,

vp–1中有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邻接。若p≧4，且在G中u,v分别只与vp和v3邻接，则dG(u)+dG(v)=2﹤p，与条件矛盾。故要么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+2≧p,故r≧

(p-2)/2

3/24/202626离散数学第26页H图充要条件证实：…顶点v必与

(8.5)中某顶点vij+1相邻接。假如v不与(8.5)中任何顶点邻接，则有dG+uv(v)

(p–1)–r=(p–1)–(dG+uv(u)–2)所以，dG+uv(v)+dG+uv(u)p+1，此与(8.4)矛盾。所以，C

=v1vijvij–1

v3v2vij+1

vpv1就是G一条H回路(C

恰不包含边uv)。即G为H图。v2(v)vpv1vij–1vij+1vijv1(u)G+uvH回路

GH回路

P-1是G最大度3/24/202627离散数学第27页A是H图当且仅当Â是H图定理8.2.3：p阶简单图A是H图当且仅当Â是H图。证实：设图A是H图，则显然Â也是H图。反之，设Â是H图，若A=Â，则A是H图；若A≠Â，则存在ei

E(A),i=1,

,t,t

1，使得A+e1+e2+

+et=Â。设ei=uv，由闭包定义知，d(u)+d(v)

p，且u与v在A中不邻接，因为Â是H图，由引理8.2.1知–et仍是H图，重复应用该引理，可知A是H图。3/24/202628离散数学第28页用顶点度序列判断H图定理8.2.4：设p(

3)阶简单图G各顶点度数序列为d1

d2

dp，于是，若对任何m<p/2，或者dm>m，或者dp–m≧p–m，则G是H图。证实:我们将证实Ĝ=Kp，从而由定理8.2.3有G是H图。(由推论8.2.1知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。3/24/202629离散数学第29页用顶点度序列判断H图证实：……m=d

(u)<p/2。设为Ĝ中不与v邻接顶点数，则d

(v)=(p–1)–，即=(p–1)–d

(v)。而p–1

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度数序列以递增次序排列，所以：dmm。3/24/202630离散数学第30页用顶点度序列判断H图证实：……dmm。

一样，设在Ĝ中不与u邻接顶点数为，于是，=(p–1)–d’(u)=(p–1)–m。设这些顶点分别为vj1,vj2,

,vj

，(v=vj

)，其中由v假定可设d(vj1)d(vj2)

d(vj

)=d(v)<p–m。又m<p/2，所以，m+(m–p)<0，即d(u)＜p–m。从而G中共有(p–m–1)+1=p–m个顶点度数均小于p–m，即dp–m<p–m。这说明存在m＜p/2使得dmm和dp–m＜p–m都成立，此与已知条件矛盾，于是Ĝ=Kp。定理得证.∵d(v)+d(u)＜p，且d(u)=m个顶点加上顶点u3/24/202631离散数学第31页§8.3应用[旅行推销员问题]设有n个城市C1,

,Cn,某推销员从C1出发推销产品，每个城市都要走到一次，最终回到C1。已知每两个城市之间距离，问怎样安排行程才能使总旅程最短？[等价图论语言描述]在赋权完全图中求权最小H回路，简称为最优回路。3/24/202632离散数学第32页求最优回路最优回路是可解。最简单方法就是穷举法，即找出KP全部H回路，然后从中选出最小者即可。可是对n(4)个顶点完全图，全部权可能不等H回路共有(n–1)!种，其时间复杂度为O(n!)。所以当N较大时，用穷举法求解是不可想象。怎样用较快算法来求最优回路，是人们正在研究且还未最终处理问题。人们开始转而求其次，即寻找一个算法能较快地求出一个较优但不一定是最优解。3/24/202633离散数学第33页逐次改进法逐次改进法这是一个近似解法。先找赋权完全图G一条H回路，记为C=v1v2

vnv1,假如w(vi–1vj–1)+w(vivj)<w(vi–1vi)+w(vj–1vj)(8.6)

则用H回路Cij=v1v2

vi–1vj–1vj–2

vi+1vivjvj+1

vnv1代替C。重复应用，直到找不出满足(8.6)式Cij为止。逐次改进法不一定得到最优回路。3/24/202634离散数学第34页图示：逐次改进法任意一条H回路C如图所表示。v1vj–1vj–2vivi+1vi–1vjvj+1v2vn