第4,5章E,H图,匹配103.ppt

《第4,5章E,H图,匹配103.ppt》由会员分享，可在线阅读，更多相关《第4,5章E,H图,匹配103.ppt（92页珍藏版）》请在优知文库上搜索。

1、第四章第四章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图 4.1 欧拉图欧拉图 定义定义1 设设G 是无孤立点的图。经过是无孤立点的图。经过G的每条边的每条边的的(闭闭)迹被称为迹被称为 Euler(闭闭)迹迹，存在，存在Euler闭迹闭迹的的图称为图称为欧拉图欧拉图,简称简称E 图。图。Euler闭迹又称为闭迹又称为Euler环游。环游。上图中，（上图中，（a）,（f）是欧拉图；（是欧拉图；（b）,(d)有欧拉迹但有欧拉迹但不是欧拉图不是欧拉图;（c）和（和（e）无欧拉迹。无欧拉迹。（a）（f）（e）（d）（c）（b）例例1 定理定理1 1 下列陈述对于一个连通图下列陈述对于一个连通图G是等价的：

2、是等价的：(1)G是欧拉图。是欧拉图。(2)G的每个点的度是偶数。的每个点的度是偶数。(3)G的边集能划分为圈。的边集能划分为圈。令令C是是G中的一条欧拉闭迹。中的一条欧拉闭迹。C中任一个给定的中任一个给定的点在点在C中每出现一次恰关联两条边，因为中每出现一次恰关联两条边，因为G的每条的每条边在边在C中仅出现一次，所以该点的度应为该点在中仅出现一次，所以该点的度应为该点在C中出现的次数乘以中出现的次数乘以2,是一个偶数。是一个偶数。证明证明 (1)(2)因为因为G连通非平凡，故每个点的度至少是连通非平凡，故每个点的度至少是2，所以所以G含有一个圈含有一个圈Z(见习题见习题1,12)。移去。移去

3、Z的各条边产生一个的各条边产生一个生成子图生成子图G1，其中每个点的度仍然是偶数。若其中每个点的度仍然是偶数。若G1没有边，没有边，则（则（3）已经成立；否则，重复应用这种论证于）已经成立；否则，重复应用这种论证于G1，产生一产生一个图个图G2，其中所有的点的度仍然是偶数，等等。当该过程其中所有的点的度仍然是偶数，等等。当该过程终止于空图终止于空图Gn时，我们就得到了将时，我们就得到了将G的边分成若干圈的一个的边分成若干圈的一个划分。划分。(2)(3):(3)(1):令令Z1是这个划分的一个圈。若是这个划分的一个圈。若G仅由仅由Z1组组成，则成，则G显然是欧拉图。否则，有另外一个圈显然是欧拉图

4、。否则，有另外一个圈Z2与与Z1有一有一个公共点个公共点v，从从v开始并且由开始并且由Z1和和Z2相连组成的通道是含有相连组成的通道是含有这两个圈中各条边的一条闭迹。继续这个过程，我们可以这两个圈中各条边的一条闭迹。继续这个过程，我们可以构成一条含有构成一条含有G的所有边的闭迹；从而的所有边的闭迹；从而G是欧拉图。是欧拉图。推论推论 连通图连通图G 有有Euler迹当且仅当迹当且仅当G最多有两个奇点。最多有两个奇点。证明证明 定理定理1表明：表明：G有有Euler闭闭迹当且仅当迹当且仅当G有有零零个奇点。个奇点。若连通图若连通图G有有Euler非闭迹非闭迹C,并设点并设点u和和v分别是分别是C

5、的起点的起点和终点和终点.记在记在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迹。迹。综上综上,推论结论成立推论结论成立.由以上讨论我们还有：由以上讨论我们

6、还有：1.图图 G 有欧拉迹有欧拉迹G 能能“一笔画一笔画”G 连通且连通且 G 中奇点数不超过中奇点数不超过22.若奇点数为若奇点数为0,则一笔画与起点无关则一笔画与起点无关;若奇点若奇点 数为数为2,则一笔画的起点与终点均为奇点则一笔画的起点与终点均为奇点.3.在有向图（即每条边均为有向边的图，其系在有向图（即每条边均为有向边的图，其系统讨论将在第九章进行）中有类似结论统讨论将在第九章进行）中有类似结论.有向图有向图D中，以一点中，以一点u为起点的弧（即有向边）的数为起点的弧（即有向边）的数目称为目称为u的出度，记为的出度，记为 dD+(u)；以一点以一点u为终点的弧的为终点的弧的数目称为

7、数目称为u的入度，记为的入度，记为dD-(u)。定理定理3 下列陈述对于一个连通有向图下列陈述对于一个连通有向图D是等价的：是等价的：（1）D是欧拉有向图。是欧拉有向图。（2）D的每个点的入度等于出度。的每个点的入度等于出度。（3）D的弧集可划分为有向圈。的弧集可划分为有向圈。例例 欧拉有向图欧拉有向图:4.2 高效率计算机鼓轮的设计高效率计算机鼓轮的设计 计算机中旋转鼓轮的位置是借助于鼓轮表面上的一计算机中旋转鼓轮的位置是借助于鼓轮表面上的一系列电触点所产生的二元信号来识别的。这个表面分系列电触点所产生的二元信号来识别的。这个表面分为为m段，每段由绝缘体或导体材料组成。绝缘段给出段，每段由绝

