第15节 偶图与匹配

1、集合集合论论与图论与图论1第第15节节 偶图与匹配偶图与匹配主要内容主要内容：l 偶图偶图l 匹配匹配集合集合论论与图论与图论2结婚结婚(婚配婚配)问题问题结婚问题结婚问题：已知由若干个小伙子组成的集合：已知由若干个小伙子组成的集合F，若干，若干个姑娘之集为个姑娘之集为G。姑娘们都渴望结婚，但也不希望媒。姑娘们都渴望结婚，但也不希望媒人介绍，随便嫁给一个她不认识或不可接受的小伙人介绍，随便嫁给一个她不认识或不可接受的小伙子。实际上，每个姑娘心中都有一张可接受为配偶子。实际上，每个姑娘心中都有一张可接受为配偶的小伙子名单。问在什么条件下才能把所有的姑娘的小伙子名单。问在什么条件下才能把所有的姑娘

2、都嫁出去？都嫁出去？对这个问题，若把姑娘和小伙对这个问题，若把姑娘和小伙子用点来表示，若某位姑娘能子用点来表示，若某位姑娘能接受某个小伙子，则在相应点接受某个小伙子，则在相应点间连一条线，则可以得到一个间连一条线，则可以得到一个无向图无向图G. 集合集合论论与图论与图论3工作安排问题工作安排问题工作安排问题：工作安排问题：一个车间有一个车间有m个工人和个工人和n件不同的工件不同的工作，每件工作只需一位工人干，而每位工人仅能熟作，每件工作只需一位工人干，而每位工人仅能熟练地干其中的几件工作练地干其中的几件工作. 问在什么条件下车间主任问在什么条件下车间主任能为每位工人分配一件他能胜任的工作呢？能

3、为每位工人分配一件他能胜任的工作呢？对这个问题，若把工人和每件对这个问题，若把工人和每件工作用点来表示，若一位工人工作用点来表示，若一位工人能胜任某项工作，则在相应点能胜任某项工作，则在相应点之间连一条线，则得到一个无之间连一条线，则得到一个无向图向图G.集合集合论论与图论与图论4偶图偶图(二部图、双图二部图、双图)定义定义1 G=(V, E)称为称为偶图偶图，如果，如果G的顶点集的顶点集V有一个二划有一个二划分分V1, V2，使得，使得G的任一条边的两个端点一个在的任一条边的两个端点一个在V1中，中，另一个在另一个在V2中中. 这个偶图有时记为这个偶图有时记为(V1, V2), E).定义定

4、义1 G=(V, E), 如果能将如果能将V分成分成V1和和V2使得使得V1V2=V, V1V2=, 且且G中的每条边的两个端点都一个属于中的每条边的两个端点都一个属于V1, 另一个属于另一个属于V2.集合集合论论与图论与图论5 如果如果 u V1，v V2均有均有u, v E，则这个偶图称为，则这个偶图称为完全偶图完全偶图，并记为，并记为K(m, n)或或Km, n，其中，其中V1 =m， V2 =n.完全偶图完全偶图1、完全偶图、完全偶图Km,n有多少条边有多少条边?有有mn条边条边.2、完全偶图中有没有三角形、完全偶图中有没有三角形?没有三角形没有三角形.集合集合论论与图论与图论6定义定

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)= 集合集合论论与图论与图论7定理定理1 图图G为偶图的充分必要条件是它

6、的所有圈的长度为偶图的充分必要条件是它的所有圈的长度都是偶数都是偶数.证证: 必要性必要性设设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、论与图论与图论8充分性充分性 设设G的每个圈的长为偶数，需证的每个圈的长为偶数，需证G是偶图是偶图.不妨设不妨设G是连通图，否则可分别考虑是连通图，否则可分别考虑G的每个支的每个支.任取任取G的一个顶点的一个顶点u，定义集合，定义集合 V1=vv V，d(u,v)是偶数是偶数， V2=vv V，d(u,v)是奇数是奇数， 则则V1,V2是是V的一个二划分，只要证明的一个二划分，只要证明V1中任意二顶中任意二顶点间无边，同时点间无边，同时V2中任意两顶点间也无边即可中任意两顶点间也无边即可. 假设假设w与与v是是V1的两个不同顶点，并且的两个不同顶点，并且v,w E，则令则令P是是u与与v间的最

