第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)无欧拉迹。,例1,定理1 下列陈述对于一个连通图G是等价的:,(1)G是欧拉图。,(2)G的每个点的度是偶数。,(3)G的边集能划分为圈。,令C是G中的一条欧拉闭迹。C中任一个给定的点在C中每出现一次恰关联两条边,因为G的每条边在C中仅出现一次,所以该点的度应为该点在C中出现的次数乘以2,是一个偶数。,推论
2、 连通图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 中
3、奇点数不超过2,2.若奇点数为0,则一笔画与起点无关;若奇点 数为2,则一笔画的起点与终点均为奇点.,3.在有向图(即每条边均为有向边的图,其系统讨论将在第九章进行)中有类似结论.,有向图D中,以一点u为起点的弧(即有向边)的数目称为u的出度,记为 dD+(u);以一点u为终点的弧的数目称为u的入度,记为dD-(u)。,定理3 下列陈述对于一个连通有向图D是等价的:,(1)D是欧拉有向图。,(2)D的每个点的入度等于出度。,(3)D的弧集可划分为有向圈。,4.2 高效率计算机鼓轮的设计,计算机中旋转鼓轮的位置是借助于鼓轮表面上的一系列电触点所产生的二元信号来识别的。这个表面分为m段,每段由绝缘
4、体或导体材料组成。绝缘段给出信号0(没有电流),导通段给出信号1(有电流)。,1.S的周期:S中对任何正整数n,具有 an+=an的最小的正整数.,问题 为提高效率,我们期望鼓轮每旋转一周(m段)读出的由k位组成的m个数应是互不相同的.进一步,对故定的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的
5、具有最大的一个(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位排成一个圆圈,与所求的鼓轮相对应,就得到下图的鼓轮设计。,德 布鲁因序列的构造:,步骤1 构造一个有向图H:它的点是2k-1个不同的有序(k-1)-元组。对点 v=(b
6、1,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的欧拉有向闭迹,
7、由此得k-部分序列 S1,S2,S 和相应的德 布鲁因序列S.,例 下图为k=4(=24=16)的德 布鲁因图,相应的欧拉有向闭迹及相应的德 布鲁因序列.,该例有16个解,其中的一些为,(abcdkijefjhlmnpq)=(0000101101001111)(abcdkipghlmjefq)=(0000101100111101)(abcfgijedklmnpq)=(0000100110101111)(abhijklmnpgcdefq)=(0000110111100101)(abhijedklmnpgcfq)=(0000110101111001)(abhijefgcdklmnpq)=(0000
8、110100101111)(abhipgcdklmnjefq)=(0000110010111101),4.3中国邮路问题,问题:邮递员从邮局出发,递送邮件,然后返回邮局,要求辖区每条街至少走一遍且走过的总路程最短,应如何选择路线?,图论模型:在一个连通的具有非负权的赋权图G中找一条包含每条边(允许重复)且边权之和最小的闭途径.称之为最优环游。,对该问题(1)若图G是一个欧拉图,则找出G的欧拉回路即可。,(2)对一般图,其解法为:添加重复边以使G成为欧拉图G*,并使添加的重复边的边权之和为最小,再求G*的欧拉回路。,(3)对恰有两个度数为奇的点的图G,可证:需要重复的边正好是从一个奇度点到另一个
9、奇度点的最短路上的边,即问题为欧拉问题与最短路问题的综合。,说明:(1)若G是Euler图,则G的任何Euler环游都是最优环游.,(2)若G 不是Euler图,用添加重复边以使G成为欧拉图G*的方法时,添加的重复边具有的特征由定理3给出.,定理3 若W是图G中一条包含所有边的闭通道,则W在这样的闭通道中具有最短的长度的充要条件是:,(1)每一条边最多重复经过一次;,(2)在G的每一个圈上,重复经过的边的数目不超过圈的长度的一半,算法的思想 从任一点出发按下法来描画一条边不重复的迹,使在每一步中未描画的子图的割边仅当没有别的边可选择时才被描画。,Euler图中确定Euler环游的Fleury算
10、法,Fleury算法,1.任意选取一个顶点v0,置w0=v0。,2.假设迹wi=v0e1v1eivi已经选定,那么按下述方法从 E e1,e2,ei中选取边ei+1:使(1)ei+1和vi相关联;(2)除非没有别的边可选择,否则ei+1 不是 G=G-e1,e2,ei的割边。,3.当第2步不能再执行时,算法停止。,例,可证,Fleury算法是一个好算法。,例:某博物馆的一层布置如下图,其中边代表走廊,结点e是入口,结点g是礼品店,通过g我们可以离开博物馆。请找出从博物馆e进入,经过每个走廊恰好一次,最后从g处离开的路线。,解:图中只有两个奇度顶点e和g,因此存在起点为e,终点为g的欧拉迹。,为
11、了在G中求出一条起点为e,终点为g的欧拉迹,在e和g间添加一条平行边m,用Fleury算法求出欧拉环游为:,emgcfabchbdhgdjiejge,所以:解为:egjeijdghdbhcbafcg,设G=(n,m)是欧拉图,由Fleury算法知:算法需要m次循环;,算法中主要运算是判断:,该判断的时间复杂性是n2数量级的。,所以Fleury算法时间复杂性是:O(n2m),是好算法。,算法复杂性分析,(2)考查G的圈,若存在圈C,其中重复边的总长大于圈长的一半,则在圈C上交换重复边和不重复边得图G”.重复这个过程,直到得到一个图G*,在G*中没有重复边的总长大于圈长的一半的圈.,不是Euler
12、图求最优环游的方法,(1)用每条边最多添一条边的方法任意添一些重复边使图G 成为一个欧拉多重图G.,(3)用Fleury算法求G*的Euler环游.,例 图G如图(a)所示(各边权为1),它有10个奇度点。任意添一些边得到一个欧拉多重图(b)。,(b)中有色圈中重复边的数目为5,大于圈长8的一半,在这个圈上交换重复边和不重复边,得到(c)。,(c)中每一个圈中重复边的数目均不大于圈长的一半.从而,由(c)中每条欧拉闭迹对应原图一条闭通道,它含有所有的边且具有最短的长度。,(a),(b),4.4 哈密尔顿图,经过图中每个点仅一次的路(圈)称为的Hamilton路(圈),存在Hamilton圈的图
13、称为哈密尔顿图,简称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=|
14、S|,可验证彼得森图(上图(b)所示)不是哈密尔顿图,但满足式(*)式。这表明定理5给出的条件只是图 G 是哈密尔顿图的必要条件而不是充分条件。,引理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=uvv3v4vnu。当G1=G+uv时,有,故有,若有i(3in-1)使u adj vi,v adj vi+1(如图),则 G
15、中有一个H圈 C1=uvivi-1v3 v vi+1vi+2vn u即G是H 图,若不存在这样的i,因 v3,v4,vn-1中有-2 个点与u邻接,故v4,v5,vn中就有-2 个点不能与v 邻接。从而,这与已知条件相矛盾。故在假设的 dG(u)+dG(v)n的条件下,一定存在上述图示那样的i,使G中存在一个H 圈,所以G为H图。,定义1 在n阶简单图G中,若对d(u)+d(v)n的任何一对点u和v均有u adj v,则称G是闭图。,引理2 若G1和G2是同一个点集V 的两个闭图,则G=G1G2是闭图。,由G1和G2是闭图,u和v在G1和G2中都邻接,故u和v在G中也邻接,从而G是闭图。,证明
16、 因对任何wV,有 dG(w),dG(w),注:闭图的并不一定是闭图。例如,定义2 若一个与G 有相同点集的闭图,使G,且对异于 的任何图H,若有G H,则H不是闭图,则称 是G的闭包,即G的闭包是包含G的极小闭图。,图的闭包的构造方法:将图中度数之和至少是图的顶点个数的非邻接顶点对递归地连接起来,直到不再有这样的顶点对存在时为止。,例 下图给出了6个顶点的图的闭包的构造过程。,故唯一。,引理3 图G的闭包是唯一的。,G,证明 如果 和 是G 的两个闭包。则由 G G,得,证明 如果G是H图,显然,是H图。,定理7(Bondy 1969)一个简单图G是H图的充要条件为它的闭包 是H图。,如果
17、是H图,当G=时,结论成立;当G 时,必相继存在若干条边,使得,G+e1+e2+ek=,其中eiG,(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)两个均不是完全图,但它们却是自己的闭包。,推论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均有 d(u)+d(v
18、)n则G是H图。,说明:判断一个图是否哈密尔顿图,往往要结合定义进行。由定义知:一个图若有度为1的顶点,一定不是哈密尔顿图,只可能有哈密尔顿路;若图是哈密尔顿图,则图中2度顶点关联的边必属于所有哈密尔顿圈;一个顶点关联的边再多,一个哈密尔顿圈只能用其两条边。,不是哈密尔顿图,因图中二度顶点所关联的8条边(红边)已构成圈,而此圈不是哈密尔顿圈。,问题:一个旅行售货员想访问若干城市(假定各城镇之间均有路可通),然后返回。问如何安排路线使其能恰好访问每个城镇一次且走过的总路程最短?这个问题称为旅行售货员问题.,求最优圈,目前还没有一个理想的算法。,4.6 旅行售货员问题,图论模型:在赋权完全图G中求
19、具有最小权的哈密尔顿圈,这个圈称为最优圈。,一个可行解法:,(1)任取G 的一个哈密尔顿圈C。,(2)修改 C 为 Cij 使Cij 比 C 优,其方法为:设 C=v1 v2vn v1,若存在整数 i,j,满足0 i+1j n,且 w(vivj)+w(v i+1v j+1)w(vi vi+1)+w(vj vj+1)则 Cij=v1 v2 vi vj vj-1 v i+1 v j+1 vj+2 vnv1 比 C 优。其中C与Cij的关系如图所示。,例3 求图中(a)所示图的最优圈。,解 任取一个哈密尔顿圈C=bcadb,如图(b)。,w(ca)+w(db)=18+7=25 23=w(cd)+w(
20、ab)取 C=b c d a b。,第五章 匹配与因子分解,5.1 匹配,定义 设M是图G的边子集,若任意的 eM,e 都不是环,且属于M 的边互不相邻,则称 M 为 G的一个匹配。设 M 为 G 的一个匹配,对 vV(G),若 v 是 M 中某边的一个端点,则称 v 为 M 饱和点,否则称为 M 非饱和点。,匹配还可分为最大匹配(含边数最多的匹配)和完美匹配(图中的点均为 M 饱和点的匹配 M)等类型。,对 M2,点v1是的饱和点,点v2是非饱和点。,例1中的M1 和M2既不是最大匹配,也不是完美匹配,而M3是最大匹配,也是完美匹配。,例1 设图G 为:,G的匹配有:,M1=v1v8,M2=
21、v1v3,v8v4,v7v5,M3=v1v2,v8v3,v7v4,v6v5 等等,关系:(1)完美匹配必是最大匹配,而最大匹 配不一定是完美匹配。,(2)一个图的最大匹配必存在,但完美匹配不一定存在。,(3)图G 存在完美匹配的一个必要条件 是 G 的点数为偶。,设M 为图G的一个匹配,可看出:对3,若取3中非 M 的边再连同 M 的不在3中的边组成 M,则 M 的边数比 M的边数多,这表明 M 不是该图的最大匹配。,M 交错路:G 中由M中的边与非M 中的边交替组成的路。,M 可扩路:起点与终点均为M 非饱和点的M交错路。,定理1(Berge,贝尔热,1957)G 的匹配 M是最大匹配当且仅
22、当 G 不含 M 可扩路.(等价于:M不是最大匹配当且仅当 G 含 M 可扩路),证明 设M是G的匹配,并假设G 包 含M可扩充路 v0v1v2m+1,定义M E 为M=(M v1v2,v3v4,v2m-1 v2m)v0v1,v2v3,v2m v2m+1,则M是G的匹配,且|M|=|M|+1,因而M就不是最大匹配。,反之,假设M不是最大匹配,且令M是G的最大匹配,则|M|M|(1.1)置H=GMM,这里MM表示M和M的对称差。,贝尔热(1926-2002)法国著名数学家。他的无限图理论及其应用(1958)是继哥尼之后的图论历史上的第二本图论专著。他不仅在图论领域做出了许多贡献,而且四处奔波传播
23、图论,推动了图论的普及和发展。1993年,他获得组合与图论领域颁发的欧拉奖章。贝尔热在博弈论、拓扑学领域里也有杰出贡献。在博弈领域,他引入了Nash均衡之外的另一种均衡系统。Nash的生活被改编成电影美丽的心灵,获02年奥斯卡金像奖。贝尔热对中国的手工艺很感兴趣。他也是一位象棋高手,还创作过小说谁杀害了Densmore公爵。,H 的每个顶点在H中具有的度是1或2。因为它最多只能和M的一条边以及 M的一条边相关联,因此 H 的每个分支或是由M和M中的边交错组成的偶圈,或是由M和M中的边交错组成的路。由(1.1)式,M包含的边多于M的边,因而H中必定有的一条路P,其边始于M且终止于M,因此P的起点



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 匹配 103

链接地址:https://www.desk33.com/p-740467.html