(b)NS)={y2,y3)≠T,取y3∈N(S)-T G=(X,Y) (c)y3为M饱和点，x2y3∈M。此时，置S=SU(x2} T=TU{y3}。 (b)NS)尸{y2,y3}=T,所以，G无完美匹配. (⑤)、匈牙利算法复杂性分析
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 (c) y3为M饱和点，x2y3 ∈ M。此时，置S=S∪｛x2｝ T=T∪｛y3｝。 (b ) N(S)= ｛y2 , y3｝ ≠T，取y3 ∈N(S)-T x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 G=(X, Y) (b ) N(S)= ｛y2 , y3｝ =T，所以，G无完美匹配。 (5) 、匈牙利算法复杂性分析
1)、最多循环X次可以找到完美匹配； 2)、初始匹配最多扩张X次可以找到完美匹配； 3)、每次生长树的生长至多2区-1次。 所以，算法复杂性为OX),是好算法。 2、偶图中寻找最大匹配 问题：在一般偶图上求最大匹配M. 分析：使用匈牙利算法求完美匹配时，当在扎根于M 非饱和点u的交错树上有N(S)KS时，由Hall定理，算法 停止。要求出最大匹配，应该继续检查X-S是否为空，如 果不为空，则检查是否在其上有M非饱和点。一直到所 有M非饱和点均没有M可扩路才停止。 12
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 12 1) 、最多循环|X|次可以找到完美匹配； 2) 、初始匹配最多扩张|X|次可以找到完美匹配； 3) 、每次生长树的生长至多2|X|-1次。 所以，算法复杂性为O(|X|3 ),是好算法。 2、偶图中寻找最大匹配 问题：在一般偶图上求最大匹配M. 分析：使用匈牙利算法求完美匹配时，当在扎根于M 非饱和点u的交错树上有|N(S)|<|S|时，由Hall定理，算法 停止。要求出最大匹配，应该继续检查X-S是否为空，如 果不为空，则检查是否在其上有M非饱和点。一直到所 有M非饱和点均没有M可扩路才停止