《离散数学》特殊图-1.ppt

《《离散数学》特殊图-1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章一些特殊的图8.1二部图8.2欧拉图8.3哈密顿图8.4平面图18.1二部图二部图完全二部图匹配极大匹配最大匹配匹配数完备匹配2二部图定义设无向图G=,若能将V分成V1和V2(V1V2=V,V1V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图（二分图）,记为,称V1和V2为互补顶点子集.若V1中每个顶点均与V2中每个顶点有且只有一条边相关联,则称二部图G为完全二部图,记为Kr,sr=

2、V1

3、,s=

4、V2

5、.注意:n阶零图（

6、E

7、＝0）为二部图.3二部图的判别法定

8、理无向图G=是二部图当且仅当G中无奇数长度的回路（无奇圈）.例：述各图都是二部图4匹配设G=为无向图,E*E匹配(边独立集):任2条均不相邻的边组成的边子集任2条边的端点都不一样极大匹配:添加任一条边后都不再是匹配的匹配最大匹配:边数最多的极大匹配匹配数:最大匹配中的边数,记为1最大匹配的边数不超过

9、V

10、的一半例3个图的匹配数依次为3,3,4.5匹配(续)设M为G中一个匹配，vV(G)v为M饱和点:M中有边与v关联v为M非饱和点:M中没有边与v关联M为完美匹配:G的每个顶点都是M饱和点所有点都在匹配边上完美匹

11、配是最大匹配例关于M1,a,b,e,d是饱和点f,c是非饱和点M1不是完美匹配M2是完美匹配M1M26二部图中的匹配定义设G=为二部图,M是G中最大匹配,若

12、M

13、＝min{

14、V1

15、，

16、V2

17、}，则称M为G中的一个完备匹配V1或V2的任意节点都是M中边的端点M是完备匹配，

18、V1

19、

20、V2

21、则称M为V1到V2的一个完备匹配.当

22、V1

23、=

24、V2

25、时,完备匹配变成完美匹配.两部分一对一最大匹配一定存在，完备匹配不一定存在7二部图中的匹配(1)(2)(3)例图中红边组成各图的一个匹配，(1)为完备的,但不是完美的;(2)不是完

26、备的,其实(2)中无完备匹配;(3)是完美的.8Hall定理定理(Hall定理)设二部图G=中，

27、V1

28、

29、V2

30、.G中存在从V1到V2的完备匹配当且仅当V1中任意k个顶点至少与V2中的k个顶点相邻(k=1,2,…,

31、V1

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

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

34、uV1,vV2,v想去u},其中s,g,x分别表示上海、广州和香港.G如图所示.G满足相异性条件，因而可给出派遣方案，共有9种派遣方案(请给出这9种方案).10上图是二部图，满足t条件（t＝2），存在V1到V2的完备匹配1

35、18.2欧拉图－－一笔画问题欧拉通路欧拉回路欧拉图半欧拉图12哥尼斯堡七桥问题欧拉图是能一笔画出的边不重复的回路.13欧拉图欧拉通路:经过图中每条边一次且仅一次，并且行遍图中每个顶点的通路.欧拉回路:经过图中每条边一次且仅一次，并且行遍图中每个顶点的回路欧拉图:有欧拉回路的图.几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图.欧拉通路是简单通路,欧拉回路是简单回路.环不影响图的欧拉性.14一笔画问题笔不离开纸，每边只能画一次，不允许重复，将图画出，称该图能一笔画。如终点回到起点，则等价于该图存在欧拉回路如终点不是起点，则等

36、价于该图仅存在欧拉通路如该图不能一笔画，则等价于该图不存在欧拉通路和欧拉回路。15ABCDABDCBFCEHADG图a不是一笔画，它不是欧拉图，也不存在欧拉通路；图b能完成起点和终点不同的一笔画，存在欧拉通路ACFEBCDGFH，但不存在欧拉回路，不是欧拉图；图c能完成起点与终点相同的的一笔画，存在欧拉回路，它是欧拉图。16欧拉图(续)例图中,(1),(4)为欧拉图;(2),(5)为欧拉通路;(3)，(6)既不是欧拉图,也不是欧拉通路.在(3),(6)中各至少加几条边才能成为欧拉图?17欧拉图的判别法定理无向图G为欧拉图当且仅当G连通

37、且无奇度顶点.无向图G是欧拉通路当且仅当G连通且恰有两个奇度顶点.定理有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.有向图D具有欧拉通路当且仅当D连通且恰有两个奇度顶点,其中一个入度比出度大1,另一个出度比入