*****第6章特殊的图6.1二部图6.2欧拉图6.3哈密顿图6.4平面图*6.1二部图二部图完全二部图匹配极大匹配,最大匹配,完美匹配,完备匹配Hall定理*二部图定义设无向图G=V,E,若能将V划分成V1和V2(V1?V2=V,V1?V2=?),使G中每边的两端点一个属V1,另一个属于V2,则称G为二部图,这时可记G为V1,V2,E,并称V1和V2为互补顶点子集.又若G是单图,且V1中每顶都与V2中每顶相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.注意:n阶零图为二部图.*二部图(续)例下述各图是否是二部图?定理无向图G=V,E是二部图当且仅当G中无奇圈不是*匹配设G=V,E,匹配(边独立集):任2条边均不相邻的边子集极大匹配:添加任一条边后都不再是匹配的匹配最大匹配:边数最多的匹配G的匹配数:最大匹配中的边数,记为?1例极大匹配最大匹配?1=3*匹配(续)设M为G中一个匹配，有以下概念：vi与vj被M匹配——(vi,vj)?Mv为M饱和点——M中有边与v关联v为M非饱和点——M中没有边与v关联M为完美匹配——G的每个顶都是M饱和点例关于M1，a,b,e,d是饱和点f,c是非饱和点M1不是完美匹配M2是完美匹配M1M2*二部图中的匹配定义设G=V1,V2,E为二部图,|V1|?|V2|,M是G中最大匹配,若V1中顶点全是M饱和点,则称M为G中V1到V2的完备匹配.当|V1|=|V2|时,完备匹配变成完美匹配.例完备,不完美不完备完美*Hall定理定理(Hall定理)设二部图G=V1,V2,E中，|V1|?|V2|.G中存在从V1到V2的完备匹配当且仅当V1中任意k个顶点至少与V2中的k个顶点相邻(k=1,2,…,|V1|).?相异性条件由Hall定理,上一页第2个图没有完备匹配.定理设二部图G=V1,V2,E中,如果存在t?1,使得V1中每个顶点至少关联t条边,而V2中每个顶点至多关联t条边，则G中存在V1到V2的完备匹配.?t条件（充分非必要）证V1中任意k个顶点至少关联kt条边,这kt条边至少关联V2中的k个顶点,即V1中任意k个顶点至少邻接V2中的k个顶点.由Hall定理,G中存在V1到V2的完备匹配.*一个应用实例例某课题组要从a,b,c,d,e5人中派3人分别到上海、广州、香港去开会.已知a只想去上海，b只想去广州，c,d,e都表示想去广州或香港.问该课题组在满足个人要求的条件下，共有几种派遣方案？解令G=V1,V2,E,其中V1={s,g,x},V2={a,b,c,d,e},E={(u,v)|u?V1,v?V2,v想去u},其中s,g,x分别表示上海、广州和香港.G满足相异性条件，红边是一个完备匹配,对应的派遣方案:a?上海,b?广州,d?香港*6.2欧拉图欧拉通路与欧拉回路存在欧拉通路和欧拉回路的充要条件*哥尼斯堡七桥问题要求边不重复地一笔画出整个图*欧拉图欧拉通路:图中行遍所有顶点且恰好经过每条边一次的通路.欧拉回路:图中行遍所有顶点且恰好经过每条边一次的回路.欧拉图:有欧拉回路的图.半欧拉图:有欧拉通路，但无欧拉回路的图.几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图.欧拉通路是简单通路,欧拉回路是简单回路.环不影响图的欧拉性.*欧拉图实例例是否是欧拉图或半欧拉图?欧拉图欧拉图半欧拉图半欧拉图不是不是*欧拉图的判别法定理无向图G为欧拉图当且仅当G连通且无奇度顶点.G是半欧拉图当且仅当G连通且恰有两个奇度顶点.定理有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.D是半欧拉图当且仅当D连通且恰有两个奇度顶点,其中一个入度比出度大1,另一个出度比入度大1,其余顶点的入度等于出度.*实例例1哥尼斯堡七桥问题4个奇度顶点,不存在欧拉通路,更不存在欧拉回路,例2下面两个图都是欧拉图.从A点出发,如何一次成功地走出一条欧