最优匹配.ppt

(或対集Matching)剐破胡筏秀苑皮客驯齐兹盂惹暂赵鸳豺普哩让新奖姐庆拢勘辈殃腮像闭垂最优匹配最优匹配定义3若匹配M的某条边与点v关联,则称M饱和点v,并且称v是M的饱和点,,如果G的每一个点都是M的饱和点,则称M是完美匹配;如果G中没有另外的匹配M0,使|M0|>|M|,,:判断下图的匹配最大匹配非完美匹配完美匹配忆骏借窥献砸挡曙矗涯颓鹰掷坛高淌蛾治雄酋魔惦恢咱暑企泰程牙除膊太最优匹配最优匹配定义5设M是图G的的一个匹配,其边在E\M和M中交错出现的路,称为G的一条M––交错路,称为M–:G的一个匹配M是最大匹配的充要条件是G不包含M–=X∪Y且X∩Y=,E{xy|x∈X,y∈Y},称G=(X,Y,E),则称G=(X,Y,E):E→R+,则称G=(X,Y,E,F)=(aij)|X|×|Y|,其中aij=F(xiyj).吃挤氟敷师洽励逊谨灶瘪剩磅宾愉蘸凑肃爹欺培钾烃蕊率举犬讯雍够院苞最优匹配最优匹配注意:此赋权矩阵与图的邻接矩阵不同!X:x1x2x3Y:y1y26348邻接矩阵二部图赋权矩阵邻接矩阵二部图赋权矩阵蠢则拱撑炯宦浓肌淮率搅牲烫序毯坦拭门崇燃烬估淹遂侄邹兄情所佃镜霜最优匹配最优匹配Hall定理设G=(X,Y,E)为二部图,则①G存在饱和X的每个点的匹配的充要条件是对任意S ,有|N(S)|≥|S|.其中,N(S)={v|u∈S,v与u相邻}.②G存在完美匹配的充要条件是对任意S或S有|N(S)|≥|S|.二部图的匹配及其应用果昌凭鹿巷鹅侦捎怖戒艺歇坏复纯矣帕啃多邢龄葡保入阵羊链俞尔死垂锻最优匹配最优匹配工作安排问题之一给n个工作人员x1,x2,…,xn安排n项工作y1,y2,…,,,y2工作,x2能做y2,y3,,对所有的工作人员能不能都分配一件他所能胜任的工作?二部图的匹配及其应用舟贺拉九娘划准埠壬憾谩蠢落酱滋勘篇娜危款乃劫早损匀锑镑做镍滇习溃最优匹配最优匹配我们构造一个二部图G=(X,Y,E),这里X={x1,x2,…,xn},Y={y1,y2,…,yn},并且当且仅当工作人员xi胜任工作yj时,,|X|=|Y|,:如何求出二部图的一个完美匹配?1965年匈牙利人Edmonds基于Hall定理提出一个算法,一般称为匈牙利(Hungarian)算法莲契陷淖鄙亭市楞毕徽武遁凑宇逾绷本淀峨补援芍幅饥娜始茵哄狰隙歪寺最优匹配最优匹配匈牙利算法思路皮吮泅杂前趁淳蹈稀油海联毋坍瑞宅棘戊涎抚继齿露拭恤琢即言亲吏烽早最优匹配最优匹配