8、缘体或导体材料组成。绝缘段给出信号信号0（没有电流），导通段给出信号（没有电流），导通段给出信号1（有电流）。（有电流）。0010010触点触点例如，例如，图中，鼓轮的位置图中，鼓轮的位置由四个触点给出读数（由四个触点给出读数（0010）。如果鼓轮沿顺时）。如果鼓轮沿顺时针方向旋转一段，读数将针方向旋转一段，读数将是（是（1001）。）。1.S的周期的周期:S中对任何正整数中对任何正整数n,具有具有 an+=an的最小的的最小的正整数正整数.问题问题 为提高效率为提高效率,我们期望鼓轮每旋转一周我们期望鼓轮每旋转一周(m段段)读出的读出的由由k位组成的位组成的m个数应是个数应是互不相同互不相同

9、的的.进一步进一步,对故定的对故定的k,最最大的大的m应是多少应是多少?如何构造这样的鼓轮如何构造这样的鼓轮?涉及该问题的数学模型的几个概念涉及该问题的数学模型的几个概念:设设 S=(a1,a2,a n,)为（为（0,1）无限序列）无限序列.2.S的的k-部分序列部分序列S1,S2,:是由是由S中相继中相继k个元素个元素组成的组成的k元组作为元素组成的序列元组作为元素组成的序列,即即 S1=(a1,a2,ak),S2=(a2,a3,ak+1),3.德德 布鲁因（布鲁因（De，Bruijn）序列序列:指对于固定的正整指对于固定的正整数数k的具有最大的具有最大的一个（的一个（0,1）周期序列）周期

10、序列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位排成一个圆圈，与所求的鼓轮相对位排成一个圆圈，

11、与所求的鼓轮相对应，就得到下图的鼓轮设计。应，就得到下图的鼓轮设计。0 11 01 100德德 布鲁因序列的构造布鲁因序列的构造:步骤步骤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,b

12、2,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.例例

13、下图为下图为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)欧拉闭迹和相应的欧拉闭迹和相应的德德 布鲁因

14、序列布鲁因序列该例有16个解，其中的一些为(abcdkijefjhlmnpq)=(0000101101001111)(abcdkipghlmjefq)=(0000101100111101)(abcfgijedklmnpq)=(0000100110101111)(abhijklmnpgcdefq)=(0000110111100101)(abhijedklmnpgcfq)=(0000110101111001)(abhijefgcdklmnpq)=(0000110100101111)(abhipgcdklmnjefq)=(0000110010111101)4.3中国邮路问题中国邮路问题 问题问题：邮

15、递员从邮局出发，递送邮件，然后返回邮递员从邮局出发，递送邮件，然后返回邮局，要求辖区每条街至少走一遍且走过的总路邮局，要求辖区每条街至少走一遍且走过的总路程最短，应如何选择路线？程最短，应如何选择路线？图论模型：图论模型：在一个连通的具有非负权的赋权图在一个连通的具有非负权的赋权图G中找中找一条包含每条边（允许重复）且边权之和最小的闭途径一条包含每条边（允许重复）且边权之和最小的闭途径.称之为称之为最优环游最优环游。对该问题对该问题 (1)若图若图G是一个欧拉图，则找出是一个欧拉图，则找出G的欧拉回路即可的欧拉回路即可。(2)对一般图，其解法为：添加重复边以使对一般图，其解法为：添加重复边以使

16、G成为欧拉成为欧拉图图G*，并使添加的重复边的边权之和为最小，再求并使添加的重复边的边权之和为最小，再求G*的的欧拉回路。欧拉回路。(3)对恰有两个度数为奇的点的图对恰有两个度数为奇的点的图G，可证：需要重可证：需要重复的边正好是从一个奇度点到另一个奇度点的最短路复的边正好是从一个奇度点到另一个奇度点的最短路上的边，即问题为欧拉问题与最短路问题的综合。上的边，即问题为欧拉问题与最短路问题的综合。说明说明:(1)若若G是是Euler图，则图，则G的任何的任何Euler环游都是最优环游环游都是最优环游.(2)若若G 不是不是Euler图，用添加重复边以使图，用添加重复边以使G成为欧拉图成为欧拉图G*的方法时，添加的重复边具有的特征由定理的方法时，添加的重复边具有的特征由定理3给出给出.定理定理3 若若W是图是图G中一条包含所有边的闭通道，则中一条包含所有边的闭通道，则W在在这样的闭通道中具有最短的长度的充要条件是：这样的闭通道中具有最短的长度的充要条件是：(1)每一条边最多重复经过一次；每一条边最多重复经过一次；(2)在在G的每一个圈上，重复经过的边的数目不超过的每一个圈上，重复经过的边的