图论及其应用第4章

第四章

欧拉图与哈密尔顿图§4.1欧拉图

定义1设G是无孤立点的图。经过G的每条边的(闭)迹被称为Euler(闭)迹，存在Euler闭迹的图称为欧拉图,简称E图。Euler闭迹又称为Euler回路。

上图中，（a）,（f）是欧拉图；（b）,(d)有欧拉迹但不是欧拉图;（c）和（e）无欧拉迹。（a）（f）（e）（d）（c）（b）例1定理1下列陈述对于一个连通图G是等价的：

(1)

G是欧拉图。(2)

G的每个点的度是偶数。(3)

G的边集能划分为圈。

令C是G中的一条欧拉闭迹。C中任一个给定的点在C中每出现一次恰关联两条边，因为G的每条边在C中仅出现一次，所以该点的度应为该点在C中出现的次数乘以2,是一个偶数。证明

(1)(2)因为G连通非平凡，故每个点的度至少是2，所以G含有一个圈Z。移去Z的各条边产生一个生成子图G1，其中每个点的度仍然是偶数。若G1没有边，则（3）已经成立；否则，重复应用这种论证于G1，产生一个图G2，其中所有的点的度仍然是偶数，等等。当该过程终止于空图Gn时，我们就得到了将G的边分成若干圈的一个划分。(2)(3):

(3)(1):

令Z1是这个划分的一个圈。若G仅由Z1组成，则G显然是欧拉图。否则，有另外一个圈Z2与Z1有一个公共点v，从v开始并且由Z1和Z2相连组成的通道是含有这两个圈中各条边的一条闭迹。继续这个过程，我们可以构成一条含有G的所有边的闭迹；从而G是欧拉图。推论连通图G有Euler迹当且仅当G最多有两个奇点。证明定理1表明：G有Euler闭迹当且仅当G有零个奇点。若连通图G有Euler非闭迹C，并设点u和v分别是C的起点和终点。记在C中添加一条连接u和v的新边e后所得到的图为C+e。显然，C+e是一条Euler闭迹,则由已证结论，C+e有零个奇点,从而C,即G有两个奇点。反之，设G是恰有两个奇点u和v的连通图。在u和v间添加新边e得图G+e,则G+e没有奇点。由已证结论,G+e有Euler闭迹,从而G有Euler迹。综上,推论结论成立.由以上讨论我们还有：1.

图G有欧拉迹G能“一笔画”G连通且G中奇点数不超过22.

若奇点数为0,则一笔画与起点无关;若奇点数为2,则一笔画的起点与终点均为奇点.3.

在有向图（即每条边均为有向边的图，其系统讨论将在第九章进行）中有类似结论.有向图D中，以一点u为起点的弧（即有向边）的数目称为u的出度，记为

dD+(u)；以一点u为终点的弧的数目称为u的入度，记为dD

-(u)。定理3下列陈述对于一个连通有向图D是等价的：（1）

D是欧拉有向图。（2）D的每个点的入度等于出度。（3）D的弧集可划分为有向圈。例

欧拉有向图:§4.2高效率计算机鼓轮的设计计算机中旋转鼓轮的位置是借助于鼓轮表面上的一系列电触点所产生的二元信号来识别的。这个表面分为m段，每段由绝缘体或导体材料组成。绝缘段给出信号0（没有电流），导通段给出信号1（有电流）。例如，图中，鼓轮的位置由四个触点给出读数0010。如果鼓轮沿顺时针方向旋转一段，读数将是1001。0010010触点01.S的周期:

S中对任何正整数n,具有an+τ

=an的最小的正整数τ.

问题为提高效率,我们期望鼓轮每旋转一周(m段)读出的由k位组成的m个数应是互不相同的.进一步,对故定的k,最大的m应是多少?如何构造这样的鼓轮?涉及该问题的数学模型的几个概念:设S=(a1,a2,…,an,…)为（0,1）无限序列.

2.S的k-部分序列S1,S2,…:

是由S中相继k个元素组成的k元组作为元素组成的序列,即S1=(a1,a2,…,ak),S2=(a2,a3,…,ak+1),…3.

德·布鲁因（DeBruijn）序列:指对于固定的正整数k的具有最大τ的一个（0,1）周期序列S，它使得S的k-部分序列S1,S2,…,Sτ

均不相同。易知,不同的k元(0,1)序列Si

恰有2k个，即τ=2k上问题的数学模型:对于固定的k，求德·布鲁因序列S.例1设k=3，则τ=23=8，这8个不同的3-部分序列为:（000）(001)(010)(101)(011)(111)(110)(100)相应的德·布鲁因序列是S=(0001011100010111……)把这个序列的前8位排成一个圆圈，与所求的鼓轮相对应，就得到下图的鼓轮设计。1101100德·布鲁因序列的构造:步骤1