8、短路，间的最短路，Q为为u与与w间的最短路，间的最短路，u1为从为从u开始，开始，P与与Q的最后的一个公共顶点的最后的一个公共顶点.用反证法：用反证法： 偶图的判别定理偶图的判别定理集合集合论论与图论与图论9 因为因为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中一个奇数长的圈，中一个奇数长的圈，这与已知矛

9、盾，所以这与已知矛盾，所以V1的任两不同顶点的任两不同顶点v与与w间无边间无边. 用完全一样的方法可证用完全一样的方法可证V2的任两顶点间也没边，的任两顶点间也没边，因此因此G是一个偶图是一个偶图.偶图的判别定理偶图的判别定理集合集合论论与图论与图论10不是偶图不是偶图不是不是偶图偶图实实 例例集合集合论论与图论与图论11匹匹 配配 定义定义3 设设G=(V,E)是一个图，则是一个图，则 (1)G的任两条不相邻的边的任两条不相邻的边x与与y称为是互相独立的称为是互相独立的. (2)若若Y E，且，且Y中任两条边都是互相独立的，则中任两条边都是互相独立的，则称称Y为为G的一个的一个匹配匹配. (

10、显然，若显然，若Y是图是图G的一个匹配，则任意的的一个匹配，则任意的vV，v至多与至多与Y 中的一条边关联中的一条边关联.) (3)设设Y是图是图G的一个匹配，若对的一个匹配，若对G的任一匹配的任一匹配Y ，恒有恒有|Y |Y |，则称，则称Y是图是图G的一个的一个最大匹配最大匹配. 集合集合论论与图论与图论12定义定义4 设设G=(V,E)是一个偶图且是一个偶图且V=V1V2，对，对任意任意xE，x是连接是连接V1的一个顶点与的一个顶点与V2的一个顶的一个顶点的边，则若存在一个点的边，则若存在一个 匹配匹配Y使得使得|Y|=min|V1|，|V2|，则称则称Y是偶图是偶图G的的完全匹配完全匹

11、配.若若|V1|V2|，则称，则称Y为为G的一个的一个完美匹配完美匹配.说明：说明：(1)若偶图若偶图G有完全匹配，则有完全匹配，则Y必是必是G的最大匹的最大匹配，但反过来不一定；配，但反过来不一定；(2)若若G有完美匹配，则有完美匹配，则G的顶点数必是偶数并且的顶点数必是偶数并且对任意对任意v，Y中恰好有一条边与中恰好有一条边与v关联关联. 匹匹 配配 集合集合论论与图论与图论13图中，图中，粗边粗边组成各图的一个匹配组成各图的一个匹配.(1)中为完全匹配，中为完全匹配，(2)中匹配不是完全匹配，中匹配不是完全匹配，(2)中无完全匹配，中无完全匹配，(3)中匹配是完全匹配，也是完美匹配中匹配

12、是完全匹配，也是完美匹配. 匹匹 配配 集合集合论论与图论与图论14匹配问题匹配问题 结婚问题结婚问题：已知由若干个小伙子组成的集合：已知由若干个小伙子组成的集合F，若干，若干个姑娘之集为个姑娘之集为G。姑娘们都渴望结婚，但也不希望媒。姑娘们都渴望结婚，但也不希望媒人介绍，随便嫁给一个她不认识或不可接受的小伙人介绍，随便嫁给一个她不认识或不可接受的小伙子。实际上，每个姑娘心中都有一张可接受为配偶子。实际上，每个姑娘心中都有一张可接受为配偶的小伙子名单。问在什么条件下才能把所有的姑娘的小伙子名单。问在什么条件下才能把所有的姑娘都嫁出去？都嫁出去？工作安排问题：工作安排问题：一个车间有一个车间有m

