[工学]图论 的配对问题.ppt

第五章 匹配 §1 最大匹配－1 具体问题描述： 有n个女士和n个男士参加舞会，每位女士与其中若干位男士相识，每位男士与其中若干位女士相识，问如何安排，使得尽量多配对的男女舞伴相识。 §1 最大匹配－1 下图就是一种分配方法： 匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓“人员分配问题”和“最优分配问题”中有重要作用。 假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生配对？ 类似的工作分配问题：现有n个人，m份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？ §1 最大匹配－定义 定义：若图G=(V,E)的顶点可以分成X，Y两个子集，每个子集里的顶点互不相邻，这样的图称为二分图。 §1 最大匹配－定义1 定义：若M是图G=(V,E)的边子集，且M中的任意两条边在G中不相邻，则称M为G中的一个匹配，M中的每条边的两个端点称为是M-饱和的的。 §1 最大匹配－定义2 定义：若图G中每个顶点均被M许配时，称M为G中的一个完美匹配。 §1 最大匹配－定义3 定义：图G中边数最多的匹配M，称为G中的一个最大匹配。 §1 最大匹配－定义4 定义：若匹配M的某边和顶点v关联，称v是M-饱和的，否则就是M-不饱和的。 §1 最大匹配－定义5 定义：若M是图G的一个匹配，若从G中一个顶点到另一个顶点存在一条道路，此路径由属于M和不属于M的边交替出现组成的，则称此路径为M-交错路。 §1 最大匹配－定义6 定义：若交错路的两个端点为关于M的不饱和顶点时，称此交互道为可增广道路。 §1 最大匹配－定义8 §1 最大匹配－ Berge定理 定理7.1(Berge 1957)：M为最大匹配的充要条件是：图G中不存在可增广道路。 [引理]　设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’， §2 Hall定理 设有m个人，n项工作，每个人会做其中的若干项工作，能不能适当安排，使得每个人都有工作做？ §2 Hall定理 当mn时，肯定是不可能的，即使是m≤n也不一定。但如果每个人能做的工作越多，越容易实现。 §2 Hall定理－1 Hall定理(1935)： 二分图G存在一匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X任一子集A，及与A邻接的点集为N(A)，恒有：|N(A)|≥|A|。 §3 人员分派问题 1965年，匈牙利著名数学家Edmonds设计了一种求最大匹配的算法，称为匈牙利(Hungarian)算法。 §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 匈牙利算法例 用匈牙利算法求下图的最大匹配： §3 匈牙利算法例解 （1）任给一个初始匹配； （2）若X已经饱和，结束；否则转（3）； §3 匈牙利算法例解1 （3）在X中找一个非饱和点x0，V1={x0}，V2=空集 （4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2 §3 匈牙利算法例解2 （5）若y已饱和， M中必有(y,z) ；作【 V1 =V1 ∪{z} ， V2 =V2∪ {y}； 转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】 §3 匈牙利算法例解3 （4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2； §3 匈牙利算法例解4 （5）若y已饱和， M中必有(y,z) ；作【 V1 =V1 ∪{z} ， V2 =V2∪ {y}； 转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】 §3 匈牙利算法例解5 （4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2； §