离散完整ppt课件8.13.ppt

《离散完整ppt课件8.13.ppt》由会员分享，可在线阅读，更多相关《离散完整ppt课件8.13.ppt（26页珍藏版）》请在优知文库上搜索。

1、1第第8章章 一些特殊的图一些特殊的图 8.1 二部图二部图8.2 欧拉图欧拉图8.3 哈密顿图哈密顿图8.4 平面图平面图 28.1 二部图二部图 二部图二部图完全二部图完全二部图匹配匹配极大匹配极大匹配最大匹配最大匹配匹配数匹配数完备匹配完备匹配 3二部图二部图 定义定义 设无向图设无向图 G=,若能将若能将V 划分成划分成V1 和和 V2(V1 V2=V,V1 V2=),使得使得G中的每条边的两个端中的每条边的两个端点都一个属于点都一个属于V1,另一个属于另一个属于V2,则称则称G为为二部图二部图,记为记为,称称V1和和V2为为互补顶点子集互补顶点子集.又若又若G是简单图是简单图,且且V

2、1中每个顶点都与中每个顶点都与V2中每个顶点相邻中每个顶点相邻,则称则称G为为完全二部图完全二部图,记为记为Kr,s,其中其中r=|V1|,s=|V2|.注意注意:n 阶零图为二部图阶零图为二部图.4二部图的判别法二部图的判别法 定理定理 无向图无向图G=是二部图当且仅当是二部图当且仅当G中无奇圈中无奇圈 例例 下述各图都是二部图下述各图都是二部图 5匹配匹配 设设G=,匹配匹配(边独立集边独立集):任任2条边均不相邻的边子集条边均不相邻的边子集极大匹配极大匹配:添加任一条边后都不再是匹配的匹配添加任一条边后都不再是匹配的匹配最大匹配最大匹配:边数最多的匹配边数最多的匹配匹配数匹配数:最大匹配

3、中的边数最大匹配中的边数,记为记为 1 例例 下述下述3个图的匹配数个图的匹配数 依次为依次为3,3,4.6匹配匹配(续续)设设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是完美匹配是完美匹配M1M27二部图中的匹配二部图中的匹配 定义定义 设设G=为二部图为二部图,|V1|V2

4、|,M是是G中最中最大匹配大匹配,若若V1中顶点全是中顶点全是M饱和点饱和点,则称则称M为为G中中V1到到V2的的完备匹配完备匹配.当当|V1|=|V2|时时,完备匹配变成完美完备匹配变成完美匹配匹配.(1)(2)(3)例例 图中红边组成各图的一个匹配，图中红边组成各图的一个匹配，(1)为完备的为完备的,但不是完但不是完美的美的;(2)不是完备的不是完备的,其实其实(2)中无完备匹配中无完备匹配;(3)是完美的是完美的.8Hall定理定理 定理定理(Hall定理定理)设二部图设二部图G=中，中，|V1|V2|.G中存中存在从在从V1到到V2的完备匹配当且仅当的完备匹配当且仅当V1中任意中任意k

5、 个顶点至少与个顶点至少与V2中的中的k个顶点相邻个顶点相邻(k=1,2,|V1|).由由Hall定理不难证明定理不难证明,上一页图上一页图(2)没有完备匹配没有完备匹配.定理定理 设二部图设二部图G=中中,如果存在如果存在t 1,使得使得V1中每个中每个顶点至少关联顶点至少关联 t 条边条边,而而V2中每个顶点至多关联中每个顶点至多关联t条边，则条边，则G中存在中存在V1到到V2的完备匹配的完备匹配.Hall定理中的条件称为定理中的条件称为“相异性条件相异性条件”,第二个定理中的条第二个定理中的条件件称为称为 t 条件条件.满足满足 t 条件的二部图一定满足相异性条件条件的二部图一定满足相异

6、性条件.9一个应用实例一个应用实例 例例 某课题组要从某课题组要从a,b,c,d,e 5人中派人中派3人分别到上海、广州、人分别到上海、广州、香港去开会香港去开会.已知已知a只想去上海，只想去上海，b只想去广州，只想去广州，c,d,e都都 表示想去广州或香港表示想去广州或香港.问该课题组在满足个人要求的条件问该课题组在满足个人要求的条件下，共有几种派遣方案？下，共有几种派遣方案？解解 令令G=,其中其中V1=s,g,x,V2=a,b,c,d,e,E=(u,v)|u V1,v V2,v想去想去u,其中其中s,g,x分别表示上海、广州和香港分别表示上海、广州和香港.G如图所示如图所示.G 满足相异

