第八章 匹配

解 以六人a,b,c,d,e,f为顶点，在懂共同语言的人的顶点间连边得图G（如图4(a)所示），因为G中没有奇圈，所以G是二部图（如图4(b)所示），故至少应有两间房间即可。

图4

二部图是十分有用的一种数学模型，许多问题可以用它来刻划。例如“资源分配”、“工作安排”、“人员择偶”等等。但是，利用二部图分析解决这类问题时，还需要与二部图有关的另一个概念——匹配。 8.2 匹配

首先看实际中常碰见的问题：给n个工作人员安排m项任务，n个人用

V?{x1,x2,,xn}表示。并不是每个工作人员均能胜任所有的任务，一个人只能胜

任其中k(k?1)个任务，那么如何安排才能做到最大限度地使每项任务都有人做，并使尽可能多的人有工作做？

例如，现有x1,x2,x3,x4,x5五个人，y1,y2,y3,y4,y5五项工作。已知x1能胜任y1和

y2，x2能胜任y2和y3，x3能胜任y2和y5，x4能胜任y1和y3，x5能胜任y3、y4和y5。如何安排才能使每个人都有工作做，且每项工作都有人做？

显然，我们只需构造这样的数学模型：以xi和yj（i，j=1，2，3，4，5）为顶点，在xi与其胜任的工作yj之间连边，得二部图G，如图5所示，然后在G中找一个边的子集，使得每个顶点只与一条边关联（图中粗线），问题便得以解决了。

这就是所谓匹配问题，下面给出匹配的基本概念和术语。

图5匹配问题示意图

定义8.2.1 设无向图G?V,E，G中有边集M?E，且在M中任意两条边都不邻接，称边集M为图G的一个匹配(Matching)。M中一条边的两个端点，叫做在M下是配对的。如果G中不存在匹配M1，使得M1?M，则称M为最大匹配(Maximum Matching)。一般情况下最大匹配是不唯一的。

对于G的一个匹配M，若顶点v与M中的边关联，则称v是M饱和的(Saturated)，也称v是M饱和顶点，或者称M饱和顶点v，否则称v是M不饱和的。若G的每一个顶点均为M饱和顶点，则称M为G的完美匹配，显然其边数达到2。完美匹配一定是最大匹配，但反之不成立。若最大匹配的边数为p(G)/2，则说明该图存在完美匹配，且这个最大匹配就是完美匹配，否则该图不存在完美匹配。 例3 （1989，美国数学奥林匹克）某地区网球俱乐部的20名成员举行14场单打比赛中，每一名成员至少上场一次，证明：必有6场比赛，其中12个参赛者各不相同。

证明 首先构造图G：用20个顶点v1,v2,p,v20代表20名成员，两个顶点相

邻当且仅当所对应的两名选手进行过一场比赛。按给定的条件，所得图G是有14条边且每个顶点的度至少是1的简单图。则只要证明G中有一个含有6条边的匹配。根据握手定理有?d?vi?=28，今对G中每个顶点v，除去与v关联的d(v)-1

i?120条边，由于一条边可能同时被与它关联的两个端点除去，所以被除去的边最多是：

??d?v??1?=28-20=8

ii?120故除去这些边后所得到的图H至少还有14-8=6条边，且图H中每个顶点的度至多为1（因为每个点的关联集仅剩一条），从而这6条边组成G中的一个匹配。因此与这6条边关联的12个顶点是各不相同的。即这6条边所对应的6场比赛的参赛者各不相同。 两个匹配和环和：

定理8.2.1设M1和M2是图G的两个不同的匹配，由边子集M1?M2所导出的G的边导出子图记为H，则H的任意连通分支是下列情况之一：

（1）其边在M1与M2中交替出现的偶圈； （2）其边在M1与M2中交替出现的偶路。

证明 H=G[M1?M2]，明显地，H中每个顶点的度至少是1。又因为M1与M2是G的两个不同的匹配，故H中每一个顶点至多与M1中的一条边关联，同时也与M2中的一条边关联，故H中每一个顶点的度至多是2。所以H中的每个连通分支或者是一条路或者是一个偶圈。根据匹配的定义，H中任意两条相邻的边必属于M1与M2，从而H中的每一条路、偶圈中的边都是在M1与M2之间交替出现。

为了寻求二部图的最大匹配，下面介绍交替路和可扩充路两个概念。 定义8.2.2 M是图G的一个匹配，L是G中的一条路，如果L是由属于M和不属于M的边交替出现组成，则称L为G的M交错道路(Alternating Path)。如果交错道路L的始点和终点都是M不饱和点，则称L为G的M可扩充路(M—Extensible Path)。

例如，在图6(a)中，对于匹配M?{(1,6),(2,7),(3,9)}，路L1:16273，L2:27394，

L3:5394，L4:51627394都是M交替路，其中L3,L4的始点和终点都是M不饱和点，所以这两条路是M可扩充路。

图6

可扩充路具有如下性质：

如果在一条可扩充路中把属于M中的边从匹配中去掉，把不属于M中的边添入到匹配中，则得到新的匹配M1，M1的边数比M多１。例如，在图6(a)中，对于匹配M?{(1,6),(2,7),(3,9)}，L4:51627394是M可扩充路，将L4中属于M中的边

(1,6)，(2,7)，(3,9)从匹配M中去掉， 把不属于M中的边(5,1),(6,2),(7,3),(9,4)添

入到匹配M中，则得到新的匹配M1?{(5,1),(6,2),(7,3),(9,4)}，M1中的边数由M中的3条增至4条。如果图中还存在可扩充路， 再按上面的步骤做， 所得到的匹配的边数又多１，一直到图G中不存在可扩充路为止。用此方法可逐步得到较大的匹配，直至得到最大匹配。这就是下面的定理。

定理8.2.2 在图G中，M为最大匹配的充分必要条件是不存在可扩充路。

证明 先证必要性。

用反证法。假设G中存在一条M可扩充路，则可以得到比M的边数多１的匹配，与M为最大匹配矛盾。所以G中不存在M可扩充路。

再证充分性。

用反证法。假设M不是最大匹配，则存在匹配M1，使得M1?M。令，设由M2导出的G的子图G[M2]?H，于是由定理M2?M?M1（?为环和运算）

8.2.1知，H的每个连通分支或者是一个边交错地属于M与M1的长度为偶数的偶圈，或者是边交错地属于M与M1的，长度为奇数的交错路。 由于M1?M，因而H中必有一个连通分支P，它所含的属于M1的边比属于M的边多，P不是偶圈（因为偶圈的长度均为偶数，属于各自的边一样多），它的起点和终点都是M不饱和的，也一定是G中的M不饱和点，因此在G中存在关于M的可扩充路，这与假设矛盾。

这一定理不仅给出了最大匹配的判别，也给出了最大匹配的寻找。Berge在1957年证明了这样所得到的匹配就是一个最大匹配。