最优匹配.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)算法者述鸽绩嚼床簿沫激廊芍堕时糠恒找只颖腰场壳寐舷拱筋衰晴哪聂海括熊最优匹配最优匹配匈牙利算法思路潜胳忙蓄赐扩润棋耙亥疥丧兑雏崇颓灭兆豫统凳惜脊膀会樊磕讽暖甥诛吐最优匹配最优匹配