最优匹配课件

（或対集Matching)定义3

若匹配M的某条边与点v关联,则称M饱和点v,并且称v是M的饱和点,否则称v是M的非饱和点.定义4

设M是图G的一个匹配,如果G的每一个点都是M的饱和点,则称M是完美匹配；如果G中没有另外的匹配M0,使

|M0|＞|M|,则称M是最大匹配.每个完美匹配都是最大匹配,反之不一定成立.例16：判断下图的匹配最大匹配非完美匹配完美匹配定义5

设M是图G的的一个匹配,其边在E\M和M

中交错出现的路,称为G的一条M–交错路.起点和终点都不是M的饱和点的M–交错路,称为M–增广路.Berge定理：

G的一个匹配M是最大匹配的充要条件是G不包含M–增广路.定义

设V=X∪Y且X∩Y=,E{xy|x∈X,y∈Y},称G=(X,Y,E)为二部图或偶图.

二部图可认为是有限简单无向图.

如果X中的每个点都与Y中的每个点邻接,则称G=(X,Y,E)为完全二部图.

若F：E→R+,则称G=(X,Y,E,F)为二部赋权图.

二部赋权图的权矩阵一般记作A=(aij

)|X|×|Y|

,其中aij

=F(xiyj

).注意：此赋权矩阵与图的邻接矩阵不同！X:x1x2x3Y:y1y26348邻接矩阵二部图赋权矩阵邻接矩阵二部图赋权矩阵Hall定理

设G=(X,Y,E)为二部图,则①G存在饱和X的每个点的匹配的充要条件是对任意S

,有|N(S)|≥|S|.其中,N(S)={v|u∈S,v与u相邻}.②G存在完美匹配的充要条件是对任意S或S有

|N(S)|≥|S|.二部图的匹配及其应用工作安排问题之一给n个工作人员x1,x2,…,xn安排n项工作y1,y2,…,yn.n个工作人员中每个人能胜任一项或几项工作,但并不是所有工作人员都能从事任何一项工作.比如x1能做y1,y2工作,x2能做y2,y3,y4工作等.

这样便提出一个问题,对所有的工作人员能不能都分配一件他所能胜任的工作？

二部图的匹配及其应用我们构造一个二部图G=(X,Y,E),这里X={x1,x2,…,xn},Y={y1,y2,…,yn},并且当且仅当工作人员xi胜任工作yj时,xi与yj才相邻.

于是,问题转化为求二部图的一个完美匹配.因为

|X|=|Y|,所以完美匹配即为最大匹配.二部图的匹配及其应用问题：如何求出二部图的一个完美匹配？1965年匈牙利人Edmonds基于Hall定理提出一个算法，一般称为匈牙利（Hungarian）算法

