《图论及其应用》课程教学课件（PPT讲稿）第五章 匹配与因子分解 5-3 匈牙利算法与最优匹配算法

本次课主要内容 匈牙利算法与最优匹配算法 (一)、匈牙利算法 (二)、最优匹配算法

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 1 本次课主要内容 (一)、匈牙利算法 (二)、最优匹配算法 匈牙利算法与最优匹配算法

(一)、匈牙利算法 1、偶图中寻找完美匹配 (1)、问题 设G=(X,Y),X=Y,在G中求一完美匹配M. (2)、基本思想 从任一初始匹配M,出发，通过寻求一条M,可扩路P,令 M=M△EP),得到比M更大的匹配M1(近似于迭代思想)。 (3)、M可扩扩路的寻找方法 1965年，Edmonds首先提出：用扎根于M非饱和点u的M 交错树的生长来求M可扩路

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 2 (一)、匈牙利算法 1、偶图中寻找完美匹配 (1) 、问题 设G=(X, Y), |X|=|Y|, 在G中求一完美匹配M. (2) 、基本思想 从任一初始匹配M0出发，通过寻求一条M0可扩路P，令 M1=M0ΔE(P), 得到比M0更大的匹配M1 (近似于迭代思想)。 (3) 、M可扩扩路的寻找方法 1965年，Edmonds首先提出: 用扎根于M非饱和点u的M 交错树的生长来求M可扩路

定义1设G=(X,Y,M是G的匹配，u是M非饱和点。称 树H是G的扎根于点u的M交错树，如果： 1)u∈V山；2)对任意v∈V山，(m,v)路是M交错路。 G=(X,Y) 扎根x3的M交错树 扎根于M非饱和点u的M交错树的生长讨论：

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 3 定义1 设G=(X, Y), M是G的匹配，u是M非饱和点。称 树H是G的扎根于点u的M交错树,如果： 1) u ∈V(H)； 2) 对任意v ∈V(H), (u, v)路是M交错路。 x1 x2 x3 x4 y1 y2 y3 y4 G=(X, Y) x3 x x2 4 y4 y3 y2 扎根 x3 的M交错树 扎根于M非饱和点u的M交错树的生长讨论：

假如扎根于M非饱和点u的M交错树为H。它有两种情形： 情形1除点ù外，H中所有点为M饱和点，且在M上配对； 扎根u的M交错树H 扎根u的M交错树H 情形2H包含除u外的M非饱和点。 对于情形1，令S=VH∩X,T=VH∩Y,显然： TN(S) 1)若N(S)=T,由于S-{u}中点与T中点配对，所以有： T=S-1,于是有：NS=S-1<Sl.由Hall定理，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 4 假如扎根于M非饱和点u的M交错树为H。它有两种情形： 情形1 除点u外，H中所有点为M饱和点，且在M上配对； x4 u x2 y4 y3 y2 扎根 u的M交错树H x5 情形2 H包含除u外的M非饱和点。 x4 u x2 y4 y3 y2 扎根 u的M交错树H 对于情形1，令S=V(H)∩X, T=V(H)∩Y,显然： T N S  ( ) 1) 若N(S)=T, 由于S - ｛u｝中点与T中点配对，所以有： |T|=|S|-1, 于是有： |N(S)| = |S|-1< |S|.由Hall定理，G中不存 在完美匹配；

2)若 TCN(S) 令y∈N(S)-T,则在树H中存在点x与y邻接。因为H的所有 点，除u外，均在M下配对。所以，或者x=u,或者x与H的某 一顶点配对，但无论哪种情况，都有y廷M 扎根u的M交错树H 扎根u的M交错树H 当然，y可能为M饱和点，也可能为M非饱和点

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 5 2) 若 T N S  ( ) 令y ∈N(S) – T, 则在树H中存在点x与y邻接。因为H的所有 点，除u外，均在M下配对。所以，或者x=u，或者x与H的某 一顶点配对，但无论哪种情况，都有 xy M x u x2 y4 y3 y2 扎根 u的M交错树H x5 y x u x2 y4 y3 y2 扎根 u的M交错树H x5 y 当然，y可能为M饱和点，也可能为M非饱和点

若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