7、性条件，因而可给满足相异性条件，因而可给出派遣方案，共有出派遣方案，共有9种派遣方案种派遣方案(请给出这请给出这9种方案种方案).108.2 欧拉图欧拉图欧拉通路欧拉通路欧拉回路欧拉回路欧拉图欧拉图半欧拉图半欧拉图 11哥尼斯堡七桥问题哥尼斯堡七桥问题 欧拉图是能一笔画出的边不重复的回路欧拉图是能一笔画出的边不重复的回路.12欧拉图欧拉图 欧拉通路欧拉通路:图中行遍所有顶点且恰好经过每条边一次的通路图中行遍所有顶点且恰好经过每条边一次的通路.欧拉回路欧拉回路:图中行遍所有顶点且恰好经过每条边一次的回路图中行遍所有顶点且恰好经过每条边一次的回路.欧拉图欧拉图:有欧拉回路的图有欧拉回路的图.半欧拉

8、图半欧拉图:有欧拉通路而无欧拉回路的图有欧拉通路而无欧拉回路的图.几点说明：几点说明：上述定义对无向图和有向图都适用上述定义对无向图和有向图都适用.规定平凡图为欧拉图规定平凡图为欧拉图.欧拉通路是简单通路欧拉通路是简单通路,欧拉回路是简单回路欧拉回路是简单回路.环不影响图的欧拉性环不影响图的欧拉性.13欧拉图欧拉图(续续)例例 图中图中,(1),(4)为欧拉图为欧拉图;(2),(5)为半欧拉图为半欧拉图;(3)，(6)既不既不 是欧拉图是欧拉图,也不是半欧拉图也不是半欧拉图.在在(3),(6)中各至少加几条边才能成为欧拉图中各至少加几条边才能成为欧拉图?14欧拉图的判别法欧拉图的判别法 定理定

9、理 无向图无向图G为欧拉图当且仅当为欧拉图当且仅当G连通且无奇度顶点连通且无奇度顶点.无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G连通且恰有两个奇度顶点连通且恰有两个奇度顶点.定理定理 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D连通且每个顶点的入度都连通且每个顶点的入度都等于出度等于出度.有向图有向图D具有欧拉通路当且仅当具有欧拉通路当且仅当D连通且恰有两个奇度顶连通且恰有两个奇度顶点点,其中一个入度比出度大其中一个入度比出度大1,另一个出度比入度大另一个出度比入度大1,其余其余顶点的入度等于出度顶点的入度等于出度.15实例实例例例1 哥尼斯堡七桥问题哥尼斯堡七桥问题例例2 下面

10、两个图都是欧拉图下面两个图都是欧拉图.从从A点出发点出发,如何一次成功地走出一条欧拉回路来？如何一次成功地走出一条欧拉回路来？168.3 哈密顿图哈密顿图 哈密顿通路哈密顿通路哈密顿回路哈密顿回路哈密顿图哈密顿图半哈密顿图半哈密顿图 17哈密顿周游世界问题哈密顿周游世界问题 18哈密顿图的定义哈密顿图的定义哈密顿通路哈密顿通路:经过图中所有顶点一次且仅一次的通路经过图中所有顶点一次且仅一次的通路.哈密顿回路哈密顿回路:经过图中所有顶点一次且仅一次的回路经过图中所有顶点一次且仅一次的回路.哈密顿图哈密顿图:具有哈密顿回路的图具有哈密顿回路的图.半哈密顿图半哈密顿图:具有哈密顿通路而无哈密顿回路的

11、图具有哈密顿通路而无哈密顿回路的图.几点说明：几点说明：平凡图是哈密顿图平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响图的哈密顿性环与平行边不影响图的哈密顿性.19实例实例例例 图中图中,(1),(2)是哈密顿图是哈密顿图;(3)是半哈密顿图是半哈密顿图.(4)既不是哈密顿图既不是哈密顿图,也不是半哈密顿图，为什么？也不是半哈密顿图，为什么？20无向哈密顿图的一个必要条件无向哈密顿图的一个必要条件 定理定理 设无向图设无向图G=是哈密顿图是哈密顿图,则对于任意则对于任意V1 V且且V1,均有均有 p(G V1)|V1|.

