离散数学一些特殊的图省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,第,8,章,一些特殊图,8.1,二部图,8.2,欧拉图,8.3,哈密顿图,8.4,平面图,1/36,1,8.1,二部图,二部图,完全二部图,匹配,极大匹配,最大匹配,匹配数,完备匹配,2/36,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,为,互补顶点子集,.,又若,G,是简单图,且,V,1,中每个顶点均与,V,2,中每个顶点都相,邻,则称,G,为,完全二部图,记为,K,r,s,其中,r,=|,V,1,|,s,=|,V,2,|.,(a),(b),以上两个图都是二部图，其中,(b),图是完全二部图。,3/36,3,例,完全二分图,K,m,n,=(V,1,V,2,E),共有,多少条边,?,解,因为,V,1,中每个顶点都与,V,2,中每个顶点相邻接,所以,V,1,中每个顶点关联,|V,2,|=n,条边,;,而,V,1,中有,m,个顶点,所以,K,m,n,共有,mn,条边,。,4/36,4,二部图判别法,定理,无向图,G,=,是二部图当且仅当,G,中,无奇圈。即,G,中每一条回路都是由偶,数条边组成。,证实：当,G(V,1,V,2,),是二部图时，,G,中任意一条回路各边必须往返于,V,1,V,2,之间，所以其回路必由偶数条边组成。,5/36,5,例：判断下列图是否为二部图。,解：图中每一条回路都是由偶数条边组成。所以此图为二部图。,6/36,6,匹配,设,G,=(V,E),是含有互补顶点子集,V,1,和,V,2,二,分图,M,E,若,M,中,任意两条边都不相邻,则称,M,为,G,中,匹配,(,对集,),。,假如,M,是,G,匹配,且,M,中再,加入任何一条边,就都是,不,匹配了,则称,M,为,极大匹配,。,最大匹配,:,边数最多匹配,匹配数,:,最大匹配中边数,记为,1,。,7/36,7,如在下列图中，假如用,a,1,a,2,a,3,a,4,表示,4,位教师，,b,1,b,2,b,3,表示三门待开课程。当某位教师能开某门课程时，则把它们对应顶点用边连接起来。假如要求一个教师只能担任一门课程，那么匹配,M,就表示了一个排课方案。为了使排课方案能最大程度地作到,“,各尽其能,”,，这就是最大匹配概念。,8/36,8,匹配,(,续,),设,M,为,G,中一个匹配,a,i,与,b,j,被,M,匹配,:(,a,i,b,j,),M,a,i,为,M,饱和点,:,M,中有边与,a,i,关联,a,i,为,M,非饱和点,:,M,中没有边与,a,i,关联,M,为完美匹配,:,G,每个顶点都是,M,饱和点,9/36,9,定义,设,G,=,为二部图,|,V,1,|,|,V,2,|,M,是,G,中最,大匹配,若,V,1,中顶点全是,M,饱和点,则称,M,为,G,中,V,1,到,V,2,完备匹配,.,当,|,V,1,|=|,V,2,|,时,完备匹配变成完美,匹配,.,(1),(2),(3),图中红边组成各图一个匹配，,(1),为完备,但不是完,美,;(2),不是完备,其实,(2),中无完备匹配,;(3),是完美,.,匹配,(,续,),例：如图,10/36,10,M,1,M,2,例 求下列图饱和点，并判断哪个图是完美匹配？,解：关于,M,1,a,b,e,d,是饱和点,f,c,是非饱和点,M,1,不是完美匹配,M,2,是完美匹配，所以,M,2,中,a,b,c,d,e,f,都是饱和点,。,11/36,11,设,G,=,V,1,V,2,E,是二部图，,M,是,G,一个匹配，假如对,G,任意匹配,M,，都有,|,M,|,M,|,，则,M,为,G,最大匹配,为了寻求二部图最大匹配，以下引进交替通路和增加通路两个概念。,定义 设,G,=,V,1,V,2,E,是二部图，,M,是,G,匹配，,P,是,G,中一条路，假如,P,是由,G,中属于,M,边和不属于,M,边交替组成，则称,P,为,GM,交替通路。假如交替通路始点和终点都是,M,非饱和点，则称为,GM,增加通路。,12/36,12,比如，在图中匹配,M,=,(,a,1,b,2,),(,a,2,b,3,),(,a,3,b,5,),，,路,L,1,：,a,1,b,2,a,2,b,3,a,3,，,L,2,：,a,2,b,3,a,3,b,5,a,4,，,L,3,：,b,1,a,3,b,5,a,4,，,L,4,：,b,1,a,1,b,2,a,2,b,3,a,3,b,5,a,4,都是,M,交替通路，其中后两条交替通路,L,3,和,L,4,始点和终点都是,M,非饱和点，所以这两条路是,M,增加通路。,13/36,13,设,G,=,V,1,V,2,E,是二部图，,M,是,G,一个匹配，,P,是,G,中一条,M,增加通路。把,P,中全部属于,M,边从,M,中去掉，而把,P,中全部不属于,M,边添加到,M,中，得到一个新边集,M,，则,M,也是一个匹配，其所含边数比匹配,M,所含边数多,1,。,14/36,14,比如在图中，把,M,增加通路,L,3,：,b,1,a,3,b,5,a,4,中属于,M,边,(,a,3,b,5,),从,M,中去掉，而把,L,3,中不属于,M,边,(,a,3,b,1,),和,(,a,4,b,5,),添加到,M,中，得到一个新边集,M,=,(,a,1,b,2,),(,a,2,b,3,),(,a,3,b,1,),(,a,4,b,5,),，显然,M,也是匹配且,M,边数比,M,边数多,l,，即,|,M,|,|,M,|+1,。,15/36,15,由此可见，利用增加通路能够增加匹配所含边数。不停地寻求,G,增加通路，直到再也找不到新增加通路，就可得到一个最大匹配。将这个结论写成以下定理。,定理,设,G,=,V,1,V,2,E,是二部图，,M,为,G,最大匹配充分必要条件是,G,中不存在,M,增加通路。,证实：设,M,为,G,最大匹配，下证,G,中不存在,M,可扩路。,假如,G,中存在一条,M,可扩路，则能够得到比,M,边数多,1,匹配，所以,M,不是最大匹配，矛盾。所以,G,中不存在,M,可扩路。,设,G,中不存在,M,可扩路，下证,M,为,G,最大匹配。,设,M,1,是最大匹配，证实,|,M,|=|,M,1,|,。,考查属于,M,而不属于,M,1,和属于,M,1,而不属于,M,中边，由这些边连同它们端点一起组成,G,子图,H,。,16/36,16,在子图,H,中，任一顶点至多与,M,中一条边关联且与,M,1,中一条边关联。因而任一顶点度数是,1,或,2,。故,H,连通分支是一条路，或者是一个回路。,假如,H,连通分支是一条路,P,，则它是,M,交替路，也是,M,1,交替路。假如,P,两个端点均与,M,中边关联，则,P,是,M,1,可扩路。由假设知，,M,1,是最大匹配，所以，不存在,M,1,可扩路，得到矛盾。假如,P,两个端点均与,M,1,边关联，那么,P,是一条,M,可扩路与题设矛盾。故,P,只能是一个端点与,M,中边关联，另一个端点与,M,1,中边关联，这么,P,中属于,M,边数与属于,M,1,边数相等。,17/36,17,假如,H,连通分支是一个回路，回路中边交替地属于,M,和,M,1,，因而属于,M,边数与属于,M,1,边数相等。,从上面能够看到，,H,中属于,M,边与属于,M,1,边数目相等。再加上既属于,M,又属于,M,1,边，能够得出：,M,中边数与,M,1,中边数相等。所以,M,是最大匹配。,18/36,18,有了上面准备以后，就能够深入讨论怎样在二部图中求最大匹配问题。,设,G,=,V,1,V,2,E,是二部图，通常先作,G,一个匹配,M,，再看,V,1,中有没有,M,非饱和点。假如没有，那么,M,必定是最大匹配；假如有，就从这些点出发找,M,增加通路。由,M,增加通路作出一个更大匹配。所以，在,G,中求最大匹配关键是寻找,M,增加通路。,19/36,19,寻找增加通路一个有效方法是标识法，其基本思想以下：,设,G,=,V,1,V,2,E,是二部图，在,G,中作一个匹配,M,，用,(,*,),标识,V,1,中全部,M,非饱和点，然后交替地进行以下和两步：,选一个,V,2,新标识过顶点，比如说,b,i,，用,(,b,i,),标识经过,M,中边与,b,i,邻接且还未标识过,V,1,全部顶点。对,V,2,全部新标识过顶点重复这一过程。,选一个,V,1,新标识过顶点，比如说,a,i,，用,(,a,i,),标识不经过,M,中边与,a,i,邻接且还未标识过,V,2,全部顶点。对,V,1,全部新标识过顶点重复这一过程。,20/36,20,直至标识到一个,V,2,中,M,非饱和点。从该顶点倒向追踪到标识有,(,*,),顶点，就得到了一个,M,增加通路。把,M,增加通路中全部属于,M,边从,M,中去掉，而把,M,可扩路中全部不属于,M,边添加到,M,中，得到一个新匹配,M,且其所含边数比匹配,M,所含边数多,1,。对,M,重复上述过程，,，直到,G,中已不存在增加通路，此时匹配就是最大匹配。,21/36,21,【,例,】,如图是二部图，求其最大匹配。,a,1,a,2,a,3,a,4,b,1,b,2,b,3,b,4,b,5,22/36,22,【,例,】,如图是二部图，求其最大匹配。,23/36,23,解：,取二部图一个匹配,M,=,(,a,3,b,1,),(,a,5,b,2,),。用,(,*,),标识,V,1,中全部,M,非饱和点,a,1,a,2,a,4,。,选,V,1,新标识过顶点,a,1,，用,(,a,1,),标识不经过,M,边与,a,1,邻接且还未标识过,V,2,顶点,b,1,；类似地用,(,a,2,),标识,b,2,。,选,V,2,新标识过顶点,b,1,，用,(,b,1,),标识经过,M,边与,b,1,邻接且还未标识过,V,1,顶点,a,3,；类似地用,(,b,2,),标识,a,5,。,24/36,24,选,V,1,新标识过顶点,a,3,，因为不存在不经过,M,边与,a,3,邻接,V,2,顶点，所以不用,(,a,3,),标识,V,2,顶点；用,(,a,5,),标识,b,3,或,b,4,，假定用,(,a,5,),标识,b,3,。如图所表示。,b,3,是,M,非饱和点，标识结束。,从,b3,倒向追踪到标识有,(,*,),顶点，就得到了,M,增加通路：,a,4,b,2,a,5,b,3,或,a,2,b,2,a,5,b,3,，取后者。把,M,增加通路,a,2,b,2,a,5,b,3,中边,(,a,5,b,2,),从,M,中去掉，而把,(,a,2,b,2,),和,(,a,5,b,3,),添加到,M,中得到新匹配,M,=,(,a,3,b,1,),(,a,2,b,2,),(,a,5,b,3,),，如图,9.61,所表示。,25/36,25,26/36,26,对匹配,M,=,(,a,3,b,1,),(,a,2,b,2,),(,a,5,b,3,),再用标识法：,用,(,*,),标识,V,1中全部,M,非饱和点,a,1,和,a,4,。,选,V,1,新标识过顶点,a,1,，用,(,a,1,),标识不经过,M,边与,a,1,邻接且还未标识过,V,2,全部顶点,b,1,；再用,(,a,4,),标识,b,2,。,选,V,2,新标识过顶点,b,1,，用,(,b,1,),标识经过,M,边与,b,1,邻接且还未标识过,V,1,全部顶点,a,3,；再用,(,b,2,),标识,a,2,。,选,V,1,新标识过顶点,a,2,和,a,3,，,V,2,中已无可标识顶点。,图中已不存在增加通路，所以,M,就是最大匹配。,27/36,27,【,例,】,求下列图最大匹配。,28/36,28,解：,取二部图图9.62,一个匹配,M,=,(,a,2,b,2,),(,a,3,b,3,),(,a,5,b,5,),。用,(,*,),标识,V,1,中全部,M,非饱和点,a,1,a,4,。,选,V,1,新标识过顶点,a,1,，用,(,a,1,),标识,b,2,和,b,3,。,选,V,2,新标识过顶点,b,2,和,b,3,，用,(,b,2,),标识,a,2,，用,(,b,3,),标识,a,3,。,选,V,1,新标识过顶点,a,2,，用,(,a,2,),标识,b,1,b,4,和,b,5,。,因为,b,1,和,b,4,都是,M,非饱和点，说明找到了,M,可扩路。它们是：,a,1,b,2,a,2,b,4,和,a,1b,2,a,2,b,1,。选前者，把边,(,a,2,b,2,),从,M,中去掉，而把,(,a,1,b,2,),和,(,a,2,b,4,),添加到,M,中，得到新匹配,M,=,(,a,1,b,2,),(,a,2,b,4,),(,a,3,b,3,),(,a,5,b,5,),，如图,9.63,所表示。,对于匹配,M,=,(,a,1,b,2,),(,a,2,b,4,),(,a,3,b,3,),(,a,5,b,5,),重复上述过程，已找不到,M,可扩路。所以,M,就是最大匹配。,29/36,29,30/36,30,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),没有完备匹配,.,Hall,定理中条件称为“,相异性条件,”,31/36,31,定理,设二部图,G,=,中,假如存在,t,1,使得,(1),V,1,中每个顶点最少关联,t,条边,(2),而,V,2,中每个顶点至多关联,t,条边，则,G,中存在,V,1,到,V,2,完备匹配,.(,充分条件,),证实,假如,(1),成立,则与,V,1,中,k(1k|V,1,|),个顶点相关联边总数,最少是,kt,条。依据,(2),这些边最少要与,V,2,中,k,个顶点相关联。,这就得出,V,1,中每,k(1k|V,1,|),个顶点,最少,邻接到到,V,2,中,k,个顶点。,定理中条件称为,t,条件,.,满足,t,条件二部图一定满足相异性条件,.,32/36,32,所以，当给出一个二分图后。判断,G,中存在从,V,1,到,V,2,完备匹配方法,:,先找出,V,中每个结点度数，令,r,min,v,V1,d(v),。,再找出,V,中每个结点度数，令,R,max,v,V2,d(v),。,若,r,R,，,则问题有解，取,t,为,r,即可。但这只是充分条件，若不满足，则还要用充要条件来判断。,33/36,33,图,9.64,中二部图满足,t,条件。其中,t,=3,。所以在图,9.64,中存在,V,1,到,V,2,完备匹配。,34/36,34,一个应用实例,例 某课题组要从,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,种方案,).,35/36,35,练习：,1.,某单位按编制有,7,个空缺：,p,1,p,2,.p,7,.,有,10,个申请者：,a,1,a,2,.a,10,.,他们合格工作岗位依次为：,p,1,p,5,p,6,p,2,p,6,p,7,p,3,p,4,p,1,p,5,p,6,p,7,p,3,p,2,p,3,p,1,p,3,p,1,p,5,，怎样安排他们工作，使有工作人最多。,2.,某单位有,6,个未婚女子,L,1,L,2,L,6,和,6,个未婚男子,g,1,g,2,g,6,每个人都有意中人，,L1:g,1,g,2,g,4,L,2,:g,3,g,5,L,3,:g,1,g,2,g,4,L,4,:g,2,g,5,g,6,L,5,:g,5,g,6,L,6,:g,3,g,5,g,6,;,而,g,1,:L,1,L,3,L,6,g,2,:L,2,L,4,L,6,g,3,:L,2,L,5,g,4,:L,1,L,3,g,5,:L,2,L,6,g,6,:L,3,L,4,L,5,请问怎样匹配，使男女双方都有满意婚姻且结婚对数最多。,36/36,36,