离散数学课件 图论7

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

1、第十八章匹配与着色主要内容二部图二部图中的匹配点着色地图着色与平面图的点着色边着色SchoolofInformationScienceandEngineering18.1二部图[定义1]设G=为一个无向图，若能将V分成V1和V2(V1V2=V，V1V2=)，使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图(或称二分图、偶图等)，称V1和V2为互补顶点子集，常将二部图G记为.又若G是简单二部图，V1中每个顶点均与V2中所有的顶点相邻，则称G为完全二部图，记为Kr,s，其中r=

2、V1

3、，s=

4、V2

5、.注意，n阶零图为二

6、部图.SchoolofInformationScienceandEngineering二部图的判别法[判定定理]无向图G=是二部图当且仅当G中无长度为奇数的圈。由定理可知图9中各图都是二部图，哪些是完全二部图？哪些图是同构的？SchoolofInformationScienceandEngineering[定义2]设G=,E*E，(1)匹配(边独立集)E*——E*中各边均不相邻(2)极大匹配E*——E*中不能再加其他边了(3)最大匹配——边数最多的匹配(4)匹配数——最大匹配中的边数，记为1上图中各图的匹配数依次为3,3,4.18.2二部图中的匹配S

7、choolofInformationScienceandEngineering关于匹配中的其他概念[定义3]设M为G中一个匹配.(1)vi与vj被M匹配——(vi,vj)M(2)v为M饱和点——有M中边与v关联(3)v为M非饱和点——无M中边与v关联(4)M为完美匹配——G中无M非饱和点(5)M的交错路径——从M与EM中交替取边构成的G中路径(6)M的可增广交错路径——起、终点都是M非饱和点的交错路径(7)M的交错圈——由M与EM中的边交替出现构成的G中圈上图中，只有第一个图存在完美匹配SchoolofInformationScienceandEngineering1

8、8.2二部图中的匹配[定义4]设G=为二部图，

9、V1

10、

11、V2

12、，M是G中最大匹配，若V1中顶点全是M饱和点，则称M为G中完备匹配.

13、V1

14、=

15、V2

16、时完备匹配变成完美匹配.图中，红边组成各图的一个匹配，(1)中为完备匹配，(2)中匹配不是完备的，(2)中无完备匹配，(3)中匹配是完备的，也是完美的.(1)(2)(3)SchoolofInformationScienceandEngineering18.2二部图中的匹配求匹配算法：设G0=是二部图,⑴置初值:V1=V0E1=ΦG1=G0⑵如果G1是零图,则结束,得E1.否则在V1中选取度最小的

17、结点,不妨设这个结点是a,且与a相邻接的一个结点为b,取边(a,b),E1=E1∪{(a,b)}⑶从图G1中删去结点a,b.(即V1=V1-{a,b}),得到图G1⑷转到⑵.试对右图执行以上算法SchoolofInformationScienceandEngineering18.2二部图中的匹配执行算法:a)度数最小的结点是c,E1={(B,c)}b)度数最小的结点是d,E1={(B,c),(A,d)}c)度数最小的结点是a,E1={(B,c),(A,d)(C,a)}d)度数最小的结点是b,E1={(B,c),(A,d),(C,a),(D,b)}当然执行此算法,不一定得到所

18、有匹配.SchoolofInformationScienceandEngineeringHall定理定理18.5（Hall定理）设二部图G=中，

19、V1

20、

21、V2

22、.G中存在从V1到V2的完备匹配当且仅当V1中任意k(k=1,2,…,

23、V1

24、)个顶点至少与V2中的k个顶点相邻.本定理中的条件常称为“相异性条件”.由Hall定理立刻可知，上图中(2)为什么没有完备匹配.定理18.6设二部图G=中，V1中每个顶点至少关联t(t1)条边，而V2中每个顶点至多关联t条边，则G中存在V1到V2的完备匹配。证明要点：满足相异性条件.定理18.6中的条

25、件称为t（t1）条件.SchoolofInformationScienceandEngineering一个应用实例某课题组要从a,b,c,d,e5人中派3人分别到上海、广州、香港去开会.已知a只想去上海，b只想去广州，c,d,e都表示想去广州或香港.问该课题组在满足个人要求的条件下，共有几种派遣方案？解用二部图中的匹配理论解本题方便.令G=，其中V1={s,g,x}，s,g,x分别表示上海、广州和香港.V2={a,b,c,d,e},E={(u,v)

26、uV1,vV2,v想去u}.G如图所示.G