第7章+图论-5(匹配)ppt课件.ppt

《第7章+图论-5(匹配)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图论引言7.1图的基本概念7.2路与连通7.3图的矩阵表示7.4最短路径问题7.5图的匹配8.1Euler图和Hamilton图8.2树8.3生成树8.4平面图7.5匹配匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓“人员分配问题”和“最优分配问题”中有重要作用。假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生结婚？类似的工作分配问题：现有n个人，m份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？7.5匹配[例]男生认识的女生b1g1,g4,g5b2g1b3g2

2、,g3,g4b4g2,g4b1b2g1b4g5b3g4g2g3配偶问题：二分图是否存在一个边集E使得其中任意两边不邻接，且每个结点bi与E的某个边关联。7.5匹配例二分图G(V1,V2)的完全匹配:是否存在单射f:V1V2使得任意vV1,v与f(v)相邻。b1b2g1b4g5b3g4g2g3二分图存在完全匹配的必要条件是：任意k个男生至少认识k个女生。这个条件也是充分的。7.5.1匹配的基本概念[匹配]设G是无环图，ME(G)，M≠，如果M中任意两条边在G中均不相邻，则M称为G的一个边独立集或匹配。[最大匹配]若对图G的任何匹配，均有

3、

4、＜

5、M

6、，则称M为图

7、G的最大匹配。[匹配数]G中最大匹配中的边数称为匹配数，记作(G)。设G的所有匹配为M1、M2、…、Mk，记7.5.1匹配的基本概念[定义]设M是G的一个匹配，若有e=(vi,vj)M，则称vi和vj在M中饱和或M饱和。若G中的每一个顶点都为M饱和，则称M为G的一个完美匹配。e1e2e3e4e5e6e7最大匹配：{e1,e5,e6}匹配数：3注释（1）完美匹配是最大匹配，反之未必。（2）匹配的概念与边的方向无关，故只需讨论无向图。（3）图G的边不交匹配的最小数目即为图G的边色数7.5.1匹配的基本概念例最大匹配完美匹配7.5.1匹配的基本概念[边覆盖]一

8、个图G=(V,E)，E´E，若G的任一个顶点都与E´中的边关联，则称E´覆盖G，或称E´为G的一个边覆盖（集）。[极小边覆盖]E´是G的一个极小边覆盖E´为G的一个边覆盖(E1)(E1E´E1不是G的边覆盖)若在E´集中去除任何元素E´不再是覆盖集7.5.2最大匹配的基本定理[M交错路]设G和M如上所述，G的一条M交错路指G中一条路，其中的边在M和EM中交错出现。路是由属于M的匹配边和不属于M的非匹配边交替出现组成[M可增广路]设G和M如上所述，若G的一条M交错路的始点和终点都是M不饱和的，则称该M交错路为一条M可增广路。例匹配，匹

9、配，匹配，增广路7.5.2最大匹配的基本定理[引理]设P是匹配Ｍ-可增广道路，则PM是一个比M更大的匹配，且

10、PM｜＝

11、M

12、+1.[定理7-2-1](Berge)设G=(V,E)，M为G中匹配，则M为G的最大匹配当且仅当G中不存在M可增广道。[证明]必要性：如有M-可增广道路，则有更大匹配。矛盾！充分性：如果有最大匹配M’,

13、M’

14、>

15、M

16、.考虑MM’，其中每个结点的最多与Ｍ边和一个M’边关联，每条道路是M边和M’边交互道路。在可增广路中，第一条边与最后一条边都不是中的边，因而可增广路中属于的边数比不在中边数少一条。7.5.2最大匹配的基本定理M实线边

17、，M’虚线边MM’其中回路包含相同数目的M边和M’边。由

18、M’

19、>

20、M

21、,必存在M’边开始，M‘边终止的M交互道路，即M-可增广道路，矛盾！7.5.2最大匹配的基本定理例]从匹配M={(v6,v7)}开始，求下图的最大匹配系统地检查不饱和点出发有无可增广道路，如，v1出发有可增广道路v1,v7v6,v8(可画以v1为根的交互树)，由此得到匹配(a),v2出发没有，v3出发存在v3v4，可得更大匹配(b),其他点出发不存在可增广道路，故(b)是最大匹配。(a)(b)7.5.2最大匹配的基本定理设S是图G的任一顶点子集，G中与S的顶点邻接的所有顶点的集合，称为S

22、的邻集（neighbourset），记作NG(S)。[定理7-2-2Hall定理]设G是有二部划分(V1,V2)的二分图，则G含有饱和V1的每个顶点的匹配M的充要条件是，对SV1，

23、N(S)

24、≥

25、S

26、。7.5.2最大匹配的基本定理[证明]必要性：对SV1，匹配M将S中的每个顶点与N(S)中顶点配对，故

27、N(S)

28、≥

29、S

30、。充分性：对SV1，有

31、N(S)

32、≥

33、S

34、。可以按下面方法作出饱和V1的匹配M。先做任一初始匹配M1，若已饱和V1，定理得证。否则，V1中至少有一个非饱和点x1，检查以x1为起点，终点在V2中的交错路。考虑下列两种情形：（1）不存在任何一条交错

35、路可以到达V2的非饱和点。这时从x1开