构造一个有向图H:

它的点是2k-1个不同的有序(k-1)-元组。对点v=(b1,b2,…,bk-1)，用两条弧分别将v联到点v1=(b2,b3,…bk-1,0)和v2.=(b2,b3,…,bk-1,1),得有向边〈v,v1〉和〈v,v2〉。当然，上述的点v=(b1,b2,…,bk-1)

也有两条由点u1和u2的指向v的边联接，其中u1=(0,b1,b2,…,bk-2)，u2=(1,b1,b2,…,bk-2)。说明：(1)

H的每一点v，有d+(v)

=d-(v)=2，且是连通的从而H是欧拉有向图,称为德·布鲁因图。(2)

H有2k条弧，若以每一条由点（b1,b2,…,bk-1）到点（b2,b3,…,bk）的弧a代表一个k-元组（b1,b2,…,bk），便可得2k个不同的k-元组。步骤2求H的欧拉有向闭迹,由此得k-部分序列S1,S2,…,Sτ

和相应的德·布鲁因序列S.

例下图为k=4(τ=24=16)的德·布鲁因图,

相应的欧拉有向闭迹及相应的德·布鲁因序列.000100010001101110011111abcdefgjklmnipqh弧a=(0000)b=(0001)c=(0010)d=(0101)e=(1010)f=(0100)g=(1001)h=(0011)i=(0110)j=(1101)k=(1011)l=(0111)m=(1111)n=(1110)p=(1100)q=(1000)(abcdefghijklmnpq……)=(0000101001101111……)欧拉闭迹和相应的德·布鲁因序列该例有16个解，其中的一些为(abcdkijefjhlmnpq……)=(0000101101001111……)(abcdkipghlmjefq……)=(0000101100111101……)(abcfgijedklmnpq……)=(0000100110101111……)(abhijklmnpgcdefq……)=(0000110111100101……)(abhijedklmnpgcfq……)=(0000110101111001……)(abhijefgcdklmnpq……)=(0000110100101111……)(abhipgcdklmnjefq……)=(0000110010111101……)§4.3中国邮递员问题

算法的思想从任一点出发按下法来描画一条边不重复的迹，使在每一步中未描画的子图的割边仅当没有别的边可选择时才被描画。Euler图中确定Euler回路的Fleury算法Fleury算法1.

任意选取一个顶点v0，置w0=v0。2.

假设迹wi=v0e1v1…eivi已经选定，那么按下述方法从E\{e1,e2,…,ei}中选取边ei+1：使(1)ei+1和vi相关联；(2)除非没有别的边可选择，否则ei+1不是G=G-{e1,e2,…,ei}

的割边。3.

当第2步不能再执行时，算法停止。例例：某博物馆的一层布置如下图，其中边代表走廊，结点e是入口，结点g是礼品店，通过g我们可以离开博物馆。请找出从博物馆e进入，经过每个走廊恰好一次，最后从g处离开的路线。afedcbihgj解：图中只有两个奇度顶点e和g,因此存在起点为e,终点为g的欧拉迹。为了在G中求出一条起点为e，终点为g的欧拉迹，在e和g间添加一条平行边mafedcbihgjm用Fleury算法求出欧拉环游为：

emgcfabchbdhgdjiejge所以，解为：egjeijdghdbhcbafcg例证明：若G有2k>0个奇数顶点，则存在k条边不重的迹Q1,Q2,…,Qk，使得：证明：不失一般性，只就G是连通图进行证明。设G=(n,m)是连通图。令vl,v2,…,vk,vk+1,…,v2k是G的所有奇度点。在vi与vi+k间连新边ei得图G*(1≦i≦k)，则G*是欧拉图。因此，由Fleury算法得欧拉回路C。在C中删去ei(1≦i≦k)得k条边不重的迹Qi

（1≦i≦k):问题：邮递员从邮局出发，递送邮件，然后返回邮局，要求辖区每条街至少走一遍且走过的总路程最短，应如何选择路线？图论模型：在一个连通的具有非负权的赋权图G中找一条包含每条边（允许重复）且边权之和最小的闭途径，称之为最优环游。对该问题

(1)

若图G是一个欧拉图，则找出G的欧拉回路即可。(2)

对一般图，其解法为：添加重复边以使G成为欧拉图G*，并使添加的重复边的边权之和为最小，再求G*的欧拉回路。(3)