13、个工人和个工人和n件不同的工件不同的工作，每件工作只需一位工人干，而每位工人仅能熟作，每件工作只需一位工人干，而每位工人仅能熟练地干其中的几件工作练地干其中的几件工作. 问在什么条件下车间主任问在什么条件下车间主任能为每位工人分配一件他能胜任的工作呢？能为每位工人分配一件他能胜任的工作呢？2个问题最终都抽象成偶图的个问题最终都抽象成偶图的完全匹配完全匹配是否存在是否存在的问题！的问题！集合集合论论与图论与图论15定理定理3(Hall定理定理, 1935年年) 设设G=(V1V2，E)是一个是一个偶图，偶图，|V1|V2|. G中存在从中存在从V1到到V2的完全匹配的完全匹配充分必要条件充分必要

14、条件是是V1中任意中任意k个顶点个顶点(k=1, 2, , |V1|)至少与至少与V2中的中的k个顶点相连接个顶点相连接. 该条件称为该条件称为相异性条件，相异性条件，Hall条件条件.Hall定理（相异性条件）定理（相异性条件）许多问题提出了偶图的完全匹配的存在性问题许多问题提出了偶图的完全匹配的存在性问题. .集合集合论论与图论与图论16例例1 现有现有4名教师：张、王、李、赵，要求他们去名教师：张、王、李、赵，要求他们去 教教4门课程：数学、物理、电工和计算机科学门课程：数学、物理、电工和计算机科学. 已已知张能教数学和计算机科学；王能教物理和电工；知张能教数学和计算机科学；王能教物理和

15、电工；李能教数学、物理和电工；赵只能教电工李能教数学、物理和电工；赵只能教电工. 如何安如何安排才能使排才能使4位教师都能教课，并且每门课都有人位教师都能教课，并且每门课都有人教？共有几种方案？教？共有几种方案？ 解解: 设设V1=张、王、李、赵张、王、李、赵，V2=数学、物理、计数学、物理、计算机、电工算机、电工. 某人能教某课程就在相应的顶点之间某人能教某课程就在相应的顶点之间连一条线，得到一个偶图连一条线，得到一个偶图. 此偶图此偶图G满足满足“相异性相异性条条件件”，因此存在，因此存在V1到到V2的完全匹配的完全匹配. 但因赵只能教电工，因而王只能教物理，李就只能但因赵只能教电工，因而

16、王只能教物理，李就只能教数学，张也就只能教计算机科学了教数学，张也就只能教计算机科学了. 即方案只有即方案只有一种一种.实实 例例集合集合论论与图论与图论17实实 例例例例2 (派遣问题派遣问题)某课题组要从某课题组要从a, b, c, d, e 5人中派人中派3人分别到上海、广州、香港去开会人分别到上海、广州、香港去开会. 已知已知a只想去只想去海，海，b只想去广州，只想去广州，c, d, e都表示想去广州或香港都表示想去广州或香港. 问该课题组在满足个人要求的条件下，共有几种问该课题组在满足个人要求的条件下，共有几种派遣方案？派遣方案？ 解：解：令令G=(V1V2,E)，其中其中V1=s,

17、 g, x，s, g, x分别表示上海、广州分别表示上海、广州和香港和香港. V2=a, b, c, d, e, E=(u,v) | u V1, v V2, v想去想去u. 共有共有9 种派遣方案种派遣方案.集合集合论论与图论与图论18匹配问题进一步分析匹配问题进一步分析 结婚问题结婚问题工作安排问题工作安排问题2个问题最终都抽象成偶图的个问题最终都抽象成偶图的完全匹配完全匹配是否存在是否存在的问题！的问题！如果完全匹配存在如果完全匹配存在 (Hall条件成立条件成立)，那么如何找，那么如何找到完全匹配呢？到完全匹配呢？如果完全匹配不存在如果完全匹配不存在 (Hall条件成立条件成立)，那么如

