若y为M饱和点，可设yz∈M,则加上顶点y及z和边xy与yz 生长H,得到情形1； 扎根u的M交错树H 若y为M非饱和点，加上顶点y和边xy生长H,得到情形2 扎根u的M交错树H
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 若y为M饱和点，可设yz ∈M,则加上顶点y及z和边xy与yz 生长H，得到情形1； x u x2 y4 y3 y2 扎根 u的M交错树H x5 y z 若y为M非饱和点，加上顶点y和边xy生长H，得到情形2. x u x2 y4 y3 y2 扎根 u的M交错树H x5 y
后一情况下找到一条M可扩路，可以对匹配进行一次修改， 过程的反复进行，最终判定G是否有完美匹配或者求出完美 匹配。 根据上面讨论，可以设计求偶图的完美匹配算法。 (4)、偶图完美匹配算法一匈牙利算法。 设M是初始匹配。H是扎根于M非饱和点u的交错树。 令：S=VH∩X,T=VHD∩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-=SU{z},T-TU(y), 转(b)。否则，设P为M可扩路，置M=M△EP),转(
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 后一情况下找到一条M可扩路，可以对匹配进行一次修改， 过程的反复进行，最终判定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饱和点，且y z ∈M, 置S=S∪｛z｝, T=T∪｛y｝, 转(b)。否则，设P为M可扩路，置M1=MΔE(P)，转(a)
例1讨论下图G=(X,Y)是否有完美匹配。 G=(X,Y) 解：取初始匹配M={xY2,x23}。 (a)S={x3),T=Φ； G=(X,Y)
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 例1 讨论下图G=(X, Y)是否有完美匹配。 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 G=(X, Y) 解：取初始匹配M=｛x1y2 , x2y3｝。 (a) S=｛x3｝,T=Φ; x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 G=(X, Y)
(b)N(S)={y2,y3),N(S)≠T,取y2∈N(S)-T G=(X,Y) (c)y2为M非饱和点，加上y2和边x3y2生长树H。此时， 置M=M△EP)=（x1y1,x2y3,X3V2 G=(X,Y)
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 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｝ x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 G=(X, Y) x3 y2 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 G=(X, Y)
G=X,Y) (a)S={x4},T=Φ； (b)N(S)={y2,y3),N(S)≠T,a取y2∈N(S)-T (c)y2为M饱和点，y2X3∈M。此时，置S=SU{x3} T=TU{y2)。 (b)NS)=(y2,y3)≠T,取y3∈N(S)-T
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 (a) S=｛x4｝,T=Φ; x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 G=(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)-T x4 y2 x3