对恰有两个度数为奇的点的图G，可以证明：需要重复的边正好是从一个奇度点到另一个奇度点的最短路上的边，即问题为欧拉问题与最短路问题的综合。说明:

(1)

若G是Euler图，则G的任何Euler回路都是最优环游.(2)

若G不是Euler图，用添加重复边以使G成为欧拉图G*的方法时，添加的重复边具有的特征由定理3给出.定理3

若W是图G中一条包含所有边的闭途径，则W具有最小权值的充要条件是：(1)

G的每一条边在W中最多重复一次；(2)对于G的每个圈上的边来说，在W中重复的边的总权值不超过该圈非重复边总权值。证明：“必要性”首先，设G是连通非欧拉图，u与v是G的两个奇度顶点，把连接u与v的路上的边改为2重边，则路中的点的度数奇偶性其次，对G1作修改：如果在G1中，边e重复数大于2，则在G1中删掉2条重复的e边后，所得之图仍然是包含G的欧拉图。在G1中，对每组平行边都做上面的处理，最后得到一个重复边数最多为1的包含G的欧拉图G2。没有改变，仍然为偶数，但u与v的度数由奇数变成了偶数。如果对G中每对奇度点都如此处理，则最终得到的图为欧拉图。设该图为G1。这说明，若W是包含G的所有边的欧拉回路，则G中每条边至多在W里出现两次。这就证明了(1)。又设C是G2中任意一个圈，在该圈中，如果重复边的总权值超过该圈中非重复边总权值，那么可以把该圈中平行边改为非平行边，而把非平行边改为平行边，如此修改，得到的图仍然是包含G的欧拉图，但对应的欧拉环游长度减小了。这就是说，只要对G2的每个圈都作上面的修改，最后得到的图仍然为包含G的欧拉图，而最后的图正好满足(2)。“充分性”只需证明：任何两条包含G中所有边的闭途径W1与W2,如果满足定理的两个条件，则它们有相同的总权值。设Y1与Y2分别表示W1与W2中重复出现的边集合。我们先证明：对于任意一个圈C*,如果满足：则有：令：Y=(Y1-Y2)∪(Y2-Y1)断言1：G[Y]的每个顶点度数必然为偶数。首先：对于G中任意点v,如果dG

(v)是奇数，那么Y1与Y2中与v关联的边数均为奇数；如果dG

(v)是偶数，那么Y1与Y2中与v关联的边数均为偶数。其次，设Y1与Y2中与v关联的边数分别为y1与y2,其中相同的边数为y0，那么，Y中与v关联的边数为：

所以，Y中与v关联的边数为偶数，说明

G[Y]的每个顶点度数必然为偶数。由于G[Y]的每个顶点度数为偶数。所以，它的每个分支是欧拉图。因此，G[Y]可以作圈分解。设断言2：事实上，因为：又因为：所以：由断言2很容易得到：所以：又因为：所以：

注:定理的证明过程实际上给出了求中国邮路问题的方法。非Euler图求最优环游的方法(1)

用每条边最多添一条边的方法任意添一些重复边使图G

成为一个欧拉多重图G’。(2)

考查G’的圈，若存在圈C，其中重复边的总权值大于该圈权值的一半，则在圈C上交换重复边和不重复边得图G”。重复这个过程，直到得到一个图G*，使得图G*中每个圈上重复边的总权值不大于该圈权值的一半。(3)用Fleury算法求G*的Euler回路。(a)(b)例图G如图(a)所示(各边权为1),它有10个奇度点。任意添一些边得到一个欧拉多重图(b)。(b)中有色圈中重复边的数目为5，大于圈长8的一半，在这个圈上交换重复边和不重复边，得到(c)。(c)中每一个圈中重复边的数目均不大于圈长的一半。从而，由(c)中每条欧拉闭迹对应原图一条闭通道，它含有所有的边且具有最短的长度。(c)例

求包含下图G的一个最优欧拉环游。v1v2v3v4v5v6v713225233354G解：v1v2v3v4v5v6v713225233354Gv1v2v3v4v5v6v713225233354v2v3v4v5v6v713225233354v1v2v3v4v5v6v713225233354v1例如果一个非负权的边赋权图G中只有两个奇度顶点u与v，设计一个求其最优欧拉环游的算法。解：(1)、在u与v间求出一条最短路P;(最短路算法)(2)、在最短路P上，给每条边添加一条平行边得到G的欧拉母图G*;(3)、在G的欧拉母图G*中用Fleury算法求出一条欧拉回路。算法：证明：设u与v是G的两个奇度顶点，G*是G的任意一个欧拉母图。考虑G*[E*-E],显然它只有两个奇数顶点u与v,当然它们必须在G*[E*-E]的同一个分支中，因此，存在(u,v)路P*。

