《图论的配对问题》PPT课件.ppt

第五章匹配 1最大匹配 1 具体问题描述 有n个女士和n个男士参加舞会 每位女士与其中若干位男士相识 每位男士与其中若干位女士相识 问如何安排 使得尽量多配对的男女舞伴相识 1匹配 1最大匹配 1 下图就是一种分配方法 f1 m3 f2 m1 f3 m2 f4 m5 f5 m4 匹配问题是运筹学的重要问题之一 也是图论的重要内容 它在所谓 人员分配问题 和 最优分配问题 中有重要作用 假定有一个男生有穷集合 其中每个男生认识一些女生 在什么条件下每个男生都可以和他认识的女生配对 类似的工作分配问题 现有n个人 m份工作 每个人有其擅长的工作 在什么条件下每个人都可以得到一份他擅长的工作 如何分配 1最大匹配 定义 定义 若图G V E 的顶点可以分成X Y两个子集 每个子集里的顶点互不相邻 这样的图称为二分图 1最大匹配 定义1 定义 若M是图G V E 的边子集 且M中的任意两条边在G中不相邻 则称M为G中的一个匹配 M中的每条边的两个端点称为是M 饱和的的 M f1 m2 f2 m1 f3 m4 f4 m5 1最大匹配 定义2 定义 若图G中每个顶点均被M许配时 称M为G中的一个完美匹配 M f1 m3 f2 m1 f3 m2 f4 m5 f5 m4 1最大匹配 定义3 定义 图G中边数最多的匹配M 称为G中的一个最大匹配 M f1 m3 f2 m1 f3 m2 f5 m5 1最大匹配 定义4 定义 若匹配M的某边和顶点v关联 称v是M 饱和的 否则就是M 不饱和的 M f1 m3 f2 m1 f3 m2 f5 m5 饱和的 不饱和的 1最大匹配 定义5 定义 若M是图G的一个匹配 若从G中一个顶点到另一个顶点存在一条道路 此路径由属于M和不属于M的边交替出现组成的 则称此路径为M 交错路 M f1 m3 f2 m1 f3 m2 f4 m5 f5 m4 P f1m3f4m5f2m1f5m4 1最大匹配 定义6 定义 若交错路的两个端点为关于M的不饱和顶点时 称此交互道为可增广道路 M f2 m5 f3 m2 f4 m3 f5 m4 P m1f2m5f4m3f1是一条可增广道路 1最大匹配 定义8 M f2 m5 f3 m2 f4 m3 f5 m4 P m1f2m5f4m3f1是一条可增广道路 M f1 m3 f2 m1 f3 m2 f4 m5 f5 m4 1最大匹配 Berge定理 定理7 1 Berge1957 M为最大匹配的充要条件是 图G中不存在可增广道路 M f1 m3 f2 m1 f3 m2 f5 m5 引理 设P是匹配 可增广道路 则P M是一个比M更大的匹配 且 P M M 1 定理1 Berge 设G V E M为G中匹配 则M为G的最大匹配当且仅当G中不存在M 可增广道 证明 必要性 如有M 可增广道路 则有更大匹配 矛盾 充分性 如果有最大匹配M M M 考虑M M 在可增广路中 第一条边与最后一条边都不是中的边 因而可增广路中属于的边数比不在中边数少一条 M实线边 M 虚线边 M M 其中每个结点的最多与 边和一个M 边关联 每条道路是M边和M 边交互道路 其中回路包含相同数目的M边和M 边 由 M M 必存在M 边开始 M 边终止的M交互道路 即M 可增广道路 矛盾 2Hall定理 设有m个人 n项工作 每个人会做其中的若干项工作 能不能适当安排 使得每个人都有工作做 2Hall定理 当m n时 肯定是不可能的 即使是m n也不一定 但如果每个人能做的工作越多 越容易实现 2Hall定理 1 Hall定理 1935 二分图G存在一匹配M 使得X的所有顶点关于M饱和的充要条件是 对于X任一子集A 及与A邻接的点集为N A 恒有 N A A 3人员分派问题 1965年 匈牙利著名数学家Edmonds设计了一种求最大匹配的算法 称为匈牙利 Hungarian 算法 工作分配问题 现有n个人 n份工作 每个人有其擅长的工作 在什么条件下每个人都可以得到一份他擅长的工作 如何分配 3匈牙利算法 匈牙利 Hungarian 算法 1 任给一个初始匹配 2 若X已经饱和 结束 否则转 3 3 在X中找一个非饱和点x0 V1 x0 V2 空集 4 若N V1 V2则停止 否则任选一点y N V1 V2 5 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 4 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 3匈牙利算法例 用匈牙利算法求下图的最大匹配 例 3匈牙利算法例解 1 任给一个初始匹配 2 若X已经饱和 结束 否则转 3 解 M x1 y1 x3 y5 x5 y3 3匈牙利算法例解1 3 在X中找一个非饱和点x0 V1 x0 V2 空集 4 若N V1 V2则停止 否则任选一点y N V1 V2 解 M x1 y1 x3 y5 x5 y3 V1 x2 V2 空集 N V1 y2 y3 3匈牙利算法例解2 5 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 4 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 解 M x1 y1 x3 y5 x5 y3 V1 V1 x5 x2 x5 V2 V2 y3 y3 V1 x2 V2 空集 3匈牙利算法例解3 4 若N V1 V2则停止 否则任选一点y N V1 V2 解 M x1 y1 x3 y5 x5 y3 V1 x2 x5 V2 y3 N V1 y2 y3 y4 y5 3匈牙利算法例解4 5 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 4 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 解 M x1 y1 x3 y5 x5 y3 V1 x2 x5 V2 y3 V1 V1 x3 x2 x5 x3 V2 V2 y5 y3 y5 3匈牙利算法例解5 4 若N V1 V2则停止 否则任选一点y N V1 V2 解 M x1 y1 x3 y5 x5 y3 V1 x2 x5 x3 V2 y3 y5 N V1 y2 y3 y4 y5 3匈牙利算法例解6 5 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 4 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 解 M x1 y1 x3 y5 x5 y3 V1 x2 x5 x3 V2 y3 y5 3匈牙利算法例解7 2 若X已经饱和 结束 否则转 3 3 在X中找一个非饱和点x0 V1 x0 V2 4 若N V1 V2则停止 否则任选一点y N V1 V2 解 V1 x4 V2 空集 M x1 y1 x2 y3 x3 y2 x5 y5 N V1 y3 3匈牙利算法例解8 5 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 4 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 解 V1 x4 V2 空集 M x1 y1 x2 y3 x3 y2 x5 y5 V1 V1 x2 x4 x2 V2 V2 y3 y3 3匈牙利算法例解9 4 若N V1 V2则停止 否则任选一点y N V1 V2 解 M x1 y1 x2 y3 x3 y2 x5 y5 V1 x4 x2 V2 y3 N V1 y2 y3 3匈牙利算法例解10 5 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 4 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 解 M x1 y1 x2 y3 x3 y2 x5 y5 V1 x4 x2 V2 y3 V1 V1 x3 x4 x2 x3 V2 V2 y2 y3 y2 3匈牙利算法例解11 4 若N V1 V2则停止 否则任选一点y N V1 V2 解 M x1 y1 x2 y3 x3 y2 x5 y5 V1 x4 x2 x3 V2 y3 y2 N V1 y2 y3 y5 3匈牙利算法例解12 5 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 4 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 解 M x1 y1 x2 y3 x3 y2 x5 y5 V1 x4 x2 x3 V2 y3 y2 V1 V1 x5 x4 x2 x3 x5 V2 V2 y5 y3 y2 y5 3匈牙利算法例解13 4 若N V1 V2则停止 否则任选一点y N V1 V2 解 M x1 y1 x2 y3 x3 y2 x5 y5 V1 x4 x2 x3 x5 V2 y3 y2 y5 N V1 y2 y3 y5 y4 3匈牙利算法例解14 5 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 4 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 解 M x1 y1 x2 y3 x3 y2 x5 y5 V1 x4 x2 x3 x5 V2 y3 y2 y5 3匈牙利算法例解15 2 若X已经饱和 结束 否则转 3 解 这时 M x1 y1 x2 y2 x3 y5 x4 y3 x5 y4 就是所求的最大匹配 4最佳匹配 公司里有n名工作人员 他们每个人都能承担n项工作的其中若干项 因为每个人的特长不同 所以对每项工作创造的价值也有所不同 问如何安排 使得他们总的创造价值最大 4最佳匹配 x对每项工作创造的价值的如右边的矩阵所表示 5最佳匹配算法及例 Kuhn和Munkras设计了求最佳匹配的有效算法 他们把求最佳匹配的问题转化成可用匈牙利算法求另一个图的完美匹配的问题 5最佳匹配算法1 为此 他们对加权的二分图每个顶点v给一个顶标l v 当xi X yj Y l xi l yj cij时 称这样的顶标为可行顶点a标号 feasiblevertexlabelling 5最佳匹配算法2 初始的时候 令l xi maxci l yi 0 最佳匹配定理 设二分图Kn n G是具有正常顶标l的加权图 取G的边子集El eij eij E G l i l j cij 令Gl是以El为边集的生成子图 如果有Gl完美匹配M 则M即为G的最佳匹配 5最佳匹配算法3 KM算法 1 选定初始正常标顶l 构作图Gl 在Gl中用匈牙利算法求一个最大匹配 2 若X饱和则结束 此时所得匹配就是最佳匹配 否则在X中任选一个非饱和点x0 令V1 x0 V2 3 若NGl V1 V2 则取 min l xi l yj cij 其中xi V1 yj NG V1 V2 使得l v v V1l v l v v V2l v 其他重新构作图Gl 在NGl V1 V2任取一点y 转向 4 否则在NGl V1 V2任取一点y 转向 4 5最佳匹配算法4 4 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 3 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 5最佳匹配算法例 求下图的最佳匹配 例 5最佳匹配算法例解1 1 选定初始正常标顶l 构作图Gl 在Gl中用匈牙利算法求一个最大匹配 解 M x1 y2 x2 y1 x3 y3 x5 y5 5最佳匹配算法例解2 2 若X饱和则结束 此时所得匹配就是最佳匹配 否则在X中任选一个非饱和点x0 令V1 x0 V2 空集 解 M x1 y2 x2 y1 x3 y3 x5 y5 V1 x4 V2 空集 5最佳匹配算法例解3 3 若NGl V1 V2 则 否则在NGl V1 V2任取一点y 转向 4 解 M x1 y2 x2 y1 x3 y3 x5 y5 V1 x4 V2 5最佳匹配算法例解4 4 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 3 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 解 M x1 y2 x2 y1 x3 y3 x5 y5 V1 x4 x3 V2 y3 5最佳匹配算法例解5 3 若NGl V1 V2 则 否则在NGl V1 V2任取一点y 转向 4 解 M x1 y2 x2 y1 x3 y3 x5 y5 V1 x4 x3 V2 y3 5最佳匹配算法例解6 4 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 3 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 解 M x1 y2 x2 y1 x3 y3 x5 y5 V1 x4 x3 x1 V2 y3 y2 5最佳匹配算法例解7 3 若NGl V1 V2 取 min l xi l yj cij 其中xi V1 yj NG V1 V2 解 M x1 y2 x2 y1 x3 y3 x5 y5 V1 x4 x3 x1 V2 y3 y2 1 NG V1 y1 y2 y3 y4 y5 5最佳匹配算法例解8 l v v V1l v l v v V2l v 其他 解 M x1 y2 x2 y1 x3 y3 x5 y5 V1 x4 x3 x1 V2 y3 y2 1 5最佳匹配算法例解9 重新构作图Gl 在NGl V1 V2任取一点y 转向 4 解 M x1 y2 x2 y1 x3 y3 x5 y5 V1 x4 x3 x1 V2 y3 y2 l xi l yj cij 5最佳匹配算法例解10 4 若y已饱和 M中必有 y z 作 V1 V1 z V2 V2 y 转 3 否则 求一条从x0到y的可增广道路P 对之进行增广 转 2 解 V1 x4 x3 x1 V2 y3 y2 M x1 y2 x2 y1 x3 y3 x5 y5 M x1 y4 x2 y1 x3 y3 x4 y4 x5 y5 5最佳匹配算法例解11 2 若X饱和则结束 此时所得匹配就是最佳匹配 否则在X中任选一个非饱和点x0 令V1 x0 V2 解 M x1 y4 x2 y1 x3 y3 x4 y4 x5 y5 W 4 2 4 1 3 14 课堂练习 1 用匈牙利算法求下图的最大匹配 课堂练习 2 若二分图K5 5的权值矩阵如下 求其最佳匹配 6色数问题 边的着色问题顶点的着色问题 一 边的着色问题 定义 给图G的边着色 使得有共同顶点的边异色的最少颜色数 称为边色数 边色数 3 边色数 5 一 边的着色问题 妖怪图 snarkgraph 妖怪图每个点都关联着3条边 用4种颜色可以把每条边涂上颜色 使得有公共端点的边异色 而用3种颜色办不到 切断任意3条边不会使它断裂成2个有边的图 一 边的着色问题1 单星妖怪和双星妖怪 一 边的着色问题 时间表问题 设x1 x2 xm为m个工作人员 y1 y2 yn表为n种设备 工作人员对设备提出要求 使用时间均假定以单位时间计算 自然每一个工作人员在同一个时间只能使用一种设备 某一种设备在同一时间里只能为一个工作人员使用 问应如何合理安排 使得尽可能短时间里满足工作人员的要求 问题转换为X x1 x2 xm Y y1 y2 yn 的二分图G 工作人员xi要求使用设备yj 每单位时间对应一条从xi到yj的边 这样所得的二分图过xi yj的边可能不止一条 问题变为对所得二分图G的边着色问题 有相同颜色的边可以安排在同一时间里 一 边的着色问题3 定理 二分图G的边色数 图中顶点的最大度 一 边的着色问题3 定理 Vizing1964 若图G为简单图 图中顶点最大度为d 则G的边色数为d或d 1 第一类图 第二类图 目前仍无有效区分 判别 任给定图属第几类图的有效方法 一 边的着色问题4 边的着色问题可以转化为顶点的着色问题 二 顶点的着色问题 定义 给图G的顶点着色 使得相邻的顶点异色的最少颜色数 称为图G顶色数 简称色数 记作 G G 2 二 顶点的着色问题 四色猜想 平面图的色数不大于5 一 边的着色问题 课程考试安排 用顶点v1 v2 vn表示n门课程 若其中两门课i j被同时选 则vi vj间连一条边 考试安排问题相当于图的顶点染色问题 着同一颜色的顶点对应的课程可以同时进行考试 使图的相邻顶点有不同颜色的最少颜色数目 便是进行考试的最少场次 物资存储问题 6 2排课表问题 问题m位教师和n个班级 其中教师Xi要给班级Yj上pij节课 欲在最少节次p内排完所有的课 将偶图G X Y E 的边集E划分成互不相交的p个匹配 E1 Ep 且使p为最小 其中X x1 xm Y y1 yn 求偶图G的p 边着色 其中p 由习题6 1 4知 上述问题有好算法 当上述问题中教室数有限时 教室数 若要在p 节内排完全部 l E 节课 所需教室数c 问题能否适当排课 使全部节课在p 节内排完 且每节课所用教室数 1 i p 6 2排课表问题 引理6 3设M N为G的二不相交匹配 且 M N 则存在G的二不相交匹配M N 使 M M 1 N N 1 且M N M N 证明 令H G M N 则H的每个分支为一路或圈 由M及N的边交错组成 且由于 M N 存在H的一个分支 它是路P 起 止于M边 因此M M E P 及N N E P 即为所求 定理6 3设G为偶图 p 则存在G的p个互不相交的匹配使E M1 Mp 且 1 i p 6 2排课表问题 证明 由定理6 1 E可划分为 个互不相交的匹配M1 M 因此 对p G有p个互不相交的匹配M1 M Mp 令Mi 当i p 使E M1 Mp 今对边数差 1的两个匹配 反复使用引理6 3 最后可得所求的匹配M1 Mp 注在实际应用中 教师和班级往往会提出一些 例如所上节次时间的要求 问题变得很复杂 Even Itai Shmir 1976 证明 在教师和班级提出条件时 判定课表的存在性问题是个NP complete问题 甚至当G为简单偶图 且学生不提出要求的情况下 也是如此 二 顶点的着色问题1 色数的性质 1 图G只有孤立点时 G 1 2 n个顶点的完全图G有 G n 二 顶点的着色问题1 3 若图G是n个顶点的回路 则 G 2n为偶数 3n为奇数 二 顶点的着色问题1 4 图G是顶点数超过1的树时 G 2 二 顶点的着色问题1 5 若图G是二分图 则 G 2 二 顶点的着色问题2 定理 图G V E 的色数 G 2的充要条件是 1 E 1 2 G不存在边数为奇数的回路 二 顶点的着色问题2 定理 若图G V E d max d vi vi V 则 G d 1 三 顶点着色的算法 下面给出顶点着色的算法 假定G的顶点为v1 v2 vn 用来染色的颜色为c1 c2 cn 1 对i 1 2 n 作Ci c1 c2 ci 2 标顶点vi i 1 2 n 的颜色集Ci的第一种颜色ck 3 对顶点vi的所有邻接点vj j i 作Cj Cj ck 4 转到 2 直到所有顶点都着色为止 三 顶点着色的算法例 对下图顶点进行着色 例 三 顶点着色的算法例解 1 对i 1 2 n 作Ci c1 c2 ci 解 C1 c1 C2 c1 c2 C3 c1 c2 c3 C4 c1 c2 c3 c4 C5 c1 c2 c3 c4 c5 C6 c1 c2 c3 c4 c5 c6 C7 c1 c2 c3 c4 c5 c6 c7 三 顶点着色的算法例解1 2 标顶点vi i 1 2 n 的颜色集Ci的第一种颜色ck 解 C1 c1 C2 c1 c2 C3 c1 c2 c3 C4 c1 c2 c3 c4 C5 c1 c2 c3 c4 c5 C6 c1 c2 c3 c4 c5 c6 C7 c1 c2 c3 c4 c5 c6 c7 c1 三 顶点着色的算法例解2 3 对顶点vi的所有邻接点vj j i 作Cj Cj ck 解 c1 C1 c1 C2 c1 c2 C3 c1 c2 c3 C4 c1 c2 c3 c4 C5 c1 c2 c3 c4 c5 C6 c1 c2 c3 c4 c5 c6 C7 c1 c2 c3 c4 c5 c6 c7 C2 c2 C3 c2 c3 C7 c2 c3 c4 c5 c6 c7 C5 c2 c3 c4 c5 C6 c2 c3 c4 c5 c6 三 顶点着色的算法例解3 4 转到 2 直到所有顶点都着色为止 2 标顶点vi i 1 2 n 的颜色集Ci的第一种颜色ck 解 c1 C1 c1 C2 c2 C3 c2 c3 C4 c1 c2 c3 c4 C5 c2 c3 c4 c5 C6 c2 c3 c4 c5 c6 C7 c2 c3 c4 c5 c6 c7 c2 三 顶点着色的算法例解4 3 对顶点vi的所有邻接点vj j i 作Cj Cj ck 解 c1 C1 c1 C2 c2 C3 c2 c3 C4 c1 c2 c3 c4 C5 c2 c3 c4 c5 C6 c2 c3 c4 c5 c6 C7 c2 c3 c4 c5 c6 c7 c2 C3 c3 三 顶点着色的算法例解5 解 c1 C1 c1 C2 c2 C3 c3 C4 c1 c2 c3 c4 C5 c2 c3 c4 c5 C6 c2 c3 c4 c5 c6 C7 c2 c3 c4 c5 c6 c7 c2 4 转到 2 直到所有顶点都着色为止 2 标顶点vi i 1 2 n 的颜色集Ci的第一种颜色ck c3 三 顶点着色的算法例解6 解 c1 C1 c1 C2 c2 C3 c3 C4 c1 c2 c3 c4 C5 c2 c3 c4 c5 C6 c2 c3 c4 c5 c6 C7 c2 c3 c4 c5 c6 c7 c2 3 对顶点vi的所有邻接点vj j i 作Cj Cj ck c3 C5 c2 c4 c5 C1 c1 c2 c4 三 顶点着色的算法例解7 解 c1 C1 c1 C2 c2 C3 c3 C4 c1 c2 c4 C5 c2 c4 c5 C6 c2 c3 c4 c5 c6 C7 c2 c3 c4 c5 c6 c7 c2 4 转到 2 直到所有顶点都着色为止 2 标顶点vi i 1 2 n 的颜色集Ci的第一种颜色ck c3 c1 三 顶点着色的算法例解8 解 c1 C1 c1 C2 c2 C3 c3 C4 c1 c2 c4 C5 c2 c4 c5 C6 c2 c3 c4 c5 c6 C7 c2 c3 c4 c5 c6 c7 c2 3 对顶点vi的所有邻接点vj j i 作Cj Cj ck c3 c1 三 顶点着色的算法例解9 解 c1 C1 c1 C2 c2 C3 c3 C4 c1 c2 c4 C5 c2 c4 c5 C6 c2 c3 c4 c5 c6 C7 c2 c3 c4 c5 c6 c7 c2 4 转到 2 直到所有顶点都着色为止 2 标顶点vi i 1 2 n 的颜色集Ci的第一种颜色ck c3 c1 c2 三 顶点着色的算法例解10 解 c1 C1 c1 C2 c2 C3 c3 C4 c1 c2 c4 C5 c2 c4 c5 C6 c2 c3 c4 c5 c6 C7 c2 c3 c4 c5 c6 c7 c2 3 对顶点vi的所有邻接点vj j i 作Cj Cj ck c3 c1 c2 C6 c3 c4 c5 c6 三 顶点着色的算法