Hall定理-南京大学课件.ppt

1、Department of Computer Science and Technology,Nanjing University二部图中的匹配二部图中的匹配离散数学课程组离散数学课程组南京大学计算机科学与技术系南京大学计算机科学与技术系 June.2016 2Department of Computer Science and Technology,Nanjing University内容提要内容提要引言引言二部图中完备匹配（二部图中完备匹配（Hall定理）定理）二部图中的最大匹配二部图中的最大匹配二部图中的稳定匹配二部图中的稳定匹配 June.2016 3Department of Comp

2、uter Science and Technology,Nanjing University孤岛上的婚姻孤岛上的婚姻成就最多幸福婚姻的配对方案成就最多幸福婚姻的配对方案互不相邻互不相邻的边集的边集 June.2016 4Department of Computer Science and Technology,Nanjing University图中的匹配图中的匹配匹配（边独立集）匹配（边独立集）：互不相邻互不相邻的边的集合的边的集合M-饱和点：饱和点：M中各边的端点中各边的端点匹配数匹配数 1=3匹配数匹配数 1=4极大匹配极大匹配最大匹配最大匹配完美匹配完美匹配M-饱和点饱和点M-饱和点饱

3、和点 June.2016 5Department of Computer Science and Technology,Nanjing University二部图中的完备匹配二部图中的完备匹配 定义：设定义：设G是二部图，二部划分为是二部图，二部划分为，若，若G中的匹配中的匹配M饱和饱和V1中所有顶点，则称中所有顶点，则称M为为V1到到V2的的完备匹配完备匹配。注意：完备匹配一定是最大匹配，但仅当注意：完备匹配一定是最大匹配，但仅当|V1|=|V2|才才是完美匹配是完美匹配。无完备匹配？无完备匹配？V1到到V2的完备匹配的完备匹配存在完美匹配存在完美匹配 June.2016 6Departme

4、nt of Computer Science and Technology,Nanjing University二部图中的完备匹配（举例）二部图中的完备匹配（举例）V1=1,2,3,4,5,6,是否存在饱和是否存在饱和V1的配对方案？的配对方案？A1B2C3D4E5F6GA,C,FA,CA,FC,F饱和饱和1,3,4,6？June.2016 7Department of Computer Science and Technology,Nanjing UniversityHall定理定理 Hall定理定理(1935,Marriage Theorem)设二部图设二部图G=,则则G有有V1到到V2的

5、完备匹配的完备匹配 A V1，|N(A)|A|证明证明.必要性易证，下证充分性（使用强归纳法）。必要性易证，下证充分性（使用强归纳法）。如果如果|V1|=1,充分性命题显然成立。充分性命题显然成立。假设当假设当|V1|k(k 1)时充分性命题均成立时充分性命题均成立,要证要证:当当|V1|=k+1时充分性命题也成立。分二种情形来证明。时充分性命题也成立。分二种情形来证明。(1)对对V1的任意真子集的任意真子集A，|N(A)|A|(2)存在存在 V1的一个真子集的一个真子集A，|N(A)|=|A|June.2016 8Department of Computer Science and Tech

6、nology,Nanjing UniversityHall定理定理 H满足归纳假设的条件满足归纳假设的条件,从而从而 H有有V1-v到到V2-w的完备匹配的完备匹配.这个匹配加上边这个匹配加上边(v,w)构成构成G的从的从V1到到V2的完备匹配的完备匹配.vw归纳证明归纳证明.(1)对对V1的任意真子集的任意真子集A,|N(A)|A|任取一个顶点任取一个顶点v V1,任取任取w N(v).H=G-v,w是一个二部图（非空）是一个二部图（非空）.June.2016 9Department of Computer Science and Technology,Nanjing UniversityH

7、all定理定理(2)存在存在 V1的一个真子集的一个真子集A,|N(A)|=|A|.记记B=N(A).据归纳假设据归纳假设,存在存在A到到B 的完备匹配的完备匹配.二部图二部图H=G-A-B 满足归纳假设条件满足归纳假设条件.AB否则否则,存在存在C V1-A.|NH(C)|C|.|NG(C A)|NH(C)|+|B|C|+|B|=|C|+|A|=|C A|.矛盾矛盾.据归纳假设据归纳假设,存在存在V1-A到到V2-B的完备匹配的完备匹配.合并上述两个匹配得到一个合并上述两个匹配得到一个V1到到V2的完备匹配的完备匹配.得证得证 June.2016 10Department of Comput

