图和网络第二讲

N(S)。

定理 1-2-6.2 设G是具有二部分划（X，Y）的二部图。G中存在饱和X中每个结点的匹配当且仅当对任何S?X,N(S)?S。

证明： 设G中存在饱和X中一切结点的匹配M。显然，仅就M而言，已有N(S)?S，因而在G中N(S)?S成立。

反之，若对任S?X,N(S)?S，则可以在G中先构造一个最大的匹配M。如果使X中的一切结点饱和，则定理已得到证明；

否则，必有x0?X不是M－饱和的。这时，如果存在一条以x0为起点，以Y中某个非M－饱和的结点y0为终点的交错道路，那么这条道路是M－可增广道路，与M是最大匹配矛盾。如果以x0为起点的一切交错道路其终点都不是Y中的非M－饱和结点，那么，这一切交错道路中不可再延长者其终点仍是X中的结点。设由上述交错路包含的X中的结点集为S，则N(S)?S?1?S，与已知件矛盾。因此M必饱和X中的一切结点。

推论 1-2-6.2.1 对任何k?0,k度正则的二部图必有完备匹配。

证明：设G是具有二部分划（X，Y）的k度正则二部图，由kX?kY知道X?Y。任取S?X，那么与S中结点相关联的边构成的集合是与N（S）中结点相关联的边构成的集合的子集合。即

kN(s)?kS

由此知N(s)?S，从而G中存在饱和X的匹配，这个匹配也饱和Y，因此就是完备匹配。

定理1-2-6.2 提供了设计求饱和X中所有结点匹配的算法基础。其基本思想是从任何一个初始匹配开始，寻找关于这个匹配的可增广道路从而扩大这个匹配，直至不能再扩大为止。这些基本思想体现在下面的匈牙利算法之中。

匈牙利算法：

设G是一个具有二部分划（X，Y）的二部图，判定并求G的饱和X中全体结点的匹配过程如下：

（1）任意确定一个初始匹配M。

（2）若M已饱和X中全部结点，则输出M，算法结束；否则，选一个非

13

M－饱和结点x?X，构造集合S??x?,T??。

（3）若N(S)?T，则不存在饱和X的匹配，算法结束；否则，选一结点

y?N(S)?T。

（4）若y是M－饱和的，且yz?M，则用S??z?代替S，用T??y?代替T，转（3），否则，则存在以x为起点，以y为终点的M－可增广道路p，用M?E(p)代替M转（2）。

例 求图1-2-6.3中二部图的一个饱和X中一切结点的匹配。可把求解过程列表如下：

顺序 1 2 3 4 5 6 当前匹配 {x1y1 , x2y5} {x1y1,x2y5,x4y3} {x1y1,x2y5,x4y3,x3y4} 结束 x x4 x3 S {x4} {x3} {x3,x1} {x3,x1,x4} ? ? {y1} T N(S) {y3 , y5} {y1 , y4} {y1,y3,y4} y z 可增广道路 p=x4y3 y3 y1 x1 y3 x4 p=x3y4 {y1,y3} {y1,y3,y4,y5} y4 这里介绍的匈牙利算法是用于判定和构造饱和二部图的一部结点的匹配。当不存在饱和这一部结点的匹配时，算法也结束，但是这时得到的匹配一般不是最大匹配。上述匈牙利算法经适当修改后可用来求二部图的最大匹配，这个问题留作练习。

在实际问题中，有时不仅要求最大匹配，还要使最大匹配满足一定的极值条件，即所谓

x4 图1-2-6.3

x2 x3 y2 y3 y4 y5

x1

y1

求最佳匹配。例如在人员工作安排时，不仅要求每个人有工作干，还进一步要求所作安排保证总的工作效益最高。这个问题就相当于要在一个带权的二部图中找一个权和最大的最大匹配。下面将介绍求带权完全二部图中最佳匹配的算法。

设G是一具二部划分（X，Y）的带权二部图，其中X??x1,?,xn?,Y??y1,?yn?边xiyj带有权w?xiyj?。再让G中每个结点v对应一个实数l(v)，称为结点v的标号。如果在X?Y上给定的标号函数l对任何x?X和y?Y满足