匈牙利算法思路求二部图G=(X,Y,E)的最大匹配算法(匈牙利算法）迭代步骤:从G的任意匹配M开始.①若X中的顶点皆是M饱和点，停止，M即完美匹配；否则将X中M的所有非饱和点都给以标号0和标记*,,转向②.②若X中所有有标号的点都已去掉了标记*,则M是G的最大匹配，无完美匹配.否则任取X中一个既有标号又有标记*的点xi,去掉xi的标记*,转向③.③找出在G中所有与xi邻接的点yj

,若所有这样的yj都已有标号,则转向②,否则转向④.④对与xi邻接且尚未给标号的yj都给定标号i.若所有的

yj

都是M的饱和点,则转向⑤,否则逆向返回.即由其中M的任一个非饱和点

yj

的标号i找到xi,再由

xi的标号k找到

yk

,…,最后由

yt

的标号s找到标号为0的xs时结束,获得M-增广路xs

yt…xiyj

,记E(P)={xs

yt

,…,xiyj

},重新记M为M⊕E(P),将所有标记标号清空，转向①.

M⊕E(P)=(M∪E(P))\(

M∩E(P)),是对称差.

⑤

将yj在M中与之邻接的点xk

,给以标号j和标记*,转向②.注释上述匈牙利算法步骤中，标记*的作用在于标记X中的M非饱和点（可以能是临时的）标记（0，1、2、。。）的作用是找M-增广路的过程的标记，从它也能确定是否通过此顶点找过增广路。M-增广路总是以X中的M-非饱和点为起始，Y中的M-非饱和点结束的，所以找到了Y中的M-非饱和点才能找到M增广路例17：求下图最大匹配Hungarian算法：二部图的匹配及其应用注意到S={x1,x3,x4}时，N(S)={y1,y3,}由Hall定理，G没有完美匹配。例18：求下图的最大匹配。匈亚利算法：解①取初始匹配M={x2

y2,x3

y3,x5

y5}②给X中M的两个非饱和点x1,x4都给以标号0和标记*(如下图所示).00**二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：00③

去掉x1的标记*,将与x1邻接的两个点y2,y3都给以标号1.

因为y2,y3都是M的两个饱和点,所以将它们在M中邻接的两个点x2,x3都给以相应的标号和标记*.**11*23*二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：00*11*23*④

去掉x2的标记*,将与x2邻接且尚未给标号的三个点y1,y4,y5都给以标号2.

222二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：00*1123*222⑤

因为y1是M的非饱和点,逆向返回,直到x1为0为止.于是得到M的增广路x1y2x2y1,记P={x1y2,y2x2,x2y1}.取M

←

M⊕P={x1y2,x2y1,x3

y3,x5

y5},则新M是比原M多一边的匹配.二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：0*⑥清空所有标记和标号。再给X中M的非饱和点x4给以标号0和标记*,然后去掉x4的标记*,将与x4邻接的两个点y2,y3都给以标号4.44二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：044因为y2,y3都是M1的两个饱和点,所以将它们在M1中邻接的两个点x1,x3都给以相应的标号和标记*.**23二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：044**23⑦

去掉x1的标记*,因为与x1邻接的两个点y2,y3都有标号4,所以去掉x3的标记*.而与x3邻接的两个点y2,y3也都有标号4,此时X中所有有标号的点都已去掉了标记*(如上图所示),因此M是G的最大匹配.没有完美匹配。二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：注意到S={x1,x3,x4}时，N(S)={y1,y3,}所以没有完美匹配。二部图的匹配及其应用定义6

设G=(X,Y,E,W)为完备的二部赋权图,若L：X∪Y→R+满足：对任意x∈X,y∈Y,L(x)+L(y)≥W(xy),则称L为G的一个可行点标记,记相应的生成子图为GL=(X,Y,EL

,W),这里EL

={xy∈E|L(x)+L(y)=W(xy)}.定理3

设L是完备的二部赋权图G=(X,Y,E,F)的可行点标记,若M*是GL的完美匹配,则M*是G的权数最大的匹配。称为最佳（或最优）匹配.工作安排问题之二给n个工作人员x1,x2,…,xn安排n项工作y1,y2,…,yn.如果每个工作人员工作效率不同,要求工作分配的同时考虑总效率最高.二部图的匹配及其应用我们构造一个二部赋权图G=(X,Y,E,F),这里X={x1,x2,…,xn},Y={y1,y2,…,yn},F(xi

yj

)为工作人员xi胜任工作yj时的工作效率.

则问题转化为：求二部赋权图G的最佳匹配.

在求G

的最佳匹配时,总可以假设G为完备二部赋权图.若xi与yj不相邻,可令F(xi

yj

)=0.同样地,还可虚设点x或y,使|X|=|Y|.如此就将G

转化为完备二部赋权图,而且不会影响结果.二部图的匹配及其应用求完备二部赋权图G=(X,Y,E,F)的最佳匹配算法迭代步骤：

设G=(X,Y,E,F)为完备的二部赋权图,L是其一个初始可行点标记,通常取

L(x)=max{F(xy)|y∈Y},x∈X,

L(y)=0,y∈Y.可行顶点标号法(Kuhn-Munkres算法)：二部图的最佳匹配算法：算法基本思想：通过顶点标记将赋权图转化为非赋权图，再用匈牙利算法求最大匹配M是GL的一个匹配.

①若X的每个点都是饱和的,则M是最佳匹配.否则取M的非饱和点u∈X,令S={u},T=,转向②.

②记NL(S)={v|u∈S,uv∈GL}.若NL(S)=T,则GL没有完美匹配,转向③.否则转向④.

③调整标记,计算aL=min{L(x)+L(y)-

F(xy)|x∈S,y∈Y\T}.由此得新的可行点标记

令L=H,GL

=GH

,重新给出GL的一个匹配M,转向①.④