资源描述：
《图论课件--匈牙利算法与最优匹配算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论及其应用应用数学学院1本次课主要内容(一)、匈牙利算法(二)、最优匹配算法匈牙利算法与最优匹配算法2(一)、匈牙利算法1、偶图中寻找完美匹配(1)、问题设G=(X,Y),
2、X
3、=
4、Y
5、,在G中求一完美匹配M.(2)、基本思想从任一初始匹配M0出发，通过寻求一条M0可扩路P，令M1=M0ΔE(P),得比M0更大的匹配M1(近似于迭代思想)。(3)、M可扩扩路的寻找方法1965年，Edmonds首先提出:用扎根于M非饱和点u的M交错树的生长来求M可扩路。3定义1设G=(X,Y),M是G的匹配，u是M非饱和点。称树H是G的扎根于点u的M交错树,如果：1)u∈V(T)；2)对任意v∈V(T),(
6、u,v)路是M交错路。x1x2x3x4y2y1y3y4G=(X,Y)x3x2x4y4y3y2扎根x3的M交错树扎根于M非饱和点u的M交错树的生长讨论：4假如扎根于M非饱和点u的M交错树为H,对于H,有两种情形：情形1除点u外，H中所有点为M饱和点，且在M上配对；x4ux2y4y3y2扎根u的M交错树Hx5情形2H包含除u外的M非饱和点。x4ux2y4y3y2扎根u的M交错树H5对于情形1，令S=V(H)∩X,T=V(H)∩Y,显然：1)若N(S)=T,由于S-｛u｝中点与T中点配对，所以有：
7、T
8、=
9、S
10、-1,于是有：
11、N(S)
12、=
13、S
14、-1<
15、S
16、.由Hall定理，G中不存在完美匹配；2)
17、若令y∈N(S)–T,且x与y邻接。因为H的所有点，除u外，均在M下配对。所以，或者x=u，或者x与H的某一顶点配对，这样，有若y为M饱和的，设yz∈M,则加上顶点y及z和边xy与yz生长H，得到情形1；6若y为M非饱和的，加上顶点y和边xy生长H，得到情形2.找到一条M可扩路，可以对匹配进行一次修改，过程的反复进行，最终判定G是否有完美匹配或者求出完美匹配。根据上面讨论，可以设计求偶图的完美匹配算法。(4)、偶图完美匹配算法——匈牙利算法。设M是初始匹配。(a)、若M饱和X所有顶点，停止。否则，设u为X中M非饱和顶点，置S=｛u｝,T=Φ;(b)、若N(S)=T,则G中不存在完美匹配。否则
18、设y∈N(S)–T.7(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)8(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=
19、(X,Y)x3y2x1x2x3x4x5y1y2y3y4y5G=(X,Y)9(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)-Tx4y2x310(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，所
20、以，G无完美匹配。(5)、匈牙利算法复杂性分析111)、最多循环
21、X
22、次可以找到完美匹配；2)、初始匹配最多扩张
23、X
24、次可以找到完美匹配；3)、每次生长树的生长至多2
25、X
26、-1次。所以，算法复杂性为O(
27、X
28、3),是好算法。2、偶图中寻找最大匹配问题：在一般偶图上求最大匹配M.分析：使用匈牙利算法求完美匹配时，当在扎根于M非饱和点u的交错树上有
29、N(S)
30、<
31、S
32、时，由Hall定理，算法停止。要求出最大匹配，应该继续检查X-S是否为空，如果不为空，则检查是否在其上有M非饱和点。一直到所有M非饱和点均没有M可扩路才停止。12偶图中寻找最大匹配算法：设M是G=(X,Y)的初始匹配。(1)置S=Φ
33、,T=Φ;(2)若X-S已经M饱和，停止；否则，设u是X-S中的一非饱和顶点，置S=S∪｛u｝。(3)若N(S)=T,转(5)；否则，设y∈N(S)-T。(4)若y是M饱和的，设yz∈M,置S=S∪｛z｝,T=T∪｛y｝,转(3);否则，存在(u,y)交错路是M可扩路P,置M=MΔE(P),转(1).(5)若X-S=Φ,停止；否则转(2).13(二)、最优匹配算法1、问题设G=(X,Y)是边赋权完全偶图，且X
