二部图匹配.ppt

二部图匹配及应用 一、人员安排问题-完备匹配 某公司准备安排n个职员x1,x2,…, xn从事n项工作y1,…,yn,　每个职员能胜任其中一项或几项工作 试问: 　　　能否把所有职员都安排一项他所胜任的工作?这个问题称为人员安排问题 　　　构造2部划分为{X,Y｝的简单2部图G，其中X={x1,x2,…, xn}，Y= {y1,…,yn}，并且xiyj ∈E(G)?职员xi胜任工作yj.于是问题转化为判定给定的2部图G中是否有完备匹配问题. 一、人员安排问题 －－完备匹配 定义：设Ｄ是无环非空图，Ｍ是E(D)的非空子集，若Ｍ中任何两条边在Ｄ中均不相邻，则称Ｍ为Ｄ的匹配。 例1.1 在下图中，粗边所示的边集是该图的一个匹配. D中与M中边关联的顶点称为M饱和点 如：x1,x2,y1,y2,x3,y3,x5,y5. 反之，称为非M饱和点 如：x4,y4 一、人员安排问题 －－完备匹配 设X属于V(D).若X中每点都是M饱和点，则称M饱和X. 若M饱和V(D)，则称M为D的完备匹配 若对D的任何匹配M’均有|M’|≤|M|，则称M为D的最大匹配 每个完备匹配都是最大匹配，反之不真. 一、人员安排问题 －－完备匹配 2部图G应满足什么条件才有完备匹配？ 定理1(Hall定理) 设G是2部划分为（X，Y）的2部图，则 G有饱和X的匹配? |NG(S)|≥|S| 任取X的子集S NG(S)表示EG(S)中边的顶点集，即S的邻集。 如上图(a),S={x1, x3,x4},N(S)={y2,y3} |N(S)| |S|,所以没有完备匹配。 如上图(b)，S={x1,x2} N(S)={y1,y2,y3,y4,y5} |N(S)| ≥|S| 一、人员安排问题 －－完备匹配 设M和M’是E(G)的两个不交的非空真子集.G中(M，M’)交错路是指其边在M和M‘中交错出现的路. (M, )交错路简称为M交错路，其中 =E(G)\M. 设M是G的匹配，两端点不同且都是非M饱和的M交错路称为M增广路. 一、人员安排问题 －－完备匹配 定理2 (Berge,1957) 设M是G的匹配.则M是最大匹配?G中不含M增广路. 说明：完备匹配一定是最大匹配，因此若M是完备匹配， G也不含M增广路。 下面定理可以用来判断G是否含有M增广路 定理3 设M是2部划分为(X，Y)的2部图G的匹配，x∈X是非M饱和点，Z是G中由起点为x的M交错路所能连接的顶点集，S=Z∩X，T=Z∩y，则 (a) T NG(S) (b) 下述三条等价 (a)G中不存在以x为端点的M增广路; (b)x是Z中唯一的非M饱和点; (c)T=NG(S)且|T|=|S|-1. 一、人员安排问题 －－完备匹配 匈牙利算法的基本思想: 从G的任何匹配M开始.若M饱和X，则M是G的完备匹配. 若M不能饱和X，则在X中选择一个非M饱和点x. (1) 若G中存在以x为起点的M增广路P，则由定理2知M不是最大匹配. 且M’=M’ △E(P)是比M更大的匹配，因而饱和X中更多的点. 用M’替代M 并重复上述程序. (2) 若G中不存在以x为起点的M增广路，则令Z是G中由起 点为x的M交错路所能连接的顶点集，令S=Z∩X，T=Z ∩ Y. 则由定理3知x是Z中唯一非M饱和点，且Nc(S)=T， |T|=|Nc(S)||S|. 由Hall定理(定理1)知G没有完备匹配. 一、人员安排问题 －－完备匹配 匈牙利算法 1.任取G的匹配M.若M饱和X，则停止.若M不能饱和X，则取X的非M饱和点x. 令S={x}，T=N(S)\T 2.若N(S)=T，则停止，此时G中无完备匹配. 若N(S) ≠T，则取y∈N (S)\T. 3.若y是M饱和的，则存在z ∈X\S 使yz ∈ M.用S∪ {z}替代S， T ∪{y} 替代T，并转入第2步.若y是非M饱和的，则G中存在以x为起点且以y为终点的M增广路P.然后用M’ △E(P)替代M并转入第1步. 例1 2部图Ｇ，其中Ｘ＝ {x1,x2,…, x5},Y= {y1,y2,…,y5},初始匹配Ｍ0={x2y2, x3y3, x5y5} 令S0= {x1 },T0 = , 因为N(S0)={y2,y3} T0, 所以取y2∈N(S0)\ T0 y2是M0