偶图与匹配

集合论 与图论第15节 偶图与匹配主要内容： l 偶图 l 匹配1集合论 与图论结婚(婚配)问题结婚问题：已知由若干个小伙子组成的集合F，若干 个姑娘之集为G姑娘们都渴望结婚，但也不希望媒 人介绍，随便嫁给一个她不认识或不可接受的小伙 子实际上，每个姑娘心中都有一张可接受为配偶 的小伙子名单问在什么条件下才能把所有的姑娘 都嫁出去？对这个问题，若把姑娘和小伙 子用点来表示，若某位姑娘能 接受某个小伙子，则在相应点 间连一条线，则可以得到一个 无向图G. 2集合论 与图论工作安排问题工作安排问题：一个车间有m个工人和n件不同的工 作，每件工作只需一位工人干，而每位工人仅能熟 练地干其中的几件工作. 问在什么条件下车间主任 能为每位工人分配一件他能胜任的工作呢？对这个问题，若把工人和每件 工作用点来表示，若一位工人 能胜任某项工作，则在相应点 之间连一条线，则得到一个无 向图G.3集合论 与图论偶图(二部图、双图)定义1 G=(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.4集合论 与图论如果uV1，vV2均有{u, v}E，则这个偶图称为 完全偶图，并记为K(m, n)或Km, n，其中V1=m，V2=n.完全偶图1、完全偶图Km,n有多少条边?有mn条边.2、完全偶图中有没有三角形 ?没有三角形. 5集合论 与图论定义2 G=(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)=6集合论 与图论定理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必 然是偶数，也就是这个圈的长度为偶数.偶图的判别定理7集合论 与图论充分性 设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的最后的一个公共顶点.用反证法：偶图的判别定理8集合论 与图论因为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是一个偶图.偶图的判别定理9集合论 与图论不是偶图不是偶图实 例10集合论 与图论匹 配 定义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的一个最大匹配. 11集合论 与图论定义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关联. 匹 配 12集合论 与图论图中，粗边组成各图的一个匹配. (1)中为完全匹配， (2)中匹配不是完全匹配， (2)中无完全匹配， (3)中匹配是完全匹配，也是完美匹配. 匹 配 13集合论 与图论匹配问题 结婚问题：已知由若干个小伙子组成的集合F，若干 个姑娘之集为G。

姑娘们都渴望结婚，但也不希望媒 人介绍，随便嫁给一个她不认识或不可接受的小伙 子实际上，每个姑娘心中都有一张可接受为配偶 的小伙子名单问在什么条件下才能把所有的姑娘 都嫁出去？ 工作安排问题：一个车间有m个工人和n件不同的工 作，每件工作只需一位工人干，而每位工人仅能熟 练地干其中的几件工作. 问在什么条件下车间主任 能为每位工人分配一件他能胜任的工作呢？2个问题最终都抽象成偶图的完全匹配是否存在 的问题！14集合论 与图论定理3(Hall定理, 1935年) 设G=(V1∪V2，E)是一个 偶图，|V1|≤|V2|. G中存在从V1到V2的完全匹配 充分必要条件是V1中任意k个顶点(k=1, 2, …, |V1|) 至少与V2中的k个顶点相连接.该条件称为相异性条件，Hall条件.Hall定理（相异性条件）许多问题提出了偶图的完全匹配的存在性问题.15集合论 与图论例1 现有4名教师：张、王、李、赵，要求他们去 教4门课程：数学、物理、电工和计算机科学. 已 知张能教数学和计算机科学；王能教物理和电工； 李能教数学、物理和电工；赵只能教电工. 如何安 排才能使4位教师都能教课，并且每门课都有人 教？共有几种方案？ 解: 设V1={张、王、李、赵}，V2={数学、物理、计 算机、电工}. 某人能教某课程就在相应的顶点之间 连一条线，得到一个偶图. 此偶图G满足“相异性条 件”，因此存在V1到V2的完全匹配. 但因赵只能教电工，因而王只能教物理，李就只能 教数学，张也就只能教计算机科学了. 即方案只有 一种.实 例16集合论 与图论实 例例2 (派遣问题)某课题组要从a, b, c, d, e 5人中派 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}. 共有9 种派遣方案.17集合论 与图论匹配问题进一步分析 结婚问题 工作安排问题2个问题最终都抽象成偶图的完全匹配是否存在 的问题！如果完全匹配存在 (Hall条件成立)，那么如何找 到完全匹配呢？如果完全匹配不存在 (Hall条件成立)，那么如何 找到最大匹配呢？18集合论 与图论稳定婚配问题2012年10月15日晚间，瑞典皇家科学院宣布，将2012 年诺贝尔经济学奖授予阿尔文·E·罗斯(Alvin E. Roth,美国经济学家，哈佛大学商学院经济与商业管理学教 授)和罗伊德·S·沙普利（Lloyd S. Shapley, 美国数学 家、经济学家，加州大学洛杉矶分校数学和经济学名 誉教授)。

授奖原因：稳定分配理论和市场设计中的实践 2012年两位经济学诺贝尔奖得主的“稳定配置理论” 是他们获奖的基础这个理论在现实中，包括男女 婚姻搭配、病人和医院的配置、学生和学校的选配、 病人互换捐肾者，等等，都有着广泛的、富有现实 意义的“市场设计实践”19集合论 与图论2012年诺贝尔经济学奖关注了一个经济学的中心问题: 如何尽可能恰当地匹配不同的市场主体 比如: 学生须与学校相匹配，人体器官的捐献者必须 同需要器官移植的患者相匹配 怎样才能使匹配尽可能有效地完成？ 什么样的方法对什么样的团体有益？2012年诺贝尔经济学奖授予的这两位学者，分别从稳 定匹配的抽象理论和市场制度的实际设计这两个角 度，对这些问题作出了回答稳定婚配问题20集合论 与图论稳定婚配问题罗伊德·S·沙普利(Lloyd S. Shapley)使用合作博弈的方 法来研究和比对不同的匹配方法 关键问题在于保证一个配对是稳定的； 所谓稳定，指的是两个主体都无法找到比当前匹配的 主体更佳的匹配对象 Shapley和他的同事找到了一个方法: GS算法(Gale-Shapley algorithm) 亦称 延迟认可算法 这种方法能确保匹配是稳定的。

21集合论 与图论稳定婚配问题Shapley和已故的加州大学伯克利分校的数学及经济学 教授大卫-盖尔（David Gale, 1921-2008）于1962年发 表的一篇相关论文：稳定婚配问题(Stable Marriage Problem)，是Shapley获得经济学诺贝尔奖的最有革命 性的文章22集合论 与图论匈牙利算法匈牙利算法(Hungarian method)It was developed and published by Harold Kuhn in1955, who gave the name “Hungarian method“ because the algorithm was largely based on the earlierworks of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.James Munkres reviewed the algorithm in 1957 andobserved that it is (strongly) polynomial. Since then the algorithm has been known also asKuhn–Munkres algorithm or Munkres assignment algorithm. time complexity: O(n4)23集合论 与图论匈牙利算法匈牙利算法(Hungarian method)Edmonds and Karp, and independently Tomizawanoticed that it can be modified to achieve an O(n3) running time. Ford and Fulkerson extended the method to general transportation problems. In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in1890 in Latin.24集合论 与图论匈牙利算法匈牙利算法(Hungarian method)匈牙利算法是由匈牙利数学家。