欧拉图和哈密尔顿图-精.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,欧拉图和哈密尔顿图,信号处理中的数学方法 第,2-4,讲,一,.,欧拉回路：,一般不限于简单图，一般指无向图,原问题：,“,右边的图中是否存在包含每条边一次且恰好一次的回路？,”,原问题等价于：欧拉图,C,D,A,B,A,C,B,D,Eg,.,哥尼斯堡七桥问题,欧拉回路，欧拉通路,图,G,的一个回路,/,通路,它经过,G,中每条边恰好一次，则回路,/,通路称为欧拉回路,/,通路。,定义：如果图,G,中含欧拉回路，则图,G,称为欧拉图。,定义：如果图,G,中仅有欧拉通路，但没有欧拉回路，则图,G,称为半欧拉图。,例,“,一笔划,”,问题,G,中有欧拉通路,？,实例,上图中，,(1),(4),为欧拉图,例 多米诺骨牌，,28,块,能否排成一圈使两两相邻的半边的点数相同，问是否可能？,将,0-6,看作,7,个结点，任,2,点的边看作一块骨牌,这样,该问题转化为,G,有无欧拉回路的问题,定理,对连通图，下列命题等价,1,）,G,是欧拉图,2,）,G,的每个结点为偶度数,3,）,G,的边集能划分成为基本回路，即,eg,.,证,1),2)3)1),1),2):,设,Go,为,G,的欧拉回路，可将,Go,表示为,v,1,e,1,v,2,e,2,e,n,v,n+1,(v,n+1,=v,1,),，其中,v,i,的一次出现总关联于左右,2,条边，对应度数为,2,又,Go,的,e,1,，,e,2,，,e,n,互不相同，且穷尽了所有的边，这样任一点,v,i,的度数为,v,i,在,Go,中出现的度数之和,必为,2,的倍数。,/,2),3):,G,连通，不妨设,G,是非平凡图,由,2,）每个结点度数至少为,2,，,所以,G,中含一基回,Z,1,，,Z,1,的度数为偶度数，删去,Z,1,的边得到,G,，原,G,为偶度数，删去,G,的每个点仍为偶度数,除孤立点外其余点至少为,2,度，即余连通点所图至少,2,连通,如法炮制，直至余图不含边,Z,1,，,Z,2,，,.,Z,k,为,E,的一个划分。,/,3),1),：,Z,1,是划分中的一个基回，若,Z,1,=E,，则,Z,1,就欧拉回路，,G,是欧拉图,否则，存在另一回路,Z,2,与,Z,1,有公共点,v,构造简单回路，从,v,经,Z,1,回到,v,，再经,Z,2,回到,v,将,Z,1,UZ,2,看作,Z,1,，再重复,上述过程，得到穷尽,E,G,的简单回路。,G,欧拉图。,/,提示,全部是偶度点的连通图中的回路,若干小回路串成欧拉回路,续例 多米诺骨牌问题,能构成回路，能够连成首尾圈。,/,定理,连通图,G,，若,G,中仅有,0,或,2,个奇,度数点,G,有欧拉通路。,0,个奇度数，显然欧拉回路,2,个奇度数，,u,，,v,，分情况：,1,）,u,v,相邻，删,(,u,v,),余图,G,为欧拉图，,从,u,开始在,G,中走欧拉回路，回到,u,，再,走,(,u,v,),得到欧拉通路,2,）,u,v,不相邻，向着,v,方向，取,(u,u,1,),删,(u,u,1,),，以,u,1,为始，重复过程，直至删,(,u,i,v,),后得到欧拉回路，连上所删除的边，得到,得到欧拉通路。,/,续例,.,“,一笔划,”,问题,G,连通，从一个奇度点开始画，图只有,0,或,2,个奇度点，则,G,可一笔画。,/,定理,对有向图，,G,有欧拉回路,每一结点入度等于出度。,安排国展中心参观路线,A,B,C,J,E,F,I,K,H,G,D,L,N,M,O,A,B,C,I,J,D,K,L,M,N,H,O,E,G,F,参观区域实景 图,G,设,E,为起始点,E,N,M,O,L,K,I,L,M,J,N,D,C,J,B,I,A,K,H,G,O,F,E,1),任取一点,v,0,，置,w,0,=v,0,2),设简单回路,w,i,=,v,0,e,1,v,1,e,2,e,i,v,i,已选定，则从,E,G,e,1,e,2,e,i,中选,e,i+1,选择条件：,i.,e,i,与,v,i,相邻,ii.,对,E,G,e,1,e,2,e,i,而言非割边优先,3),重复,2),，直到不能执行,讨论这种情况下，会否出现,E,G,e,1,e,2,e,i,中有边，而,2),之条件,i,不成立的情况：,如,v,i,=v,0,，则必有某个,ji,时刻选,e,j+1,边为割边,与,2,）之,ii,条件相矛盾，,不可能,出现，即,v,i,v,0,如,v,i,v,0,，则,v,i,的度数为奇数,与欧拉图相矛盾,在画欧拉回路时，已经经过的边不能再用；,在走回路中的,任何时刻,，将已经经过的边删除，,剩下的边,必须,仍,在同一,连通,分支当中,提示：,随机欧拉图,G,是欧拉图，,v,V,G,，从,v,开始，每一步从当前点所关联边中随机选边，均可构造欧拉回路，则,G,称为以,v,为始点的随机欧拉图。,注，若,G,是以,v,为始点的随机欧拉图，则任何一个以,v,为始点的不包含,G,中所有边的回路都应该能扩充成欧拉回路。反之，若,G,不是以,v,为始点的随机欧拉图，则一定存在已经包含了,v,所关联的所有边，却未包含,G,中所有边的简单回路。,随机欧拉图的判定,定理,欧拉图,G,是以,v,为始点的随机欧拉图,当且仅当,G,中任一回路均包含,v,。,推论,欧拉图,G,是以任一顶点为始点的随机欧拉图 当且仅当,G,本身是一个基本回路,),中国邮递员问题：,问题：邮递员从邮局出发，走过辖区内每条街道,至少一次,，如何选择最短路线？,1,）每街一次,/,至少一次,2,）环游最短,中国邮递员问题,-,模型,数学模型：,构造无向权图,G,，以道路为边，路长为权,问题的解,G,中包含所有边的回路权最小，称为最优回路,(,未必是简单回路,),。,当,G,是欧拉图，则最优回路即欧拉回路。,若,G,不是欧拉图，则通过加边来消除,G,中的奇度顶点，,要求使加边得到的欧拉图,G,中重复边的权和最小,。,周游世界的游戏,1859,哈密尔顿,“,周游世界,”,游戏：,20,个城市，每个城市恰游一次，回到出发地,用一个正,12,面体的,20,个,顶点代表,20,个城市，,哈密尔顿图,定义：若图,G,中有经过所有顶点的基本回路，称为,哈密尔顿回路，若,G,中含哈密尔顿回路，则称,G,为,H_,图,。,定义：经过图,G,中所有顶点的,基本通路称为哈密尔顿通路，,若,G,中含哈密尔顿通路，,但不含,哈密尔顿回路，则称,G,为半哈密尔顿图。,周游世界的游戏,的解,哈密顿图,哈密顿图,哈密顿图,无哈密顿通路,存在哈密顿通路,实例,在上图中，,(1),(2),是哈密顿图,;,实例,已知有关人员,a,b,c,d,e,f,g,的有关信息,a,：,说英语；,b,：,说英语或西班牙语；,c,；,说英语，意大利语和俄语；,d,：,说日语和西班牙语,e,：,说德语和意大利语；,f,：,说法语、日语和俄语；,g,：,说法语和德语,.,试问：上述,7,人中是否任意两人都能交谈？,(,可借助其余,5,人中组成的译员链帮助,),解 设,7,个人为,7,个结点,将两个懂同一语言的人之间连一条边,(,即他们能直接交谈,),这样就得到一个简单图,G,问题就转化为,G,是否连通,.,如图所示,因为,G,的任意两个结点是连通的,所以,G,是连通图,.,因此,上述,7,个人中任意两个人能交谈,.,a,：,说,英语,；,b,：,说,英语,或,西班牙,语；,C:,说英语,意大利语,和,俄语,；,d,：,说,日语,和,西班牙,语,e,：,说德语和,意大利语,；,f,：,说,法语,、,日语,和,俄语,；,g,：,说,法语,和德语,.,a,b,c,d,e,f,g,解一,解二,a,b,c,d,e,f,g,英,英,西,日,法,德,意,如果题目改为：试问这,7,个人应如何安排座位,才能使每个人都能与他身边的人交谈？,解：用结点表示人，用边表示连接的两个人能说讲一种语言，够造出,哈密顿图如右上,图所示。,a,：,说英语；,b,：,说英语或西班牙语；,c,；,说英语，意大利,语和俄语；,d,：,说日语和西班牙语,e,：,说德语和意大利语；,f,：,说法语、日语和俄语；,g,：,说法语和德语,.,判断,H-,图,任何一个,H_,图,都可以看成是一个基本回路，再加上其他若干条边,H_,图的充分条件和必要条件均有，但尚无充要条件,H_,图的必要条件,G,是,H_,图,，则对,V,G,的任意非空真子集,S(,S,，,S,V,，均有,W(G-S),|S|,其中,W(G),是,G,的分支数,必要条件的应用,证,设,C,是,G,的,H_,回路,W(C-S),|S|,(,从一个基本回路上,删除,k,个顶点,，,最多形成,k,个连通分支,),又,G,S,与,C,S,的点相同，而,E,G-S,E,C,S,W(G-S),|S|,例,图中,A,类点仅与,B,类点连,|A|=|v,1,v,3,v,7,|=3,|B|=|v,2,v,4,v,5,v,6,v,8,|=5,选,S=v,1,v,3,v,7,，,|S|=3,则,W(G-S)=5,|S|=3,必要条件的局限性,只能判定一个图,不是,哈密尔顿图,下图,(Petersen,图,),满足上述必要条件。,Petersen,图不是,H_,图。,H-,通路,/,半哈密尔顿图 充分条件,定理,简单,G,有,n(n,2),个节点，若,G,中任二点度数和大于等于,n-1,，则,G,有,H-,通路,例,.,有,H_,通路，无,H_,回路,设,S=v,1,v,4,，,|S|=2,W(G-S)=3,2,=,|S|,H-,图的 充分条件,定理,简单,G,有,n,个结点，,n,3,，,若,G,中任二点度数和大于等于,n,，则,G,有,H-,图,例,.N,边形，,n,5,任一对结点度数和,=4,5,但它显然是,H_,图,例,.,Kn,是完全图,d(v,i,)+d(v,j,)=(n-1)+(n-1)=2n-2,n (,n,3),K,n,是,H-,图,只要图中边足够多，,G,易为,H_,图,只要图中成对节点度数足够大，,G,易为,H_,图,间接充要条件,引理,设,G,中,u,v,不相邻，且,d(u)+d(v,),n,，则,G+(u,v,),是,H_,图的充要条件是,G,是,H_,图,闭合图,C(G),：,在,G,中反复增添结点度数和,|V,G,|,的不相邻的节点对上的边，直至不能再添，得到的图为,闭合图,C(G),图,G,的闭合图是唯一的,例,加成了完全图，,故是,H_,图,“,如果只在满足,d,(u)+,d,(v,),n,的,u,v,之间加边,构造闭合图，图的哈密尔顿性质不会改变,”,棋盘上的哈密尔顿回路问题,在,4,4,或,55,的缩小了的国际象棋棋盘上，马,(Knight),不可能从某一格开始，跳过每个格子一次，并返回起点。,货郎担,/,旅行推销员,(TSP),问题：,在一个赋权的完全图中，找出一个具有最小权的,H_,回路，也即回路边的权之和最小,对该赋权图上的边，满足三角不等式（距离不等式）,W(a,b,),W(a,c,)+,W(c,b,),数学模型,构造无向带权,图,G,，,V,G,中的元素对应于每个城市，,E,G,中每个元素对应于城市之间的道路，道路长度用相应边的权表示。,则问题的解对应于,G,中包含所有边的权最小的哈密尔顿回路。,G,是带权完全图，总共有,n!/2,条哈密尔顿回路。因此，问题是如何从这,n!/2,条中找出最短的一条,eg,：含,20,个顶点的完全图中不同的哈密尔顿回路有约,6000,万亿条,-(1.21645,10,17,)/2,，若机械地检查，每秒处理,10,万条，需,2,万年,货郎担问题的近似算法,1),由任一点,v,0,开始，找一条与之相关联的权最小的边,(V,0,V,1,),，形成初始回路,v,0,v,1,2),设,v,0,v,1,v,i,已选定，从,V,v,0,v,1,v,i,中找一点,v,i+1,与,v,i,距离最近,3),重复,2),直到所有节点都在通路中,4),连接始点与终点,不一定是最佳解,例,8,c,d e,a,b,e,14,12,9,5,6,7,13,11,10,从,a,出发的“较好的”回路，,14,8,a d c e b a,7,6,5,长度：,40,算法精度下限,设算法所得的回路长度为,d,，,d,0,是最小,H_,回路的长度，,G,有,n,点，则,d/d,0,ln(n)+1+,改进：,如果在已有回路中，,W(v,i,v,j,)+W(v,i+1,v,j+1,)W(v,i,v,i+1,)+W(v,j,v,j+1,),则分别用边,v,i,v,i+1,和,v,j,v,j+1,替代,v,i,v,j,和,v,i+1,v,j+1,。,从,a,出发的“较好的”回路长度：,40,14,8,a,a,d,c,e,b,7,6,5,9,10,a,a,d,c,e,b,7,6,5,9,10,经改进的回路，长度：,37,c,d e,a,b,e,14,12,9,5,6,7,13,11,10,