离散数学高等里离散数学-课件-CHAP9.ppt

* 求一个二分图的完美匹配 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 现在匹配变成了： M={x1y2, x2y1, x3y3, x5y5}。 ⑴X中有非M–饱和点x4，令S={x4}，T= ?； ⑵ NG(S)={y2, y3} ≠T, 取y2∈NG(S)–T ； ⑶y2是M–饱和点, x1y2∈M, S为{x4, x1}, T为{y2}。 ⑵ NG(S)={y2, y3}≠T, 取y3∈NG(S)–T ； ⑶y3是M–饱和点, x3y3∈M, S为{x4, x1, x3}, T为{y2, y3}。 ⑵ NG(S)={y2, y3, y4}≠T, 取y4∈NG(S)–T ； ⑶y4是非M–饱和点, x4y2x1y3x3y4为M–可增广路P； * 求一个二分图的完美匹配 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 于是M为M ?E(P)，也就是， M={x2y1, x5y5 , x4y2, x1y3, x3y4} 。 ⑴X没有非M–饱和点，算法终止。M即为所求。 一个图的完美匹配可能不唯一，例如右边是本问题的另一种完美匹配。 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 * 匈牙利算法的数据结构 W[X, Y]表示人员与工作的关系。W[i, *]为xi所胜任的所有工作， W[*, j]为所有胜任yj的人员。 X[n]和Y[n]表示匹配，X[i]为xi所分配的工作，Y[i]为承担yi的人员。 S[n]和T[n]表示算法中的S和T，N[n]表示NG(S)。 P[n, 2]表示M–交错路, P[i, 1]?S, P[i, 2]?T, 显然，P[i, 1]P[i, 2]?M，P[i, 2]P[i+1, 1]?M。 xk yj xu … … i i+1 * 实现匈牙利算法的难点 匈牙利算法是建立一个含未饱和点x的S。取S的邻接点。如果是一个饱和点则扩大S；否则就存在一条M-可增广路P。 但是匈牙利算法中并没有直接给出这条M-可增广路P。 因此在实现匈牙利算法的程序中要同时建立这条M–可增广路P。这是实现匈牙利算法的较为困难之处。 * 匈牙利算法的程序实现 Hungary(input W, output X); begin InitialMatch( ); q:=true; //建立初始匹配 while q do begin //循环修改初始匹配 u:=Check(X); //取出一个非饱和点u if un then q:=false //若X全部饱和则终止 else begin //u为起点寻找交错路 p:=Mixed-Route(u); //有交错路时p为真 if p then NewMatch( ) //有交错路就更新匹配 else q:= false; end //无完美匹配而终止 end //注：程序中只给出终end //止处而省略了其输出 * 初始匹配 InitialMatch( ); //产生初始匹配 begin for i=1 to n do X[i]:=Y[i]:=0； //将X和Y置零 for i=1 to n do begin q := true; j:=1； while q and j=n do //Y[j]=0表示yj尚未匹配 if W[i, j]=1 and Y[j]=0 then begin X[i]:=j; Y[j]:=i; q:=false end else j:=j+1 //依据W取出若干不相邻接的边 end end * 更新匹配 用M–可增广路更新匹配的子过程： RenewMatch( ); // begin for j:=1 to last do begin X[P[j, 1]]:= P[j, 2]; //修改xi的匹配