若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 7 若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=VHnx,T=VHnY。 (a)、若M饱和X所有顶点，停止。否则，设u为X中M 非饱和顶点，置S=(u},T=Φ； b)、若NS)=T,则G中不存在完美匹配。否则设y∈NS)-T (c)若y为M饱和点，且yz∈M,置S=SU{z},T=TU{y), 转(b)。否则，设P为M可扩路，置M=M△EP),转(a
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 后一情况下找到一条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)是否有完美匹配。 以入 y3 ys G=(X,Y) 解：取初始匹配M=(x1Y2,x2W}。 (a)S={x3),T=Φ； y2 y3 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 例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)NS)F{y2,y3},NS)≠T,取y2∈N(S)-T G=(X,Y) (c)y为M非饱和点，加上y,和边x3y,生长树H。此时 置M=M△EP)={xy1,x2y3,x3y2} y4 G=(,Y) 10
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 (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={x},T=Φ； (b)NS)={y2,y3},NS≠T,取y2∈N(S)-T (c)y2为M饱和点，y2X3∈M。此时，置S-SU{x3 T=TU{y2}。 (b)NS)={y2y3}≠T,取y3∈N(S)-T 11
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 11 (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