离散数学 一些特殊的图VIP免费

1第8章一些特殊的图8

3哈密顿图8

4平面图28

1二部图二部图完全二部图匹配极大匹配最大匹配匹配数完备匹配3二部图定义设无向图G=,若能将V分成V1和V2(V1V2=V,V1V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图(二分图),记为,称V1和V2为互补顶点子集

又若G是简单图,且V1中每个顶点均与V2中每个顶点都相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|

(a)(b)以上两个图都是二部图，其中(b)图是完全二部图

4例完全二分图Km,n=(V1,V2,E)共有多少条边

解因为V1中每个顶点都与V2中每个顶点相邻接,所以V1中每个顶点关联|V2|=n条边;而V1中有m个顶点,所以Km,n共有mn条边

5二部图的判别法定理无向图G=是二部图当且仅当G中无奇圈

即G中的每一条回路都是由偶数条边组成

证明：当G(V1,V2)是二部图时，G中的任意一条回路的各边必须往返于V1,V2之间，因此其回路必由偶数条边组成

6例：判断下图是否为二部图

解：图中的每一条回路都是由偶数条边组成

所以此图为二部图

→7匹配设G=(V,E)是具有互补顶点子集V1和V2的二分图,ME,若M中任意两条边都不相邻,则称M为G中的匹配(对集)

如果M是G的匹配,且M中再加入任何一条边就都是不匹配了,则称M为极大匹配

最大匹配:边数最多的匹配匹配数:最大匹配中的边数,记为1

8如在下图中，如果用a1,a2,a3,a4表示4位教师，b1,b2,b3表示三门待开的课程

当某位教师能开某门课程时，则把它们的对应顶点用边连接起来

如果规定一个教师只能担任一门课程，那么匹配M就表示了一种排课方案

为了使排课方案能最大限度地作到“各尽其能”，这就是最大匹配的概念

9匹配(续)设M为G中一个匹配ai与bj