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

第七章图论 引言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匹配 例 配偶问题 二分图是否存在一个边集E使得其中任意两边不邻接 且每个结点bi与E的某个边关联 7 5匹配 例 二分图G V1 V2 的完全匹配 是否存在单射f V1V2使得任意v V1 v与f v 相邻 二分图存在完全匹配的必要条件是 任意k个男生至少认识k个女生 这个条件也是充分的 7 5 1匹配的基本概念 匹配 设G是无环图 ME G M 如果M中任意两条边在G中均不相邻 则M称为G的一个边独立集或匹配 最大匹配 若对图G的任何匹配 均有 M 则称M为图G的最大匹配 匹配数 G中最大匹配中的边数称为匹配数 记作 G 设G的所有匹配为M1 M2 Mk 记 7 5 1匹配的基本概念 定义 设M是G的一个匹配 若有e vi vj M 则称vi和vj在M中饱和或M 饱和 若G中的每一个顶点都为M 饱和 则称M为G的一个完美匹配 最大匹配 e1 e5 e6 匹配数 3 注释 1 完美匹配是最大匹配 反之未必 2 匹配的概念与边的方向无关 故只需讨论无向图 3 图G的边不交匹配的最小数目即为图G的边色数 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最大匹配的基本定理 M实线边 M 虚线边 M M 其中回路包含相同数目的M边和M 边 由 M M 必存在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的邻集 neighbourset 记作NG S 定理7 2 2Hall定理 设G是有二部划分 V1 V2 的二分图 则G含有饱和V1的每个顶点的匹配M的充要条件是 对SV1 N S S 7 5 2最大匹配的基本定理 证明 必要性 对SV1 匹配M将S中的每个顶点与N S 中顶点配对 故 N S S 充分性 对SV1 有 N S S 可以按下面方法作出饱和V1的匹配M 先做任一初始匹配M1 若已饱和V1 定理得证 否则 V1中至少有一个非饱和点x1 检查以x1为起点 终点在V2中的交错路 考虑下列两种情形 1 不存在任何一条交错路可以到达V2的非饱和点 这时从x1开始的一切交错路的终点还是在V1 故存在AV1 使得 N A A 这与已知矛盾 2 存在一条以x1为起点 终点为V2的非饱和点的交错路P 可见P是可增广路 于是作新匹配M2 M1P 显然M2饱和x1 且 M2 M1 因此 重复以上过程 可以找到饱和V1的全部顶点的匹配M 定理的充分性得证 7 5 2最大匹配的基本定理 定理7 5 3Hall婚配定理 具有二部划分 V1 V2 的二分图G有完美匹配 V1 V2 且对SV1 或V2 均有 N S S 推论 设G是k k 0 正则二分图 则G有完美匹配 证明 设G是二部划分 V1 V2 的k正则二分图 则k V1 E G k V2 由于k 0 所以 V1 V2 任取SV1 并用E1和E2分别表示G中与S和N S 中点关联的边集 则E1E2 因而k N S E2 E1 k S 即 N S S SV1由定理7 5 3可知 G有饱和V1的匹配M 由于 V1 V2 所以M是完美匹配 7 5 2最大匹配的基本定理 例 某工厂生产由六种不同颜色的纱织成的双色布 由这个工厂所生产的双色布中 每一种颜色至少和其它三种颜色搭配 证明 可以挑选出三种不同的双色布 它们含有所有的六种颜色 证明 分以下几步 1 建立图G V E 一个点代表一种颜色 两个点相邻当且仅当这个工厂生产出一种由这两个点所对应的这两种颜色搭配而成的双色布 2 由题意 所得图是6阶简单图 且每个点的度至少为3 3 证明这个图有一个完美对集 5 3最大匹配算法 匈牙利算法 1965年 匈牙利著名数学家Edmonds设计了一种求最大匹配的算法 称为匈牙利 Hungarian 算法 基本思想 从一个初始匹配M开始 系统地寻找M的可增广路P 然后扩展为更大的匹配M P M 直至不存在可增广路 方法 从一个不饱和结点开始u 寻找一条M可增广路P 构造一颗以u为根的交错树 即根出发的道路是M交错路 i 如果叶结点均为饱和的 换另一个不饱和结点 ii 如果某个叶是不饱和的 则有可增广路P 置M P M 重复上述过程 直至尝试过所有不饱和结点 5 3最大匹配算法 基本步骤 设有初始匹配M x0是M不饱和点 还没有尝试扩展 如果不存在这样的结点 即不存在M可增广路 转5 寻找从x0出发的M可增广路P S表示P在X中的结点 T表示P在Y中的结点 S x0 T 如果N S T 则x0不可扩展 即不存在从x0出发的可增广路 转1 否则 转4 当N S T时 取y N S T 若y不饱和 则P是可增广路 则扩展M P M 转1 若y饱和 则有 x y M 继续扩展P S S x T T y 转3 M是最大匹配 结束 5 3最大匹配算法 匈牙利算法 5 3最大匹配算法 例 5 3最大匹配算法 解 匈牙利算法例解 1 任给一个初始匹配 2 若X已经饱和 结束 否则转 3 M x1 y1 x3 y5 x5 y3 5 3最大匹配算法 解 匈牙利算法例解 3 在X中找一个非饱和点x0 S x0 T 4 若N S T则停止 否则任选一点y N S T M x1 y1 x3 y5 x5 y3 S x2 T N S y2 y3 5 3最大匹配算法 解 匈牙利算法例解 5 若y已饱和 M中必有 x y 作 S S x T T y 转 4 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 M x1 y1 x3 y5 x5 y3 S S x5 x2 x5 T T y3 y3 S x2 T 5 3最大匹配算法 解 匈牙利算法例解 4 若N S T则停止 否则任选一点y N S T M x1 y1 x3 y5 x5 y3 S x2 x5 T y3 N S y2 y3 y4 y5 5 3最大匹配算法 解 匈牙利算法例解 5 若y已饱和 M中必有 x y 作 S S x T T y 转 4 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 M x1 y1 x3 y5 x5 y3 S x2 x5 T y3 S S x3 x2 x5 x3 T T y5 y3 y5 5 3最大匹配算法 解 匈牙利算法例解 4 若N S T则停止 否则任选一点y N S T M x1 y1 x3 y5 x5 y3 N S y2 y3 y4 y5 5 3最大匹配算法 解 匈牙利算法例解 5 若y已饱和 M中必有 x y 作 S S x T T y 转 4 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 M x1 y1 x3 y5 x5 y3 5 3最大匹配算法 解 匈牙利算法例解 2 若X已经饱和 结束 否则转 3 3 在X中找一个非饱和点x0 S x0 T 4 若N S T则停止 否则任选一点y N S T S x4 T N S y3 5 3最大匹配算法 例1 如图G所示 V1 x1 x2 x3 x4 x5 V2 y1 y2 y3 y4 y5 试求图G的最大匹配 图 a 图 b 5 3最大匹配算法 解 任取初始匹配M x2y2 x3y3 x5y5 如图 a 中虚线所 示 解题过程如下表 5 3最大匹配算法 因此 M x1y2 x2y1 x3y3 x5y5 即为图G的最大匹配 如图 b 虚线所示 图 b 图 a 匈牙利算法的时间复杂度分析 设二分图G有n个结点 m条边 利用匈牙利算法求G的最大匹配时 初始匹配可为空 因此算法最多可找n条可增广路 每找一条可增广路 最多比较m条边 从而算法的时间复杂度为O mn 故匈牙利算法为有效算法 7 5 4最优匹配 某公司准备安排n个员工x1 x2 xn从事n项工作y1 y2 yn 已知每个员工能胜任其中一项或几项工作 试问应该怎样安排 才能使尽可能多的人有工作可做 同时使尽量多的工作有人胜任 构造具有二部划分 V1 V2 的简单二分图G 其中其中V1 x1 x2 xn V2 y1 y2 yn 并且边 xi yj E G 职员xi能胜任工作yj 于是问题转化为求给定二分图G的最大匹配 7 5 4最优匹配 这种分配方案可能不止一种 或者说职员做各项工作 熟练程度 工作效率等未必一致 因此 要制定一个分工方案 使人尽其才 且公司的总效益最大 这样 就要考察具有二部划分 V1 V2 的加权完全二分图 其中V1 x1 x2 xn V2 y1 y2 yn 边 xi yj 上的权 xi yj 表示职员xi做工作yj的效率 于是问题等价于在这个加权图 中求一个总权最大的完美匹配 称这种匹配为最优匹配 optimalmatching 当然 若枚举所有n 个完美匹配 然后比较它们的权 这种方法无疑是可以的 但是 当n很大时 这种方法显然是无效的 本节将介绍一个求最优匹配的有效算法 7 5 4最优匹配 带权二分图 二分图的每条边 i j 均带有一个权w i j 一个匹配的权是匹配各边权的和 最优匹配问题 给定带权二分图 求具有最大权的匹配 7 5 4最优匹配 考虑带权完全二分图G X Y X x1 xn Y y1 yn V X Y可行顶点标号是定义在V上的一个实数函数l 满足条件 对于任意x X y Yl x l y w x y l v 称为顶点v的标号 可行顶标总是存在的 例如 这种可行顶标称为平凡标号 trivillabelling 7 5 4最优匹配 等式子图 关于标号l的等式子图Gl V El El x y l x l y w x y 7 5 4最优匹配 定理1 设l是G的可行顶标 若l顶子图Gl有完美匹配M 则M是G的最优匹配 al min l x l y w x y x S y V2 T 7 5 4最优匹配 基于定理1的在一个加权二分图 Km n 中求最优匹配的有效算法 Kuhn munkres算法 1 从任意可行顶标 如平凡标号 l开始 确定l等子图Gl 并且在Gl中选取匹配M 若M饱和V1 则M是完美匹配 也即M是最优匹配 算法终止 否则转入 2 步 2 匈牙利算法终止于S V1 T V2且使NGl S T 计算a1 确定新的可行顶标l 并以l 替代l 以Gl 替代Gl转入 1 步 7 5 4最优匹配 例1已知完全二分图K5 5 其中V1 x1 x2 x3 x4 x5 V2 y1 y2 y3 y4 y5 且K5 5的权矩阵为A 求K5 5的最优匹配 解 1 取可行顶标l如下 l y1 l y2 l y3 l y4 l y5 0l x1 max 3 5 5 4 1 5l x2 max 2 2 0 2 2 2l x3 max 2 4 4 1 0 4l x4 max 0 1 1 0 0