所以，例：求出下图的一条最优欧拉环游。y222211u43365wxvGzy222211u43365wxvGz最优欧拉环游：xuywvzwyxuwvxzyx§4.4哈密尔顿图经过图中每个点仅一次的路（圈）称为的Hamilton路(圈)，存在Hamilton圈的图称为哈密尔顿图，简称H图。Hamilton路也简称H路。只有哈密尔顿路，但不是哈密尔顿图哈密尔顿图无哈密尔顿路例如证明

设C是G中一条哈密尔顿圈。任取

V中非空子集S，因

C是G的哈密尔顿圈含G的所有点，故S也是子图

C的非空子集。由点不重复的圈的特性知任意删去C中|S|个点，最多将C分为|S|“段”

，即

ω

(C-S)≤|S|（*）

而C是G的生成子图，又有

ω

(G-S)≤ω

(C-S

)所以

ω

(G-S

)≤|S

|定理5

若G是H图，则对于V的每个非空真子集S，均有

ω(G-S)≤|S|(4.1)

依据定理4可判断下图（a）不是哈密尔顿图，这是因若取S

={v}，有

ω

(G-S

)=2>1=|S

|（a）v

可验证彼得森图（上图（b）所示）不是哈密尔顿图，但满足式（*）式。这表明定理5给出的条件只是图G是哈密尔顿图的必要条件而不是充分条件。

(b)引理1设G是简单图，u和v是G中不邻接的顶点，且适合

d(u)+d(v)≥n

则G是H图的充要条件是G+uv为H图。证明

必要性：若G是H图，则显然G+uv也是H图。充分性：设G+uv是H图。如果G+uv的H圈不含边uv，则由

G=(G+uv)-uv知G中有一个H圈。如果G+uv的H圈中含有uv

边，不妨设H圈为

C=uvv3v4…vnu。当G1=G+uv时，有故有若有i(3≤i≤n-1)使uadj

vi，v

adjvi+1(如图)，则G中有一个H圈C1=uvivi-1…v3vvi+1vi+2…vnu即G是H图vi-1vi-2

v3

vivi+1

vi+2

vi+3vu

vn若不存在这样的i，因

v3,v4,…,vn-1中有-2个点与u邻接，故v4,v5,…,vn中就有-2个点不能与v邻接。从而这与已知条件相矛盾。故在假设的dG(u)+dG(v)≥n的条件下，一定存在上述图示那样的i，使G中存在一个H

圈，所以G为H图。(v)≤(n-1)–(-2)=n-dG(u)dG(v)<d(u)+d(v)<n定义1在n阶简单图G中，若对d(u)+d(v)≥n的任何一对点u和v均有u

adj

v，则称G是闭图。引理2

若G1和G2是同一个点集V的两个闭图，则G=G1∩G2是闭图。由G1和G2是闭图，u和v在G1和G2中都邻接，故u和v在G中也邻接，从而G是闭图。证明因对任何w∈V，有

dG(w)≤,dG(w)≤,可得故由注:

闭图的并不一定是闭图。例如

G1G2G1∪G2

G1∩G2定义2若一个与G有相同点集的闭图，使G

，且对异于的任何图H，若有G

H

，则H不是闭图，则称是G的闭包，即G的闭包是包含G的极小闭图。图的闭包的构造方法:

将图中度数之和至少是图的顶点个数的非邻接顶点对递归地连接起来，直到不再有这样的顶点对存在时为止。例下图给出了6个顶点的图的闭包的构造过程。故唯一。引理3图G的闭包是唯一的。G

∩证明如果和是G的两个闭包。则由G

G,得而∩是闭图(引理2),且

∩,∩,故由闭包的定义∩证明如果G是H图，显然，是H图。定理7(Bondy1969)一个简单图G是H图的充要条件为它的闭包是H图。如果是H图，当G=时，结论成立；当G≠时，必相继存在若干条边，使得G+e1+e2+…+ek

=其中ei

G，(i

=1,2,…,k)。根据闭包的定义，对中边ek的端点u和v有因为G+e1+e2+…+ek是H图，由引理1知G+e1+e2+…+ek-1是H图，反复应用引理1可知G是H图。注:一个图G的闭包不一定是完全图。比如下图中（a）、（b）两个均不是完全图，但它们却是自己的闭包。（a）（b）推论1设是n≥3的简单图。若是完全图，则G是H图。

推论2

（1）设G是n≥3的简单图。若G中每个点的度d(v)≥n/2，则G是H图。(由此得定理6)

（2）设G是n≥3的简单图，若G中任何两个不邻接的点u和v均有