离散数学一些特殊的图.ppt

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