l(x)?l(y)?w(xy)

14

则称l是G上一个可行标号（函数）。显然，在任何带权完全二部图上，至少存在一个可行标号。

设l是G?(V,E)上的一个可行标号，构造E的一个子集，称为关于标号l的一个等性子集。

定理 1-2-6.3 设l是带权完全二部图G上一个可行标号，El是G关于标号l的等性子集。若边诱导子图G(El)包含了G的一个完备匹配M*，则M*就是G的一个最佳匹配。

证明： 因为G(El)包含了G的一个完备匹配M*，则M*是等性子集El的一个子集，从而M*的权是

W(M*)?xy?M*?w(xy)??l(v)。

v?V另设M是G中任何一完备匹配，则

W(M*)?xy?M*?w(xy)??l(x)?l(y)??l(v)?W(M*)，

v?vv?v即M*是G的一个最佳匹配。

定理1-2-6.3暗示可以构造一个好的算法：把求G的最佳匹配转化成利用标号法求生成子图G(El)的完备匹配。因此，算法的主要部份仍是匈牙利算法。其基本思想是由任一可行标号l构造等性子集El，当能由El确定出G的一个完备的匹配M*时，则M*就是最佳匹配；当不能由El确定G的一个完备匹配时，则修改标号，重复上述过程直至求出M*。下面介绍求带权完全二部图G的最佳匹配的算法。设G的二部分划为（X，Y），边xy的权为w(xy)。

求最佳匹配的标号法：

（1）给定初始可行标号l：对所有x?X，令l(x)?max(w(xy))；对所有y?Y，

y?Y令l(y)?0。

（2）找出等性子集El，并求G(El)的个匹配M。

（3）若M已饱和X部结点，则M是最佳匹配，算法结束；否则，选一个非M－饱和结点x?X，构造集合S??x?,T??。

（4）若在G(El)中，N(S)?T，转（5）；否则，计算

15

??xi?S,yj?Y?Tmin?l(x)?l(yij)?w(xiyj)?，

然后修改标号l为

?l(v)??,当v?S?l?(v)??l(v)??,当v?T

?l(v),其它，???求出等性子集El。用l?代替l，用El代替El。

（5）对于G(El)，在N（S）-T中选一结点y。若y是M-饱和的且yz?M，则以S??z?代替S，以T??y?代替T后转（4）；若y不是M－饱和的，则存在从x到y的M－可增广道路p，以M??M?E(p)代替M转（3）。

例 已知利用5种不同产品作5种不同用途的效益矩阵为

x1?3x2?2?C?x3?4?x4?8x5??7y16014?3552??0615??，

2364?4256??y2y3y4y5求最佳匹配使总的效益最高。

用x1,x2,x3,x4,x5表示5种产品，y1,y2,y3,y4,y5表示5种用途，可得一个完全二部图K5,5。利用标号法求最佳匹配的步骤如下：

（1）给予初始标号：l(x1)?6,l(x2)?5,l(x3)?6,l(x4)?8,l(x5)?7,l(y1)?l(y2)

?l(y3)?l(y4)?l(y5)?0。

（2）在给定的标号下求得的等性子集El??x1y2,x2y3,x2y4,x3y3,x4y1,x5y1?。构造G(El)，如图1-2-6.4所示。

（3）在G(El)中求得最大匹配M??x1y2,x2y4,x3y3,x4y1?。

（4）x5未饱和，S??x5?,T??,N(S)??y1?；选y1，因为x4y1?M，重新构造S??x4,x5?,T??y1?，这时N(S)?T，必须修改原标号。

（5）求得??l(x1)?6,l(x2)?5,i?4,5;2?j?5min?l(x)?l(yij)?w(xiyj)??1，新的标号是

l(x3)?6,l(x4)?7,l(x5)?6,l(y1)?1,l(y2)?l(y3)?l(y4)?l(y5)?0。

16