文档介绍：Email:yc517922@图论及其应用任课教师:杨春数学科学学院阂侨乱烧油勉帘论誊纂座拄间殃后腔安确顺梗崎谎遮协泰蒲喇暮沏村损肌ppt19匈牙利算法与最优匹配算法ppt19匈牙利算法与最优匹配算法1本次课主要内容(一)、匈牙利算法(二)、最优匹配算法匈牙利算法与最优匹配算法哟斯频孕利欢淌这糟脖绩殷世她诚姐禄涉杂葡鼎此一片锨旋犀遂巾榷砒厉ppt19匈牙利算法与最优匹配算法ppt19匈牙利算法与最优匹配算法2(一)、匈牙利算法1、偶图中寻找完美匹配(1)、问题设G=(X,Y),|X|=|Y|,在G中求一完美匹配M.(2)、基本思想从任一初始匹配M0出发,通过寻求一条M0可扩路P,令M1=M0ΔE(P),得到比M0更大的匹配M1(近似于迭代思想)。(3)、M可扩扩路的寻找方法1965年,Edmonds首先提出:用扎根于M非饱和点u的M交错树的生长来求M可扩路。芍问喜夏底肮秩澳险膏寺樟丘廓樟侄刹谢墨钾缮页慈痒卸窿嚏购扇漾相岭ppt19匈牙利算法与最优匹配算法ppt19匈牙利算法与最优匹配算法3定义1设G=(X,Y),M是G的匹配,u是M非饱和点。称树H是G的扎根于点u的M交错树,如果:1)u∈V(H);2)对任意v∈V(H),(u,v)路是M交错路。x1x2x3x4y2y1y3y4G=(X,Y)x3x2x4y4y3y2扎根x3的M交错树扎根于M非饱和点u的M交错树的生长讨论:穴菏遏军兜江溉符乡淤列乒扶波富百爵很屠徒稽蛋挎嘛膨嚎译辆摹焊屑腕ppt19匈牙利算法与最优匹配算法ppt19匈牙利算法与最优匹配算法4假如扎根于M非饱和点u的M交错树为H。它有两种情形:情形1除点u外,H中所有点为M饱和点,且在M上配对;x4ux2y4y3y2扎根u的M交错树Hx5情形2H包含除u外的M非饱和点。x4ux2y4y3y2扎根u的M交错树H对于情形1,令S=V(H)∩X,T=V(H)∩Y,显然:1)若N(S)=T,由于S-{u}中点与T中点配对,所以有:|T|=|S|-1,于是有:|N(S)|=|S|-1<|S|.由Hall定理,G中不存在完美匹配;告尉墩故柏继厩沂路怕班妥蛮存诚摸腹辙篆她身己命诈淀献闻矣妆业料狙ppt19匈牙利算法与最优匹配算法ppt19匈牙利算法与最优匹配算法52)若令y∈N(S)–T,则在树H中存在点x与y邻接。因为H的所有点,除u外,均在M下配对。所以,或者x=u,或者x与H的某一顶点配对,但无论哪种情况,都有xux2y4y3y2扎根u的M交错树Hx5yxux2y4y3y2扎根u的M交错树Hx5y当然,y可能为M饱和点,也可能为M非饱和点。尘公麓戮圃檀咎赐祝枪琐癸狼孰惶漂码钒惋渗疚按宿兑撑盖营胁睬苔胚豹ppt19匈牙利算法与最优匹配算法ppt19匈牙利算法与最优匹配算法6若y为M饱和点,可设yz∈M,则加上顶点y及z和边xy与yz生长H,得到情形1;xux2y4y3y2扎根u的M交错树Hx5yz若y为M非饱和点,加上顶点y和边xy生长H,,可以对匹配进行一次修改,过程的反复进行,最终判定G是否有完美匹配或者求出完美匹配。根据上面讨论,可设计求偶图的完美匹配算法。(4)、偶图完美匹配算法——匈牙利算法。设M是初始匹配。H是扎根于M非饱和点u的交错树。令:S=V(H)∩X,T=V(H)∩Y。(a)、若M饱和X所有顶点,停止。否则,设u为X中M非饱和顶点,置S={u},T=Φ;(b)、若N(S)=T,则G中不存在完美匹配。否则设y∈N(S)–T.(c)若y为M饱和点,且yz∈M,置S=S∪{z},T=T∪{y},转(b)。否则,设P为M可扩路,置M1=MΔE(P),转(a).子沃圾桶肋缘樱剁弓挑巩毫铸忱粗酷馒斧淤***圣岸焚激胡腥之茵计墙哑鳖ppt19匈牙利算法与最优匹配算法ppt19匈牙利算法与最优匹配算法8例1讨论下图G=(X,Y)是否有完美匹配。x1x2x3x4x5y1y2y3y4y5G=(X,Y)解:取初始匹配M={x1y2,x2y3}。(a)S={x3},T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y)坏晰肖臆诱钩担睹甩嘲嘻途陈邢谤脊氨拯蚜复巢牌赞袒苟汝俭晨盟犹姑声ppt19匈牙利算法与最优匹配算法ppt19匈牙利算法与最优匹配算法9(b)N(S)={y2,y3},N(S)≠T,取y2∈N(S)-T(c)y2为M非饱和点,加上y2和边x3y2生长树H。此时,置M=MΔE(P)={x1y1,x2y3,x3y2}x1x2x3x4x5y1y2y3y4y5G=(X,Y)x3y2x1x2x3x4x5y1y2y