离散数学-图论课件打包第7章+图论-5（匹配）.ppt

第七章 图论 引言 7.1 图的基本概念 7.2 路与连通 7.3 图的矩阵表示 7.4 最短路径问题 7.5 图的匹配 8.1 Euler图和Hamilton图 8.2 树 8.3 生成树 8.4 平面图 7.5 匹配 匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓“人员分配问题”和“最优分配问题”中有重要作用。 假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生结婚？ 类似的工作分配问题：现有n个人，m份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？ 7.5 匹配 [例] 7.5 匹配 例 7.5 .1 匹配的基本概念 [匹配]设G是无环图，M E(G)，M≠ ，如果M中任意两条边在G中均不相邻， 则M称为G的一个边独立集或匹配。 [最大匹配]若对图G的任何匹配，均有| |＜|M|，则 称M为图G的最大匹配。 [匹配数] G中最大匹配中的边数称为匹配数，记作 (G)。设G的所有匹配为M1、M2、… 、Mk，记 7.5 .1 匹配的基本概念 7.5 .1 匹配的基本概念 例 7.5 .1 匹配的基本概念 [边覆盖] 一个图 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?可增广路。 7.5 .2 最大匹配的基本定理 [引理]　设P是匹配Ｍ-可增广道路，则P?M是一个比M更大的匹配，且| P?M｜＝|M|+1. [定理7-2-1] (Berge) 设G=(V,E)，M为G中匹配，则 M为G的最大匹配当且仅当G中不存在 M?可增广道。 [证明] 必要性：如有M-可增广道路，则有更大匹配。矛盾！ 充分性 ：如果有最大匹配M’, |M’||M|. 考虑M?M’，其中每个结点的最多与Ｍ边和一个M’边关联，每条道路是M边和M’边交互道路。 7.5 .2 最大匹配的基本定理 7.5 .2 最大匹配的基本定理 例] 从匹配M={(v6,v7)}开始，求下图的最大匹配 7.5 .2 最大匹配的基本定理 设S是图G的任一顶点子集，G中与S的顶点邻接的所有顶点的集合，称为S的邻集（neighbour set），记作NG(S)。 [定理7-2-2 Hall定理]设G是有二部划分(V1,V2)的二分图，则G含有饱和V1的每个顶点的匹配M的充要条件是，对S V1，|N(S)|≥|S|。 7.5 .2 最大匹配的基本定理 [证明] 必要性：对S V1，匹配M将S中的每个顶点与N(S)中顶点配对，故|N(S)|≥|S|。 充分性： 对S V1，有|N(S)|≥|S|。可以按下面方法作出饱和V1的匹配M。 先做任一初始匹配M1，若已饱和V1，定理得证。否则，V1中至少有一个非饱和点x1，检查以x1为起点，终点在V2中的交错路。考虑下列两种情形： （1）不存在任何一条交错路可以到达V2的非饱和点。这时从x1开始的一切交错路的终点还是在V1。故存在A V1，使得|N(A)|＜|A|，这与已知矛盾。 （2）存在一条以x1为起点，终点为V2的非饱和点的交错路P，可见P是可增广路，于是作新匹配M2＝M1 P，显然M2饱和x1，且|M2|＞|M1|。 因此，重复以上过程，可以找到饱和V1的全部顶点的匹配M。定理的充分性得证。 7.5 .2 最大匹配的基本定理 [定理7.5.3 Hall婚配定理]具有二部划分(V1,V2)的二分图G有完美匹配?|V1|＝|V2|，且对S V1（或V2）均有|N(S)|≥|S|。 推论：设G是k（k＞0）正则二分图，则G有完美匹配。 证明： 设G是二部划分(V1,V2)的k正则二分图，则k|V1|＝|E(G)|＝k|V2| 由于k≠0，所以|V1|＝|V2|。任取S V1，并用E1和E2分别表示G中与S和N(S)中点关联的边集，则E1 E2。 因而k|N(S)|＝|E2|≥|E1|＝k|S| 即 |N(S)|≥|S|，S