8、er Science and Technology,Nanjing UniversityHall定理的推论定理的推论设二部图设二部图G是一个是一个k-正则的正则的(k 1),则则G有完美匹配有完美匹配.证明证明.不妨设不妨设G=,k|A|=k|B|,所以所以|A|=|B|.下证下证G有有A到到B的完备匹配的完备匹配.对任一对任一S A，S与与N(S)之间总共有之间总共有k|S|条边，而与条边，而与N(S)相关的边总共有相关的边总共有k|N(S)|条边。条边。k|S|k|N(S)|N(S)|S|根据根据Hall定理，定理，G有有A到到B的完备匹配，因的完备匹配，因|A|=|B|，该匹配是完美匹配

9、。该匹配是完美匹配。June.2016 11Department of Computer Science and Technology,Nanjing University完备匹配的一个充分条件完备匹配的一个充分条件二部图二部图G=(V1,V2,E),若若V1中每个顶点至少关联中每个顶点至少关联t条边，条边，而若而若V2中每个顶点至多关联中每个顶点至多关联t条边，则条边，则G中存在中存在V1到到V2的完备匹配。的完备匹配。证明类似于上述推论，证明类似于上述推论，t|S|t|N(S)|。June.2016 12Department of Computer Science and Technolo

10、gy,Nanjing University交错路径与可增广交错路径交错路径与可增广交错路径定义：设定义：设M是是G中一个匹配。若中一个匹配。若G中路径中路径P中中M与与EG-M中的边交替出现，则称中的边交替出现，则称P为为M-交错路径交错路径(也可也可以是回路以是回路)；若；若P的起点与终点都是的起点与终点都是M-非饱和点非饱和点（没有被匹配的顶点），则称（没有被匹配的顶点），则称P是是可增广交错路径可增广交错路径（增广路径）（增广路径）。可增广交错路可增广交错路 June.2016 13Department of Computer Science and Technology,Nanjing

11、 University最大匹配最大匹配Berges Lemma(1957).M是最大匹配是最大匹配 相对于相对于M没没有增广路径有增广路径 证明证明.容易证明必要性，下证充分性容易证明必要性，下证充分性.假设有一个更大的匹配假设有一个更大的匹配M.令令G=(V,M M).G中中各顶点的度最多为各顶点的度最多为2.因此因此,G的各连通分支要么是的各连通分支要么是路径路径(孤立点也看作路径孤立点也看作路径),要么是回路要么是回路.无论是路径无论是路径还是回路，来自还是回路，来自M 的边与来自的边与来自M的边一定是交错的边一定是交错的的.June.2016 14Department of Compu

12、ter Science and Technology,Nanjing University最大匹配最大匹配若是回路若是回路,来自来自M 的边数等于来自的边数等于来自M的边数的边数.因为因为|M|M|,故必有一条路径包含故必有一条路径包含M的边多于的边多于M的边的边,从而是相对于从而是相对于M的增广路径的增广路径.得证得证 June.2016 15Department of Computer Science and Technology,Nanjing University增广路径的算法思想增广路径的算法思想在二部图中直接使用增广路径的匹配算法在二部图中直接使用增广路径的匹配算法找增广路径找增广

13、路径,对对M进行增广进行增广,一直至没有增广路径一直至没有增广路径.复杂度复杂度 O(|V|E|)，最大匹配的元素个数，最大匹配的元素个数|V|/2 June.2016 16Department of Computer Science and Technology,Nanjing University稳定匹配（稳定的婚姻）稳定匹配（稳定的婚姻）G的一个偏好集的一个偏好集 一族线性序一族线性序(v)v V，其中，其中，v是是E(v)上的线性序。上的线性序。Unstable:If M is a matching and e=(a,b)is an edge not in M such that bo

14、th a and b prefer e to their current matching edge.egfab June.2016 17Department of Computer Science and Technology,Nanjing University稳定匹配（稳定的婚姻）稳定匹配（稳定的婚姻）定理定理 1.4.(Gale&Shapley 1962)任意给定一个偏好集，二步图任意给定一个偏好集，二步图G有一个稳定的匹配。有一个稳定的匹配。efe v fefe v fG中一个匹配中一个匹配M 是稳定的是稳定的 对任意一个对任意一个e EM，存在，存在 f M满足：满足：(i)e 和

15、和f 有公共端点有公共端点v，(ii)e v f.June.2016 18Department of Computer Science and Technology,Nanjing University稳定匹配（稳定的婚姻）稳定匹配（稳定的婚姻）思路思路男子向尚未拒绝他的最喜爱的女子求婚男子向尚未拒绝他的最喜爱的女子求婚.女子接受目前为止最如意的求婚提议，但是，倘若女子接受目前为止最如意的求婚提议，但是，倘若有更如意的求婚者，会改变主意。有更如意的求婚者，会改变主意。June.2016 19Department of Computer Science and Technology,Nanjin

