《离散数学》特殊图-1

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,第,8,章,一些特殊的图,8.1,二部图,8.2,欧拉图,8.3,哈密顿图,8.4,平面图,1,8.1,二部图,二部图,完全二部图,匹配,极大匹配,最大匹配,匹配数,完备匹配,2,二部图,定义,设无向图,G,=,若能将,V,分成,V,1,和,V,2,(,V,1,V,2,=,V,V,1,V,2,=,),使得,G,中的每条边的两个端点都一个属于,V,1,另一个属于,V,2,则称,G,为,二部图（二分图）,记为,称,V,1,和,V,2,为,互补顶点子集,.,若,V,1,中每个顶点均与,V,2,中每个顶点有且只有一条边相关联,则称二部图,G,为,完全二部图,记为,K,r,s,r,=|,V,1,|,s,=|,V,2,|.,注意,:,n,阶零图（,|E|,0,）为二部图,.,3,二部图的判别法,定理,无向图,G,=,是二部图当且仅当,G,中无奇数长度的回路（无奇圈）,.,例：述各图都是二部图,4,匹配,设,G,=,为无向图,E,*,E,匹配,(,边独立集,),:,任,2,条均不相邻的边组成的边子集,任,2,条边的端点都不一样,极大匹配,:,添加任一条边后都不再是匹配的匹配,最大匹配,:,边数最多的极大匹配,匹配数,:,最大匹配中的边数,记为,1,最大匹配的边数不超过,|V|,的一半,例,3,个图的匹配数 依次为,3,3,4.,5,匹配,(,续,),设,M,为,G,中一个匹配，,v,V,(,G),v,为,M,饱和点,:,M,中有边与,v,关联,v,为,M,非饱和点,:,M,中没有边与,v,关联,M,为完美匹配,:,G,的每个顶点都是,M,饱和点,所有点都在匹配边上,完美匹配是最大匹配,例,关于,M,1,a,b,e,d,是饱和点,f,c,是非饱和点,M,1,不是完美匹配,M,2,是完美匹配,M,1,M,2,6,二部图中的匹配,定义,设,G,=,为二部图,M,是,G,中最大匹配,若,|M|,min|,V,1,|,，,|,V,2,|,，则称,M,为,G,中的一个完备匹配,V1,或,V2,的任意节点都是,M,中边的端点,M,是完备匹配，,|,V,1,|,|,V,2,|,则称,M,为,V,1,到,V,2,的一个,完备匹配,.,当,|,V,1,|=|,V,2,|,时,完备匹配变成完美匹配,.,两部分一对一,最大匹配一定存在，完备匹配不一定存在,7,二部图中的匹配,(1),(2),(3),例 图中红边组成各图的一个匹配，,(1),为完备的,但不是完,美的,;(2),不是完备的,其实,(2),中无完备匹配,;(3),是完美的,.,8,Hall,定理,定理,(Hall,定理,),设二部图,G,=,中，,|,V,1,|,|,V,2,|.,G,中存,在从,V,1,到,V,2,的完备匹配当且仅当,V,1,中任意,k,个顶点至少与,V,2,中的,k,个顶点相邻,(,k,=1,2,|,V,1,|).,由,Hall,定理不难证明,上一页图,(2),没有完备匹配,.,定理,设二部图,G,=,中,V,1,中每个顶点至少关联,t,条边,(,t,1),而,V,2,中每个顶点至多关联,t,条边，则,G,中存在,V,1,到,V,2,的完备匹配,.,Hall,定理中的条件称为“,相异性条件,”,第二个定理中的条件,称为,t,条件,.,满足,t,条件的二部图一定满足相异性条件,.,9,一个应用实例,例 某课题组要从,a,b,c,d,e,5,人中派,3,人分别到上海、广州、香港去开会,.,已知,a,只想去上海，,b,只想去广州，,c,d,e,都表示想去广州或香港,.,问该课题组在满足个人要求的条件下，共有几种派遣方案？,解 令,G,=,其中,V,1,=,s,g,x,V,2,=,a,b,c,d,e,E,=(,u,v,)|,u,V,1,v,V,2,v,想去,u,其中,s,g,x,分别表示上海、广州和香港,.,G,如图所示,.,G,满足相异性条件，因而可给,出派遣方案，共有,9,种派遣方案,(,请给出这,9,种方案,).,10,上图是二部图，满足,t,条件（,t,2,），存在,V1,到,V2,的完备匹配,11,8.2,欧拉图一笔画问题,欧拉通路,欧拉回路,欧拉图,半欧拉图,12,哥尼斯堡七桥问题,欧拉图是能一笔画出的边不重复的回路,.,13,欧拉图,欧拉通路,:,经过图中每条边一次且仅一次，并且行遍图中每,个顶点的通路,.,欧拉回路,:,经过图中每条边一次且仅一次，并且行遍图中每个顶点的回路,欧拉图,:,有欧拉回路的图,.,几点说明：,上述定义对无向图和有向图都适用,.,规定平凡图为欧拉图,.,欧拉通路是简单通路,欧拉回路是简单回路,.,环不影响图的欧拉性,.,14,一笔画问题,笔不离开纸，每边只能画一次，不允许重复，将图画出，称该图能一笔画。,如终点回到起点，则等价于该图存在欧拉回路,如终点不是起点，则等价于该图仅存在欧拉通路,如该图不能一笔画，则等价于该图不存在欧拉通路和欧拉回路。,15,A,B,C,D,A,B,D,C,B,F,C,E,H,A,D,G,图,a,不是一笔画，它不是欧拉图，也不存在欧拉通路；,图,b,能完成起点和终点不同的一笔画，存在欧拉通路,ACFEBCDGFH,，但不存在欧拉回路，不是欧拉图；,图,c,能完成起点与终点相同的的一笔画，存在欧拉回路，它是欧拉图。,16,欧拉图,(,续,),例 图中,(1),(4),为欧拉图,;(2),(5),为欧拉通路,;(3),，,(6),既不,是欧拉图,也不是欧拉通路,.,在,(3),(6),中各至少加几条边才能成为欧拉图,?,17,欧拉图的判别法,定理,无向图,G,为欧拉图当且仅当,G,连通且无奇度顶点,.,无向图,G,是欧拉通路当且仅当,G,连通且恰有两个奇度顶点,.,定理,有向图,D,是欧拉图当且仅当,D,连通且每个顶点的入度都等于出度,.,有向图,D,具有欧拉通路当且仅当,D,连通且恰有两个奇度顶点,其中一个入度比出度大,1,另一个出度比入度大,1,其余顶点的入度等于出度,.,18,实例,例,1,哥尼斯堡七桥问题,例,2,下面两个图都是欧拉图,.,从,A,点出发,如何一次成功地走出一条欧拉回路来？,19,中国邮路问题：,问题：一个邮递员从邮局出发,走遍所有街道,把邮件送到每个收件人手中,最后回到邮局,要怎样走,使全程路线最短。,转化为图论问题：以街道为边,以街道交叉点为结点,以街道的长度为边上的权,在权图,G=,上,找出一个经过所有边至少一次的回路,并使得该回路的权和达到最小。,说明：,该回路未必是,Euler,回路,边允许重复。,管梅谷提出了这个问题,并指出如果图,G,有,m,条边,则所求回路至少是,m,条边,最多不超过,2m,条边,并且每边在回路中至多出现两次。,20,8.3,哈密顿图点不重复,哈密顿通路,哈密顿回路,哈密顿图,半哈密顿图,21,哈密顿周游世界问题,22,哈密顿图的定义,哈密顿通路,:,经过图中所有顶点一次且仅一次的通路,.,哈密顿回路,:,经过图中所有顶点一次且仅一次的回路,.,哈密顿图,:,具有哈密顿回路的图,.,几点说明：,平凡图是哈密顿图,.,哈密顿通路是初级通路，哈密顿回路是初级回路,.,环与平行边不影响图的哈密顿性,.,23,实例,例 图中,(1),(2),是哈密顿图,;(3),是哈密顿通路,.,(4),既不是哈密顿图,也不是哈密顿通路，为什么？,24,无向哈密顿图的一个,必要条件,定理,设无向图,G,=,是哈密顿图,则对于任意,V,1,V,且,V,1,均有,p,(,G,V,1,),|,V,1,|.,证 设,C,为,G,中一条哈密顿回路,有,p,(,C,V,1,),|,V,1,|.,又因为,C,G,故,p,(,G,V,1,),p,(,C,V,1,),|,V,1,|.,几点说明,定理中的条件是哈密顿图的必要条件,但不是充分条件,.,可利用该定理判断某些图不是哈密顿图,.,由定理可知,二部图,K,r,s,当,s,r,+1,时不是哈密顿图,.,当,r,2,时,二部图,K,r,r,是哈密顿图,而二部图,K,r,r,+1,是哈密顿通路,.,25,理解：满足上述条件的土不一定是哈密顿图,如彼得森图，去掉一个点，连通分支数不发生变化，仍然为,1,，满足条件，但不是哈密顿图；,26,实例,例 设,G,为,n,阶无向连通简单图,若,G,中有割点或桥,则,G,不是哈密顿图,.,证,(1),设,v,为割点,则,p,(,G,v,),2|,v,|=1.,根据定理,G,不是哈密顿图,.,(2),若,G,是,K,2,(,K,2,有桥,),它显然不是哈密顿图,.,除,K,2,外,其他的有桥连通图均有割点,.,由,(1),得证,G,不是,哈密顿图,.,27,无向哈密顿图的一个充分条件,定理,设,G,是,n,阶,(,n,3),无向简单图,若任意两个不相邻的顶,点的度数之和大于等于,n,1,则,G,中存在哈密顿通路,.,当,n,3,时,若任意两个不相邻的顶点的度数之和大,于等于,n,则,G,中存在哈密顿回路,从而,G,为哈密顿,图,.,28,哈密顿通路,(,回路,),的存在性,(,续,),定理中的条件是存在哈密顿通路,(,回路,),的充分条,件,但不是必要条件,.,例如,设,G,为长度为,n,1(,n,4),的路径,它不满足定理,中哈密顿通路的条件,但它显然存在哈密顿通路,.,设,G,是长为,n,的圈,它不满足定理中哈密顿回路的条,件,但它显然是哈密顿图,.,29,由定理,当,n,3,时,K,n,均为哈密顿图,.,判断某图是否为哈密顿图至今还是一个难题,定理,8.8,：设有向图,D=,|V|=n,2,如果所有的有向边均用无向边代替,所得无向图中含有生成子图,kn,，则该有向图中存在哈密尔顿通路。,推论,:|V|,3,的有向,(,无向,),完全图为哈密尔顿图。,30,哈密顿图与欧拉图,H,E,E,H,非,H,非,E,31,判断是否是哈密顿图,的可行方法,观察出一条哈密顿回路,例如 右图,(,周游世界问题,),中红,边给出一条哈密顿回路,故它,是哈密顿图,.,注意,此图不满足定理的条件,.,满足充分条件,例如 当,n,3,时,K,n,中任何两个不同的顶点,u,v,均,有,d,(,u,)+,d,(,v,)=2(,n,1),n,所以,K,n,为哈密顿图,.,32,判断是否是哈 密顿图,的可行方法,(,续,),例,1/4,国际象棋盘,(4,4,方格,),上的,跳马问题,:,马是否能恰好经过,每一个方格一次后回到原处,?,解 每个方格看作一个顶点,2,个,顶点之间有边当且仅当马可以从一个方格跳到另一个方格,得到,16,阶图,G,如左图红边所示,.,取,V,1,=,a,b,c,d,则,p,(,G,V,1,),=6|,V,1,|,见右图,.,由定理,图中无哈密顿回路,故问题无解,.,不满足必要条件,33,应用实例,例 某次国际会议,8,人参加，已知每人至少与其余,7,人中,的,4,人有共同语言，问服务员能否将他们安排在同一张,圆桌就座，使得每个人都能与两边的人交谈？,解 图是描述事物之间关系的最好的手段之一,.,作无向图,G,=,其中,V,=,v,|,v,为与会者,，,E,=(,u,v,)|,u,v,V,u,与,v,有共同语言,且,u,v,.,G,为简单图,.,根据条件,v,V,d,(,v,),4.,于是，,u,v,V,有,d,(,u,)+,d,(,v,),8.,由定理可知,G,为哈密顿,图,.,服务员在,G,中找一条哈密顿回路,C,，按,C,中相邻关系,安排座位即可,.,由本题想到的：哈密顿图的实质是能将图中所有的顶点,排在同一个圈中,.,34,应用货郎担问题：,问题的提出：今有,n,个城市,任意两个城市之间均有路,今有一个售货员从某个城市出发要经过其它,n-1,个城市恰一次,最后回到出发城市,问如何走使得经过的总路程最短。,转化为图论问题：以城市为结点,两城市之间的路为边,路程长度为边上的权,则问题转化为在带权无向图,G=,中找一个权和最小的哈密尔顿回