18、何，那么如何找到最大匹配呢？找到最大匹配呢？集合集合论论与图论与图论19稳定婚配问题稳定婚配问题2012年年10月月15日晚间，瑞典皇家科学院宣布，将日晚间，瑞典皇家科学院宣布，将2012年诺贝尔经济学奖授予年诺贝尔经济学奖授予阿尔文阿尔文E罗斯罗斯(Alvin E. Roth, 美国经济学家，哈佛大学商学院经济与商业管理学教美国经济学家，哈佛大学商学院经济与商业管理学教授授)和和罗伊德罗伊德S沙普利沙普利（Lloyd S. Shapley, 美国数学美国数学家、经济学家，加州大学洛杉矶分校数学和经济学名家、经济学家，加州大学洛杉矶分校数学和经济学名誉教授誉教授)。授奖原因：稳定分配理论和市场

19、设计中的实践。授奖原因：稳定分配理论和市场设计中的实践。2012年两位经济学诺贝尔奖得主的年两位经济学诺贝尔奖得主的“稳定配置理论稳定配置理论”是他们获奖的基础。这个理论在现实中，包括男女是他们获奖的基础。这个理论在现实中，包括男女婚姻搭配、病人和医院的配置、学生和学校的选配、婚姻搭配、病人和医院的配置、学生和学校的选配、病人互换捐肾者，等等，都有着广泛的、富有现实病人互换捐肾者，等等，都有着广泛的、富有现实意义的意义的“市场设计实践市场设计实践”。集合集合论论与图论与图论202012年诺贝尔经济学奖关注了一个经济学的中心问题年诺贝尔经济学奖关注了一个经济学的中心问题:如何尽可能恰当地匹配不同

20、的市场主体。如何尽可能恰当地匹配不同的市场主体。比如比如: 学生须与学校相匹配，人体器官的捐献者必须学生须与学校相匹配，人体器官的捐献者必须同需要器官移植的患者相匹配。同需要器官移植的患者相匹配。怎样才能使匹配尽可能有效地完成？怎样才能使匹配尽可能有效地完成？什么样的方法对什么样的团体有益？什么样的方法对什么样的团体有益？2012年诺贝尔经济学奖授予的这两位学者，分别从年诺贝尔经济学奖授予的这两位学者，分别从稳稳定匹配定匹配的抽象理论和市场制度的实际设计这两个角的抽象理论和市场制度的实际设计这两个角度，对这些问题作出了回答。度，对这些问题作出了回答。稳定婚配问题稳定婚配问题集合集合论论与图论与

21、图论21稳定婚配问题稳定婚配问题罗伊德罗伊德S沙普利沙普利(Lloyd S. Shapley)使用合作博弈的方使用合作博弈的方法来法来研究和比对不同的匹配方法研究和比对不同的匹配方法。关键问题在于保证一个配对是稳定的；关键问题在于保证一个配对是稳定的；所谓稳定，指的是两个主体都无法找到比当前匹配的所谓稳定，指的是两个主体都无法找到比当前匹配的主体更佳的匹配对象。主体更佳的匹配对象。Shapley和他的同事找到了一个方法和他的同事找到了一个方法:GS算法算法(Gale-Shapley algorithm)亦称亦称 延迟认可算法延迟认可算法 这种方法能确保匹配是稳定的。这种方法能确保匹配是稳定的。

22、集合集合论论与图论与图论22稳定婚配问题稳定婚配问题Shapley和已故的加州大学伯克利分校的数学及经济和已故的加州大学伯克利分校的数学及经济学学教授大卫教授大卫-盖尔（盖尔（David Gale, 1921-2008）于）于1962年发年发表的一篇相关论文：稳定婚配问题表的一篇相关论文：稳定婚配问题(Stable Marriage Problem)，是，是Shapley获得经济学诺贝尔奖的最有革命获得经济学诺贝尔奖的最有革命性的文章。性的文章。集合集合论论与图论与图论23匈牙利算法匈牙利算法匈牙利算法匈牙利算法(Hungarian method)It was developed and pu

23、blished by Harold Kuhn in 1955, who gave the name Hungarian method because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dnes Knig and Jen Egervry.James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm has been known also as KuhnMunkres algorithm or Munkres assignment algorithm. time complexity: O(n4)集合集合论论与图论与图论24匈牙利算法匈牙利算法匈牙利算法匈牙利