16、g University稳定匹配（稳定的婚姻）稳定匹配（稳定的婚姻）Example.Given men x,y,z,w,women a,b,c,d,and preferences listed below,the matching xa,yb,zd,wc is a stable matching.Menx,y,z,w Women a,b,c,dx:a b c d a:z x y wy:a c b d b:y w x zz:c d a b c:w x y zw:c b a d d:x y z wXaYbZcWd June.2016 20Department of Computer Science

17、 and Technology,Nanjing University稳定匹配（稳定的婚姻）稳定匹配（稳定的婚姻）x:a b c d a:z x y wy:a c b d b:y w x zz:c d a b c:w x y zw:c b a d d:x y z wXaYbZcWdY June.2016 21Department of Computer Science and Technology,Nanjing University稳定匹配（稳定的婚姻）稳定匹配（稳定的婚姻）术语术语给定给定M，aA可被可被bB接受接受(a,b)EM，并且，并且若存在若存在(a,b)M,则则(a,b)b(a,b

18、).aA对对M满意满意a是一个尚未配对的顶点，或者是一个尚未配对的顶点，或者存在存在(a,b)M,若若a可被可被b接受，则接受，则(a,b)a(a,b)June.2016 22Department of Computer Science and Technology,Nanjing University稳定匹配（稳定的婚姻）稳定匹配（稳定的婚姻）算法算法从一个空的边集开始，构造（更新）匹配从一个空的边集开始，构造（更新）匹配M，保持，保持“A中的所有顶点对中的所有顶点对M满意满意”这一特性。这一特性。给定这样的一个给定这样的一个M,对于对于A中尚未配对的某顶点中尚未配对的某顶点a，若，若(a,

19、b)|a可被可被b接受接受非空非空.按照线性序按照线性序a找出最大元，记为找出最大元，记为(a,bj)，将这条边添加到，将这条边添加到M中，删除中，删除M中以中以bj为端点的边（假如有的话）。为端点的边（假如有的话）。对于对于A中尚未配对的所有顶点中尚未配对的所有顶点a，(a,b)|a可被可被b接受接受均为均为空空.（结束）（结束）June.2016 23Department of Computer Science and Technology,Nanjing University稳定匹配（稳定的婚姻）稳定匹配（稳定的婚姻）算法正确性分析算法正确性分析结束之时结束之时A中的所有顶点对中的所有顶

20、点对M满意满意A中未配对的顶点均没有可被接受的对象中未配对的顶点均没有可被接受的对象结束之时，结束之时，M是稳定的是稳定的 对任意一个对任意一个e EM，存在，存在 f M满足满足：(i)e 和和f 有公共端点有公共端点;(ii)e vf.egf June.2016 24Department of Computer Science and Technology,Nanjing University稳定匹配（稳定的婚姻）稳定匹配（稳定的婚姻）算法正确性分析算法正确性分析算法是否会结束？算法是否会结束？M越来越好，至于不能更好。越来越好，至于不能更好。何为何为“好好”:M 比比M好好对于对于B中任

21、一顶点中任一顶点b，若，若b是某个边是某个边f M的端点，则的端点，则b必是必是某个边某个边fM的端点，且的端点，且f b f.（B中顶点有更好的配对）中顶点有更好的配对）June.2016 25Department of Computer Science and Technology,Nanjing University工作分配问题工作分配问题问题：问题：n个毕业生有可供选择的个毕业生有可供选择的m个岗位，每个毕业个岗位，每个毕业生给出若干个志愿，是否存在每个人都满意的分配生给出若干个志愿，是否存在每个人都满意的分配方案。方案。数学模型：建立二部图，数学模型：建立二部图，V1中每个点对应一个

22、毕业中每个点对应一个毕业生，生，V2中每个点对应一个可选的岗位，中每个点对应一个可选的岗位，uv E当且仅当且仅当当u对应的毕业生愿意选择对应的毕业生愿意选择v对应的岗位。对应的岗位。问题的解：问题有解当且仅当问题的解：问题有解当且仅当G有饱和有饱和V1中所有顶点中所有顶点的完备匹配。的完备匹配。June.2016 26Department of Computer Science and Technology,Nanjing University工作分配问题的一般形式工作分配问题的一般形式工作分配问题工作分配问题某机构提供某机构提供m个空缺职位个空缺职位,有有n个申请者。每个申请者满足个申请者

