是离散数学

1第6章特殊的图6.1二部图6.2欧拉图6.3哈密顿图6.4平面图26.1二部图二部图完全二部图匹配极大匹配,最大匹配,完美匹配,完备匹配Hall定理3二部图定义设无向图G=V,E,若能将V划分成V1和V2(V1V2=V,V1V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为V1,V2,E,称V1和V2为互补顶点子集.又若G是简单图,且V1中每个顶点都与V2中每个顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.注意:n阶零图为二部图.4二部图(续)例下述各图是否是二部图?定理无向图G=V,E是二部图当且仅当G中无奇圈不是5匹配设G=V,E,匹配(边独立集):任2条边均不相邻的边子集极大匹配:添加任一条边后都不再是匹配的匹配最大匹配:边数最多的匹配匹配数:最大匹配中的边数,记为1例极大匹配最大匹配1=3例下述3个图的匹配数依次为3,3,4.67匹配(续)设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是完美匹配M1M28二部图中的匹配定义设G=V1,V2,E为二部图,|V1||V2|,M是G中最大匹配,若V1中顶点全是M饱和点,则称M为G中V1到V2的完备匹配.当|V1|=|V2|时,完备匹配变成完美匹配.例完备,不完美不完备完美9Hall定理定理(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的完备匹配.10一个应用实例例某课题组要从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满足相异性条件，因而可给出派遣方案，共有9种派遣方案(请给出这9种方案).红边是一个完备匹配,对应的派遣方案:a上海,b广州,d香港116.2欧拉图欧拉通路与欧拉回路存在欧拉通路和欧拉回路的充分必要条件12哥尼斯堡七桥问题要求边不重复地一笔画出整个图13欧拉图欧拉通路:图中行遍所有顶点且恰好经过每条边一次的通路.欧拉回路:图中行遍所有顶点且恰好经过每条边一次的回路.欧拉图:有欧拉回路的图.半欧拉图:有欧拉通路,但无欧拉回路的图.几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图.欧拉通路是简单通路,欧拉回路是简单回路.环不影响图的欧拉性.14欧拉图实例例是否是欧拉图或半欧拉图?欧拉图欧拉图半欧拉图半欧拉图不是不是15欧拉图的判别法定理无向图G为欧拉图当且仅当G连通且无奇度顶点.G是半欧拉图当且仅当G连通且恰有两个奇度顶点.定理有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.D是半欧拉图当且仅当D连通且恰有两个奇度顶点,其中一个入度比出度大1,另一个出度比入度大1,其余顶点的入度等于出度.16实例例1哥尼斯堡七桥问题4个奇度顶点,不存在欧拉通路,更不存在欧拉回路,例2下面两个图都是欧拉图.从A点出发,如何一次成功地走出一条欧拉回路来？应用实例例设旋转磁鼓分成8个扇区,每个扇区标记一个0或1,有3个探测器能够读出连续的3个扇区的标记.如何赋给扇区标记,使得能够根据探测器的读数确定磁鼓的位置.为了能够根据读数确定磁鼓的位置,必须构造一个由8个0和1组成的圆环,使得圆环上连续3个数字的序列都不相同.1700011111应用实例(续)构造一个4阶有向图,8条边的标记是不同的,图中存在一条欧拉回路:000,001,011,111,110,101,010,100.在这条回路上连续3条边的标记的第一位恰好与第一条边的标记相同.顺着这条回路取每一条边标记的第一位得到00011101,按照这个顺序标记磁鼓的扇区.1800011011000001011010100101110111196.3哈密顿图哈密顿通路和哈密顿回路存在哈密顿通路和哈密顿回路的充分条件与必要条件格雷码20哈密顿周游世界问题每个顶点是一个城市,有20个城市,要求从一个城市出发,恰好经过每一个城市一次,回到出发点.21哈密顿图的定义哈密顿通路:经过图中所有顶点一次且仅一次的通路.哈密顿回路:经过图中所有顶点一次且仅一次的回路.哈密顿图:具有哈密顿回路的图.半哈密顿图:具有哈密顿通路而无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响图的哈密顿性.22实例例是否是哈密顿图,半哈密顿图?哈密顿图哈密顿图半哈密顿图不是23无向哈密顿图的一个必要条件定理设无向图G=V,E是哈密顿图,则对于任意V1V且V1,均有p(GV1)|V1|.证设C为G中一条哈密顿回路,有p(CV1)|V1|.又因为CG,故p(GV1)p(CV1)|V1|.几点说明定理中的条件是哈密顿图的必要条件,但不是充分条件.可利用该定理判断某些图不是哈密顿图.由定理可知,Kr,s当sr+1时不是哈密顿图.当r2时,Kr,r是哈密顿图,而Kr,r+1是半哈密顿图.24实例例设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.证(1)设v为割点,则p(Gv)2|{v}|=1.根据定理,G不是哈密顿图.(2)若G是K2(K2有桥),它显然不是哈密顿图.除K2外,其他的有桥连通图均有割点.由(1),得证G不是哈密顿图.25无向哈密顿图的一个充分条件定理设G是n阶无向简单图,若任意两个不相邻的顶点的度数之和大于等于n1,则G中存在哈密顿通路.当n3时,若任意两个不相邻的顶点的度数之和大于等于n,则G中存在哈密顿回路.由定理,当n3时,Kn均为哈密顿图.定理中的条件是充分条件,但不是必要条件.例如,n(6)个顶点的路径存在哈密顿通路,但不满足条件.n(5)个顶点的圈是哈密顿图,不满足条件.26判断是否是哈密顿图的可行方法观察出一条哈密顿回路例如右图(周游世界问题)中红边给出一条哈密顿回路,故它是哈密顿图.满足充分条件例如当n3时,Kn中任何两个不同的顶点u,v,均有d(u)+d(v)=2(n1)n,所以Kn为哈密顿图.27判断是否是哈密顿图的可行方法(续)例44国际象棋盘上的跳马问题:马是否能恰好经过每一个方格一次后回到原处?解每个方格看作一个顶点,2个顶点之间有边当且仅当马可以从一个方格跳到另一个方格,得到16阶图G,如左图红边所示.取V1={a,b,c,d},则p(GV1)=6|V1|,见右图.由定理,图中无哈密顿回路,故问题无解.在88国际象棋盘上,跳马问题是否有解?不满足必要条件判断是否为哈密顿图是NP完全的28应用实例例某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？解作无向图G=V,E,其中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中相邻关系安排座位即可.竞赛图竞赛图:任意两个顶点之间恰好有一条有向边.在循环赛中,n个参赛队中的任意两个队比赛一次,假设没有平局,用有向图描述比赛结果:顶点表示参赛队,A到B有一条边当且仅当A队胜B队.29ABCD竞赛图(续)定理在n(n≥2)阶有向图D中,如果所有有向边均用无向边代替,所得无向图中含生成子图Kn,则有向图D中存在哈密顿通路.根据定理,竞赛图中一定有哈密顿通路,当然也可能有哈密顿回路.当没有哈密顿回路时,通常只有一条哈密顿通路,这条通路给出参赛队的惟一名次.例如,CABD是一条哈密顿通路,它没有哈密顿回路,比赛结果是C第一,A第二B,C第三,D第四.30格雷码(graycode)为了确定圆盘停止旋转后的位置,把圆盘划分成2n个扇区,每个扇区分配一个n位0-1串.要用某种电子装置读取扇区的赋值.当圆盘停止旋转后,如果电子装置处于一个扇区的内部,它将能够正确的读出这个扇区的赋值,如果电子装置恰好处于两个扇区的边界上,就可能出问题.如何赋值,才能将可能出现的误差减少到最小?31100011010111101000001110格雷码(续)格雷码:相邻的两个以及最后一个和第一个之间只有一位不同的把n位0-1串序列例如,000,001,011,010,110,111,101,100是一个格雷码构造n维立方体图:2n个顶点,每个顶点表示一个n位串,两个顶点之间有一条边当且仅当它们的n位串仅相差一位.当n2时,图中一定存在哈密顿回路.3200110111101100010001011001001110