第15节 偶图与匹配

集合论与图论1/29第15节偶图与匹配主要内容：偶图匹配集合论与图论2/29结婚(婚配)问题结婚问题：已知由若干个小伙子组成的集合F，若干个姑娘之集为G。姑娘们都渴望结婚，但也不希望媒人介绍，随便嫁给一个她不认识或不可接受的小伙子。实际上，每个姑娘心中都有一张可接受为配偶的小伙子名单。问在什么条件下才能把所有的姑娘都嫁出去？对这个问题，若把姑娘和小伙子用点来表示，若某位姑娘能接受某个小伙子，则在相应点间连一条线，则可以得到一个无向图G.集合论与图论3/29工作安排问题工作安排问题：一个车间有m个工人和n件不同的工作，每件工作只需一位工人干，而每位工人仅能熟练地干其中的几件工作.问在什么条件下车间主任能为每位工人分配一件他能胜任的工作呢？对这个问题，若把工人和每件工作用点来表示，若一位工人能胜任某项工作，则在相应点之间连一条线，则得到一个无向图G.集合论与图论4/29偶图(二部图、双图)定义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.集合论与图论5/29如果uV1，vV2均有{u,v}E，则这个偶图称为完全偶图，并记为K(m,n)或Km,n，其中V1=m，V2=n.完全偶图1、完全偶图Km,n有多少条边?有mn条边.2、完全偶图中有没有三角形?没有三角形.集合论与图论6/29定义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)=集合论与图论7/29定理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必然是偶数，也就是这个圈的长度为偶数.偶图的判别定理集合论与图论8/29充分性设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的最后的一个公共顶点.用反证法：偶图的判别定理集合论与图论9/29因为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是一个偶图.偶图的判别定理集合论与图论10/29不是偶图不是偶图实例集合论与图论11/29匹配定义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的一个最大匹配.集合论与图论12/29定义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关联.匹配集合论与图论13/29图中，粗边组成各图的一个匹配.(1)中为完全匹配，(2)中匹配不是完全匹配，(2)中无完全匹配，(3)中匹配是完全匹配，也是完美匹配.匹配集合论与图论14/29匹配问题结婚问题：已知由若干个小伙子组成的集合F，若干个姑娘之集为G。姑娘们都渴望结婚，但也不希望媒人介绍，随便嫁给一个她不认识或不可接受的小伙子。实际上，每个姑娘心中都有一张可接受为配偶的小伙子名单。问在什么条件下才能把所有的姑娘都嫁出去？工作安排问题：一个车间有m个工人和n件不同的工作，每件工作只需一位工人干，而每位工人仅能熟练地干其中的几件工作.问在什么条件下车间主任能为每位工人分配一件他能胜任的工作呢？2个问题最终都抽象成偶图的完全匹配是否存在的问题！集合论与图论15/29定理3(Hall定理,1935年)设G=(V1∪V2，E)是一个偶图，|V1|≤|V2|.G中存在从V1到V2的完全匹配充分必要条件是V1中任意k个顶点(k=1,2,…,|V1|)至少与V2中的k个顶点相连接.该条件称为相异性条件，Hall条件.Hall定理（相异性条件）许多问题提出了偶图的完全匹配的存在性问题.集合论与图论16/29例1现有4名教师：张、王、李、赵，要求他们去教4门课程：数学、物理、电工和计算机科学.已知张能教数学和计算机科学；王能教物理和电工；李能教数学、物理和电工；赵只能教电工.如何安排才能使4位教师都能教课，并且每门课都有人教？共有几种方案？解:设V1={张、王、李、赵}，V2={数学、物理、计算机、电工}.某人能教某课程就在相应的顶点之间连一条线，得到一个偶图.此偶图G满足“相异性条件”，因此存在V1到V2的完全匹配.但因赵只能教电工，因而王只能教物理，李就只能教数学，张也就只能教计算机科学了.即方案只有一种.实例集合论与图论17/29实例例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}.共有9种派遣方案.集合论与图论18/29匹配问题进一步分析结婚问题工作安排问题2个问题最终都抽象成偶图的完全匹配是否存在的问题！如果完全匹配存在(Hall条件成立)，那么如何找到完全匹配呢？如果完全匹配不存在(Hall条件成立)，那么如何找到最大匹配呢？集合论与图论19/29稳定婚配问题2012年10月15日晚间，瑞典皇家科学院宣布，将2012年诺贝尔经济学奖授予阿尔文·E·罗斯(AlvinE.Roth,美国经济学家，哈佛大学商学院经济与商业管理学教授)和罗伊德·S·沙普利（LloydS.Shapley,美国数学家、经济学家，加州大学洛杉矶分校数学和经济学名誉教授)。授奖原因：稳定分配理论和市场设计中的实践。2012年两位经济学诺贝尔奖得主的“稳定配置理论”是他们获奖的基础。这个理论在现实中，包括男女婚姻搭配、病人和医院的配置、学生和学校的选配、病人互换捐肾者，等等，都有着广泛的、富有现实意义的“市场设计实践”。集合论与图论20/292012年诺贝尔经济学奖关注了一个经济学的中心问题:如何尽可能恰当地匹配不同的市场主体。比如:学生须与学校相匹配，人体器官的捐献者必须同需要器官移植的患者相匹配。怎样才能使匹配尽可能有效地完成？什么样的方法对什么样的团体有益？2012年诺贝尔经济学奖授予的这两位学者，分别从稳定匹配的抽象理论和市场制度的实际设计这两个角度，对这些问题作出了回答。稳定婚配问题集合论与图论21/29稳定婚配问题罗伊德·S·沙普利(LloydS.Shapley)使用合作博弈的方法来研究和比对不同的匹配方法。关键问题在于保证一个配对是稳定的；所谓稳定，指的是两个主体都无法找到比当前匹配的主体更佳的匹配对象。Shapley和他的同事找到了一个方法:GS算法(Gale-Shapleyalgorithm)亦称延迟认可算法这种方法能确保匹配是稳定的。集合论与图论22/29稳定婚配问题Shapley和已故的加州大学伯克利分校的数学及经济学教授大卫-盖尔（DavidGale,1921-2008）于1962年发表的一篇相关论文：稳定婚配问题(StableMarriageProblem)，是Shapley获得经济学诺贝尔奖的最有革命性的文章。集合论与图论23/29匈牙利算法匈牙利算法(Hungarianmethod)ItwasdevelopedandpublishedbyHaroldKuhnin1955,whogavethenameHungarianmethodbecausethealgorithmwaslargelybasedontheearlierworksoftwoHungarianmathematicians:DénesKőnigandJenőEgerváry.JamesMunkresreviewedthealgorithmin1957andobservedthatitis(strongly)polynomial.SincethenthealgorithmhasbeenknownalsoasKuhn–MunkresalgorithmorMunkresassignmentalgorithm.timecomplexity:O(n4)集合论与图论24/29匈牙利算法匈牙利算法(Hungarianmethod)EdmondsandKarp,andindependentlyTomizawanoticedthatitcanbemodifiedtoachieveanO(n3)runningtime.FordandFulkersonextendedthemethodtogeneraltransportationproblems.In2006,itwasdiscoveredthatCarlGustavJacobihadsolvedtheassignmentprobleminthe19thcentury,andthesolutionhadbeenpublishedposthumouslyin1890inLatin.集合论与图论25/29匈牙利算法匈牙利算法(Hungarianmethod)匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想。它是偶图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求偶图最大匹配的算法。Matrixinterpretation集合论与图论26/29应用图像匹配图像配准图像融合图像拼接集合论与图论27/29应用图像匹配集合论与图论28/29应用图像配准集合论与图论29/29应用图像配准