图论-的配对问题

第五章匹配§1最大匹配－1具体问题描述：有n个女士和n个男士参加舞会，每位女士与其中若干位男士相识，每位男士与其中若干位女士相识，问如何安排，使得尽量多配对的男女舞伴相识。f1f2m1f3f4f5m2m3m4m5§1匹配§1最大匹配－1下图就是一种分配方法：f1f2m1f3f4f5m2m3m4m5(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓“人员分配问题”和“最优分配问题”中有重要作用。假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生配对？类似的工作分配问题：现有n个人，m份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？§1最大匹配－定义定义：若图G=(V,E)的顶点可以分成X，Y两个子集，每个子集里的顶点互不相邻，这样的图称为二分图。f1f2m1f3f4f5m2m3m4m5§1最大匹配－定义1定义：若M是图G=(V,E)的边子集，且M中的任意两条边在G中不相邻，则称M为G中的一个匹配，M中的每条边的两个端点称为是M-饱和的的。f1f2m1f3f4f5m2m3m4m5M={(f1,m2),(f2,m1),(f3,m4),(f4,m5)}§1最大匹配－定义2定义：若图G中每个顶点均被M许配时，称M为G中的一个完美匹配。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}§1最大匹配－定义3定义：图G中边数最多的匹配M，称为G中的一个最大匹配。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5§1最大匹配－定义4定义：若匹配M的某边和顶点v关联，称v是M-饱和的，否则就是M-不饱和的。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5饱和的不饱和的§1最大匹配－定义5定义：若M是图G的一个匹配，若从G中一个顶点到另一个顶点存在一条道路，此路径由属于M和不属于M的边交替出现组成的，则称此路径为M-交错路。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}P=f1m3f4m5f2m1f5m4§1最大匹配－定义6定义：若交错路的两个端点为关于M的不饱和顶点时，称此交互道为可增广道路。M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一条可增广道路。f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5§1最大匹配－定义8f1f2m1f3f4f5m2m3m4m5M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一条可增广道路。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}§1最大匹配－Berge定理定理7.1(Berge1957)：M为最大匹配的充要条件是：图G中不存在可增广道路。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5[引理]设P是匹配Ｍ-可增广道路，则PM是一个比M更大的匹配，且|PM｜＝|M|+1.[定理1](Berge)设G=(V,E)，M为G中匹配，则M为G的最大匹配当且仅当G中不存在M可增广道。[证明]必要性：如有M-可增广道路，则有更大匹配。矛盾！充分性：如果有最大匹配M’,|M’||M|.考虑MM’，在可增广路中，第一条边与最后一条边都不是中的边，因而可增广路中属于的边数比不在中边数少一条。MMMMMM实线边，M’虚线边MM’其中每个结点的最多与Ｍ边和一个M’边关联，每条道路是M边和M’边交互道路。其中回路包含相同数目的M边和M’边。由|M’||M|,必存在M’边开始，M‘边终止的M交互道路，即M-可增广道路，矛盾！§2Hall定理设有m个人，n项工作，每个人会做其中的若干项工作，能不能适当安排，使得每个人都有工作做？w1w2m1w3w4w5m2m3m4§2Hall定理当mn时，肯定是不可能的，即使是m≤n也不一定。但如果每个人能做的工作越多，越容易实现。w1w2m1w3w4w5m2m3m4§2Hall定理－1Hall定理(1935)：二分图G存在一匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X任一子集A，及与A邻接的点集为N(A)，恒有：|N(A)|≥|A|。w1w2m1w3w4w5m2m3m4YX§3人员分派问题1965年，匈牙利著名数学家Edmonds设计了一种求最大匹配的算法，称为匈牙利(Hungarian)算法。工作分配问题：现有n个人，n份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？§3匈牙利算法匈牙利(Hungarian)算法：（1）任给一个初始匹配；（2）若X已经饱和，结束；否则转（3）；（3）在X中找一个非饱和点x0，V1={x0}，V2=空集；（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2；（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】§3匈牙利算法例用匈牙利算法求下图的最大匹配：例x1x2y1x3x4x5y2y3y4y5§3匈牙利算法例解（1）任给一个初始匹配；（2）若X已经饱和，结束；否则转（3）；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}§3匈牙利算法例解1（3）在X中找一个非饱和点x0，V1={x0}，V2=空集（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2},V2=空集N(V1)={y2,y3}§3匈牙利算法例解2（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1=V1∪{x5}={x2,x5}；V2=V2∪{y3}={y3}V1={x2},V2=空集§3匈牙利算法例解3（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5}；V2={y3}N(V1)={y2,y3,y4,y5}§3匈牙利算法例解4（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5}；V2={y3}；V1=V1∪{x3}={x2,x5,x3}；V2=V2∪{y5}={y3,y5}§3匈牙利算法例解5（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5,x3}；V2={y3,y5}；N(V1)={y2,y3,y4,y5}§3匈牙利算法例解6（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5,x3}；V2={y3,y5}；x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=ME(P)={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}§3匈牙利算法例解7（2）若X已经饱和，结束；否则转（3）；（3）在X中找一个非饱和点x0，V1={x0}，V2={}（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5V1={x4}；V2=空集M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}N(V1)={y3}§3匈牙利算法例解8（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5V1={x4}；V2=空集M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1=V1∪{x2}={x4,x2}；V2=V2∪{y3}={y3}§3匈牙利算法例解9（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,}；V2={y3}N(V1)={y2,y3}§3匈牙利算法例解10（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,}；V2={y3}V1=V1∪{x3}={x4,x2,x3}；V2=V2∪{y2}={y3,y2}§3匈牙利算法例解11（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3}；V2={y3,y2}N(V1)={y2,y3,y5}§3匈牙利算法例解12（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3}；V2={y3,y2}V1=V1∪{x5}={x4,x2,x3,x5}；V2=V2∪{y5}={y3,y2,y5}§3匈牙利算法例解13（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3,x5}；V2={y3,y2,y5}N(V1)={y2,y3,y5,y4}§3匈牙利算法例解14（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3,x5}；V2={y3,y2,y5}x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=ME(P)={(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)}§3匈牙利算法例解15（2）若X已经饱和，结束；否则转（3）；解x1x2y1x3x4x