偶图与匹配

第15节偶图与匹配 主要内容 偶图匹配 结婚 婚配 问题 结婚问题 已知由若干个小伙子组成的集合F 若干个姑娘之集为G 姑娘们都渴望结婚 但也不希望媒人介绍 随便嫁给一个她不认识或不可接受的小伙子 实际上 每个姑娘心中都有一张可接受为配偶的小伙子名单 问在什么条件下才能把所有的姑娘都嫁出去 对这个问题 若把姑娘和小伙子用点来表示 若某位姑娘能接受某个小伙子 则在相应点间连一条线 则可以得到一个无向图G 工作安排问题 工作安排问题 一个车间有m个工人和n件不同的工作 每件工作只需一位工人干 而每位工人仅能熟练地干其中的几件工作 问在什么条件下车间主任能为每位工人分配一件他能胜任的工作呢 对这个问题 若把工人和每件工作用点来表示 若一位工人能胜任某项工作 则在相应点之间连一条线 则得到一个无向图G 偶图 二部图 双图 定义1G V E 称为偶图 如果G的顶点集V有一个二划分 V1 V2 使得G的任一条边的两个端点一个在V1中 另一个在V2中 这个偶图有时记为 V1 V2 E 定义1 G V E 如果能将V分成V1和V2使得V1 V2 V V1 V2 且G中的每条边的两个端点都一个属于V1 另一个属于V2 如果 u V1 v V2均有 u v E 则这个偶图称为完全偶图 并记为K m n 或Km n 其中 V1 m V2 n 完全偶图 1 完全偶图Km n有多少条边 有mn条边 2 完全偶图中有没有三角形 没有三角形 定义2G V E 是一个图 u和v是G的顶点 联结u和v的最短路的长称为u与v之间的距离 并记为d u v 如果u与v之间没有路 则定义d u v 两点之间的距离 性质 1 d u v 0 且d u v 0 u v 2 d u v d v u 3 d u v d v w d u w 例如 a与e之间的最短路 ace afe d a e 2 d a h 定理1图G为偶图的充分必要条件是它的所有圈的长度都是偶数 证 必要性 设P u1u2u3 um 1umu1是G的一个长为m的圈 因为G V E 是一个偶图 则V存在一个二划分 V1 V2 对于任意 u v E u V1 v V2 在圈P中 若设u1 V1 那么所有圈上奇数下标的顶点都在V1中 偶数下标的顶点全在V2中 下标m必然是偶数 也就是这个圈的长度为偶数 偶图的判别定理 充分性设G的每个圈的长为偶数 需证G是偶图 不妨设G是连通图 否则可分别考虑G的每个支 任取G的一个顶点u 定义集合V1 v v V d u v 是偶数 V2 v v V d u v 是奇数 则 V1 V2 是V的一个二划分 只要证明V1中任意二顶点间无边 同时V2中任意两顶点间也无边即可 假设w与v是V1的两个不同顶点 并且 v w E 则令P是u与v间的最短路 Q为u与w间的最短路 u1为从u开始 P与Q的最后的一个公共顶点 用反证法 偶图的判别定理 因为P与Q是最短路 所以P和Q上的u到u1段也是最短的u与u1间路 设P中从u1到v的那一段为P1 Q中u1到w的那一段为Q1 因为P与Q都是偶数 因此P1与Q1有相同的奇偶性 于是 边 v w Q1 P1构成G中一个奇数长的圈 这与已知矛盾 所以V1的任两不同顶点v与w间无边 用完全一样的方法可证V2的任两顶点间也没边 因此G是一个偶图 偶图的判别定理 不是偶图 不是偶图 实例 匹配 定义3设G V E 是一个图 则 1 G的任两条不相邻的边x与y称为是互相独立的 2 若Y E 且Y中任两条边都是互相独立的 则称Y为G的一个匹配 显然 若Y是图G的一个匹配 则任意的v V v至多与Y中的一条边关联 3 设Y是图G的一个匹配 若对G的任一匹配Y 恒有 Y Y 则称Y是图G的一个最大匹配 定义4设G V E 是一个偶图且V V1 V2 对任意x E x是连接V1的一个顶点与V2的一个顶点的边 则若存在一个匹配Y使得 Y min V1 V2 则称Y是偶图G的完全匹配 若 V1 V2 则称Y为G的一个完美匹配 说明 1 若偶图G有完全匹配 则Y必是G的最大匹配 但反过来不一定 2 若G有完美匹配 则G的顶点数必是偶数并且对任意v Y中恰好有一条边与v关联 匹配 图中 粗边组成各图的一个匹配 1 中为完全匹配 2 中匹配不是完全匹配 2 中无完全匹配 3 中匹配是完全匹配 也是完美匹配 匹配 匹配问题 结婚问题 已知由若干个小伙子组成的集合F 若干个姑娘之集为G 姑娘们都渴望结婚 但也不希望媒人介绍 随便嫁给一个她不认识或不可接受的小伙子 实际上 每个姑娘心中都有一张可接受为配偶的小伙子名单 问在什么条件下才能把所有的姑娘都嫁出去 工作安排问题 一个车间有m个工人和n件不同的工作 每件工作只需一位工人干 而每位工人仅能熟练地干其中的几件工作 问在什么条件下车间主任能为每位工人分配一件他能胜任的工作呢 2个问题最终都抽象成偶图的完全匹配是否存在的问题 定理3 Hall定理 1935年 设G V1 V2 E 是一个偶图 V1 V2 G中存在从V1到V2的完全匹配充分必要条件是V1中任意k个顶点 k 1 2 V1 至少与V2中的k个顶点相连接 该条件称为相异性条件 Hall条件 Hall定理 相异性条件 许多问题提出了偶图的完全匹配的存在性问题 例1现有4名教师 张 王 李 赵 要求他们去教4门课程 数学 物理 电工和计算机科学 已知张能教数学和计算机科学 王能教物理和电工 李能教数学 物理和电工 赵只能教电工 如何安排才能使4位教师都能教课 并且每门课都有人教 共有几种方案 解 设V1 张 王 李 赵 V2 数学 物理 计算机 电工 某人能教某课程就在相应的顶点之间连一条线 得到一个偶图 此偶图G满足 相异性条件 因此存在V1到V2的完全匹配 但因赵只能教电工 因而王只能教物理 李就只能教数学 张也就只能教计算机科学了 即方案只有一种 实例 实例 例2 派遣问题 某课题组要从a b c d e5人中派3人分别到上海 广州 香港去开会 已知a只想去海 b只想去广州 c d e都表示想去广州或香港 问该课题组在满足个人要求的条件下 共有几种派遣方案 解 令G V1 V2 E 其中V1 s g x s g x分别表示上海 广州和香港 V2 a b c d e E u v u V1 v V2 v想去u 匹配问题进一步分析 结婚问题 工作安排问题 2个问题最终都抽象成偶图的完全匹配是否存在的问题 如果完全匹配存在 Hall条件成立 那么如何找到完全匹配呢 如果完全匹配不存在 Hall条件成立 那么如何找到最大匹配呢 稳定婚配问题 2012年10月15日晚间 瑞典皇家科学院宣布 将2012年诺贝尔经济学奖授予阿尔文 E 罗斯 AlvinE Roth 美国经济学家 哈佛大学商学院经济与商业管理学教授 和罗伊德 S 沙普利 LloydS Shapley 美国数学家 经济学家 加州大学洛杉矶分校数学和经济学名誉教授 授奖原因 稳定分配理论和市场设计中的实践 2012年两位经济学诺贝尔奖得主的 稳定配置理论 是他们获奖的基础 这个理论在现实中 包括男女婚姻搭配 病人和医院的配置 学生和学校的选配 病人互换捐肾者 等等 都有着广泛的 富有现实意义的 市场设计实践 2012年诺贝尔经济学奖关注了一个经济学的中心问题 如何尽可能恰当地匹配不同的市场主体 比如 学生须与学校相匹配 人体器官的捐献者必须同需要器官移植的患者相匹配 怎样才能使匹配尽可能有效地完成 什么样的方法对什么样的团体有益 2012年诺贝尔经济学奖授予的这两位学者 分别从稳定匹配的抽象理论和市场制度的实际设计这两个角度 对这些问题作出了回答 稳定婚配问题 稳定婚配问题 罗伊德 S 沙普利 LloydS Shapley 使用合作博弈的方法来研究和比对不同的匹配方法 关键问题在于保证一个配对是稳定的 所谓稳定 指的是两个主体都无法找到比当前匹配的主体更佳的匹配对象 Shapley和他的同事找到了一个方法 GS算法 Gale Shapleyalgorithm 亦称延迟认可算法这种方法能确保匹配是稳定的 稳定婚配问题 Shapley和已故的加州大学伯克利分校的数学及经济学教授大卫 盖尔 DavidGale 1921 2008 于1962年发表的一篇相关论文 稳定婚配问题 StableMarriageProblem 是Shapley获得经济学诺贝尔奖的最有革命性的文章 匈牙利算法 匈牙利算法 Hungarianmethod ItwasdevelopedandpublishedbyHaroldKuhnin1955 whogavethename Hungarianmethod becausethealgorithmwaslargelybasedontheearlierworksoftwoHungarianmathematicians D nesK nigandJen Egerv ry JamesMunkresreviewedthealgorithmin1957andobservedthatitis strongly polynomial SincethenthealgorithmhasbeenknownalsoasKuhn MunkresalgorithmorMunkresassignmentalgorithm timecomplexity O n4 匈牙利算法 匈牙利算法 Hungarianmethod EdmondsandKarp andindependentlyTomizawanoticedthatitcanbemodifiedtoachieveanO n3 runningtime FordandFulkersonextendedthemethodtogeneraltransportationproblems In2006 itwasdiscoveredthatCarlGustavJacobihadsolvedtheassignmentprobleminthe19thcentury andthesolutionhadbeenpublishedpos