图论课件--匈牙利算法与最优匹配算法VIP免费

10.810.60.40.20xt00.511.5210.500.51n图论及其应用应用数学学院20.810.60.40.20xt00.511.5210.500.51n本次课主要内容(一)、匈牙利算法(二)、最优匹配算法匈牙利算法与最优匹配算法30.810.60.40.20xt00.511.5210.500.51n(一)、匈牙利算法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可扩路。40.810.60.40.20xt00.511.5210.500.51n定义1设G=(X,Y),M是G的匹配，u是M非饱和点。称树H是G的扎根于点u的M交错树,如果：1)u∈V(T)；2)对任意v∈V(T),(u,v)路是M交错路。x1x2x3x4y2y1y3y4G=(X,Y)x3x2x4y4y3y2扎根x3的M交错树扎根于M非饱和点u的M交错树的生长讨论：50.810.60.40.20xt00.511.5210.500.51n假如扎根于M非饱和点u的M交错树为H,对于H,有两种情形：情形1除点u外，H中所有点为M饱和点，且在M上配对；x4ux2y4y3y2扎根u的M交错树Hx5情形2H包含除u外的M非饱和点。x4ux2y4y3y2扎根u的M交错树H60.810.60.40.20xt00.511.5210.500.51n对于情形1，令S=V(H)∩X,T=V(H)∩Y,显然：1)若N(S)=T,由于S-｛u｝中点与T中点配对，所以有：()TNS|T|=|S|-1,于是有：|N(S)|=|S|-1<|S|.由Hall定理，G中不存在完美匹配；2)若()TNS令y∈N(S)–T,且x与y邻接。因为H的所有点，除u外，均在M下配对。所以，或者x=u，或者x与H的某一顶点配对，这样，有xyM若y为M饱和的，设yz∈M,则加上顶点y及z和边xy与yz生长H，得到情形1；70.810.60.40.20xt00.511.5210.500.51n若y为M非饱和的，加上顶点y和边xy生长H，得到情形2.找到一条M可扩路，可以对匹配进行一次修改，过程的反复进行，最终判定G是否有完美匹配或者求出完美匹配。根据上面讨论，可以设计求偶图的完美匹配算法。(4)、偶图完美匹配算法——匈牙利算法。设M是初始匹配。(a)、若M饱和X所有顶点，停止。否则，设u为X中M非饱和顶点，置S=｛u｝,T=Φ;(b)、若N(S)=T,则G中不存在完美匹配。否则设y∈N(S)–T.80.810.60.40.20xt00.511.5210.500.51n(c)若y为M饱和点，且yz∈M,置S=S∪｛z｝,T=T∪｛y｝,转(b)。否则，设P为M可扩路，置M1=MΔE(P)，转(a).例1讨论下图G=(X,Y)是否有完美匹配。x1x2x3x4x5y1y2y3y4y5G=(X,Y)解：取初始匹配M=｛x1y2,x2y3｝。(a)S=｛x3｝,T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y)90.810.60.40.20xt00.511.5210.500.51n(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)x3y2x1x2x3x4x5y1y2y3y4y5G=(X,Y)100.810.60.40.20xt00.511.5210.500.51n(a)S=｛x4｝,T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y)(b)N(S)=｛y2,y3｝,N(S)≠T,取y2∈N(S)-T(c)y2为M饱和点，y2x3∈M。此时，置S=S∪｛x3｝T=T∪｛y2｝。(b)N(S)=｛y2,y3｝≠T，取y3∈N(S)-Tx4y2x3110.810.60.40.20xt00.511.5210.500.51n(c)y3为M饱和点，x2y3∈M。此时，置S=S∪｛x2｝T=T∪｛y3｝。(b)N(S)=｛y2,y3｝≠T，取y3∈N(S)-Tx1x2x3x4x5y1y2y3y4y5G=(X,Y)(b)N(S)=｛y2,y3｝=T，所以，G无完美匹配。(5)、匈牙利算法复杂性分析120.810.60.40.20xt00.511.5210.500.51n1)、最多循环|X|次可以找到完美匹配；2)、初始匹配最多扩张|X|次可以找到完美匹配；3)、每次生长树的生长至多2|X|-1次。所以，算法复杂性为O(|X|3),是好算法。2、偶图中寻找最大匹配问题：在一般偶图上求最大匹配M.分析：使用匈牙利算法求完美匹配时，当在扎根于M非饱和点u的交错树上有|N(S)|<|S|时，由Hall定理，算法停止。要求出最大匹配，应该继续检查X-S是否为空，如果不为空，则检查是否在其上有M非饱和点。一直到所有M非饱和点均没有M可扩路才停止。130.810.60.40.20xt00.511.5210.500.51n偶图中寻找最大匹配算法：设M是G=(X,Y)的初始匹配。(1)置S=Φ,T=Φ;(2)若X-S已经M饱和，停止；否则，设u是X-S中的一非饱和顶点，置S=S∪｛u｝。(3...