23、。每个申请者满足某些职位的要求某些职位的要求。是否可能使每个申请者得到一个他是否可能使每个申请者得到一个他/她适合的职位？她适合的职位？若不能，最多多少申请者能够被分配到合适的职位？若不能，最多多少申请者能够被分配到合适的职位？如何实现一个最佳分配方案？如何实现一个最佳分配方案？June.2016 27Department of Computer Science and Technology,Nanjing University工作分配问题的求解模型工作分配问题的求解模型AaiBbj.申请者集合申请者集合职位的集合职位的集合aibj EG iff.ai 适合于适合于 bj在此模型中如何在此模型

24、中如何解释问题的解？解释问题的解？June.2016 28Department of Computer Science and Technology,Nanjing University棋盘上的士兵棋盘上的士兵要在左图所示的棋盘上放置要在左图所示的棋盘上放置4个士兵，任何一行或者一个士兵，任何一行或者一列恰好放一个，但不能放在列恰好放一个，但不能放在有标记的格子中。有标记的格子中。构造一个二步图，构造一个二步图，ai表示行，表示行，bi表示列。表示列。aibj E 当且仅当第当且仅当第i行第行第j列的方格没有标记。列的方格没有标记。oooo June.2016 29Department of

25、Computer Science and Technology,Nanjing University作业作业教材教材9.2p.468：27,28 June.2016 30Department of Computer Science and Technology,Nanjing UniversityExercise(II)1.从下图从下图G=(A,B,E)中中,找出相对于匹配找出相对于匹配M(粗边的集合粗边的集合)的任意三条交错路径的任意三条交错路径(alternating path)和两条增广和两条增广路径路径(augmenting path)。然后利用找出的增广路径。然后利用找出的增广路径扩

26、大扩大M.a0a1a2a3a4a5b0b1b2b3b4b5 June.2016 31Department of Computer Science and Technology,Nanjing UniversityExercise(II)2.对于每一个二部图对于每一个二部图G=(A,B,E),判断判断G是否有饱和是否有饱和A的匹配。如果没有，请说明理由的匹配。如果没有，请说明理由a0a1a2a3b2b1b0AB1)a0a1a2b3b2b1b0AB2)a0a1a2a3b2b1b0AB3)a4b3b4b5a0a1a2a3b2b1b0AB4)a4b3b4 June.2016 32Department

27、of Computer Science and Technology,Nanjing UniversityExercise(II)3.令令k为一整数。对于任意有限集合，证明对它的任意为一整数。对于任意有限集合，证明对它的任意 两个划分两个划分 都存在一个相同的代表集。都存在一个相同的代表集。说明：）划分指划分为大小相同的互不想交的个子集，为简便起见，设集说明：）划分指划分为大小相同的互不想交的个子集，为简便起见，设集合的大小为的整数倍从而每个子集均有相同个元素。合的大小为的整数倍从而每个子集均有相同个元素。）一个划分的代表集指从每个子集中取出一个元素而构成的集合。）一个划分的代表集指从每个子集

28、中取出一个元素而构成的集合。举例：集合举例：集合 1,2,3,4 1,2,3,4的一个划分为的一个划分为 A:1,2 3,4.A:1,2 3,4.此划分的代表集有此划分的代表集有 1,3 1,3，2,3 2,3，1,4 1,4，2,4,2,4,但但 1,2 1,2不是其代表集不是其代表集.集合的另外一个划分为集合的另外一个划分为 B:2,3 B:2,3 1,4.1,4.易见，与存在相同的代表集易见，与存在相同的代表集 1,3 1,3。可以试验，任意两个划分均存在相同的。可以试验，任意两个划分均存在相同的代表集。代表集。June.2016 33Department of Computer Sci

29、ence and Technology,Nanjing University拓展题拓展题4.找出一个二部图和一组偏好找出一个二部图和一组偏好(preference),使得在此图使得在此图中所有最大匹配均不是稳定匹配而所有稳定匹配均不是中所有最大匹配均不是稳定匹配而所有稳定匹配均不是最大匹配最大匹配（Find a bipartite graph and a set of preferences such that no matching of maximal size is stable and no stable matching has maximal size.）5.找出一个非二部图（找出一个非二部图（non-bipartite graph）和一组偏）和一组偏好，使得图中不存在稳定匹配好，使得图中不存在稳定匹配。June.2016 34Department of Computer Science and Technology,Nanjing UniversityQ&A参考文献参考文献Reinhard Diestel.Graph Theory.Springer,Heidelberg,2005