12、证证 设设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是半哈密顿图是半哈密顿图.21实例实例例例 设设G为为n阶无向连通简单图阶无向连通简单图,若若G中有割点或桥中有割点或桥,则则G不是哈密顿

13、图不是哈密顿图.证证 (1)设设v为割点为割点,则则p(G v)2|v|=1.根据定理根据定理,G不是哈密顿图不是哈密顿图.(2)若若G是是K2(K2有桥有桥),它显然不是哈密顿图它显然不是哈密顿图.除除K2外外,其他的有桥连通图均有割点其他的有桥连通图均有割点.由由(1),得证得证G不是不是哈密顿图哈密顿图.22无向哈密顿图的一个充分条件无向哈密顿图的一个充分条件 定理定理 设设G是是n阶无向简单图阶无向简单图,若任意两个不相邻的顶点若任意两个不相邻的顶点的度数之和大于等于的度数之和大于等于n 1,则则G中存在哈密顿通路中存在哈密顿通路.当当n 3时时,若任意两个不相邻的顶点的度数之和大若任

14、意两个不相邻的顶点的度数之和大于等于于等于n,则则G中存在哈密顿回路中存在哈密顿回路,从而从而G为哈密顿为哈密顿图图.23哈密顿通路哈密顿通路(回路回路)的存在性的存在性(续续)定理中的条件是存在哈密顿通路定理中的条件是存在哈密顿通路(回路回路)的充分条的充分条件件,但不是必要条件但不是必要条件.例如例如,设设G为长度为为长度为n 1(n 4)的路径的路径,它不满足定理它不满足定理中哈密顿通路的条件中哈密顿通路的条件,但它显然存在哈密顿通路但它显然存在哈密顿通路.设设G是长为是长为n的圈的圈,它不满足定理中哈密顿回路的条它不满足定理中哈密顿回路的条件件,但它显然是哈密顿图但它显然是哈密顿图.由

15、定理由定理,当当n 3时时,Kn均为哈密顿图均为哈密顿图.判断某图是否为哈密顿图至今还是一个难题判断某图是否为哈密顿图至今还是一个难题 24判断是否是哈密顿图判断是否是哈密顿图的可行方法的可行方法n观察出一条哈密顿回路观察出一条哈密顿回路 例如例如 右图右图(周游世界问题周游世界问题)中红中红边给出一条哈密顿回路边给出一条哈密顿回路,故它故它是哈密顿图是哈密顿图.注意注意,此图不满足定理的条件此图不满足定理的条件.n满足充分条件满足充分条件例如例如 当当n 3时时,Kn中任何两个不同的顶点中任何两个不同的顶点 u,v,均均有有d(u)+d(v)=2(n 1)n,所以所以Kn为哈密顿图为哈密顿图

16、.25判断是否是哈判断是否是哈 密顿图密顿图的可行方法的可行方法(续续)例例 4 4国际象棋盘上的跳马问国际象棋盘上的跳马问题题:马是否能恰好经过每一个马是否能恰好经过每一个方格一次后回到原处方格一次后回到原处?解解 每个方格看作一个顶点每个方格看作一个顶点,2个个顶点之间有边当且仅当马可以从一个方格跳到另一个方格顶点之间有边当且仅当马可以从一个方格跳到另一个方格,得到得到16阶图阶图G,如左图红边所示如左图红边所示.取取V1=a,b,c,d,则则p(G V1)=6|V1|,见右图见右图.由定理由定理,图中无哈密顿回路图中无哈密顿回路,故问题无解故问题无解.在在8 8国际象棋盘上国际象棋盘上,跳马问题是否有解跳马问题是否有解?不满足必要条件不满足必要条件26应用实例应用实例例例 某次国际会议某次国际会议8人参加，已知每人至少与其余人参加，已知每人至少与其余7人中人中的的4人有共同语言，问服务员能否将他们安排在同一张人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？圆桌就座，使得每个人都能与两边的人交谈？解解 图是描述事物之间关系的最好的手段之一图是描述