*7.5 二部图及匹配
7.5.1二部图
在许多实际问题中常用到二部图，本节先介绍二部图的基本概念和主要结论，然后介绍它的一个重要应用—匹配。
定义7.5.1 若无向图G?V,E的顶点集V能分成两个子集V1和V2，满足 （1）V?V1?V2，V1?V2??；
（2）?e?(u,v)?E，均有u?V1，v?V2。?
则称G为二部图或偶图(Bipartite Graph或Bigraph)，V1和V2称为互补顶点子集，常记为
G?V1,V2,E。如果V1中每个顶点都与V2中所有顶点邻接，则称G为完全二部图或完全偶图
(Complete Bipartite Graph)，并记为Kr,s，其中r?V1,s?V2。
由定义可知，二部图是无自回路的图。 图7-55中，(a),b是完全二部图(),c()d,()e都,(是二部图，其中(b),(c),d()e,(K1,3,K2,3,K2,4,K3,3。
图7-55二部图示例
显然，在完全二部图中Kr,s中，顶点数n?r?s，边数m?rs。
一个无向图如果能画成上面的样式，很容易判定它是二部图。有些图虽然表面上不是上面的样式，但经过改画就能成为上面的样式，仍可判定它是一个二部图，如图7-56中(a)可改画成图(b)，图(c)可改画成图(d)。可以看出，它们仍是二部图。
图7-56二部图示例
定理7.5.1 无向图G?V,E为二部图的充分必要条件为G中所有回路的长度均为偶数。
331
证明 先证必要性。
设G是具有互补节点子集V1和V2的二部图。(v1,v2,?,vk,v1)是G中任一长度为k的回路，不妨设v1?V1，则v2m?1?V1，v2m?V2，所以k必为偶数，不然，不存在边(vk,v1)。
再证充分性。
设G是连通图，否则对G的每个连通分支进行证明。设G?V,E只含有长度为偶数的回路，定义互补节点子集V1和V2如下：任取一个顶点v0?V，令
V1?{v(v?V)?d(v0,v)为偶数} V2?V?V1
现在证明V1中任意两节点间无边存在。
假若存在一条边(vi,vj)?E，且vi,vj?V1，则由v0到vi间的最短路（长度为偶数）， 边
(vi,vj)和vj到v0间的最短路（长度为偶数）所组成的回路的长度为奇数，与假设矛盾。
同理可证V2中任意两节点间无边存在。
故G中的每条边必具有形式(vi,vj)，其中vi?V1，vj?V2， 即G是具有互补节点子集V1和V2的一个二部图。
利用定理7.5.1可以很快地判断出图7-57中的(a)、(c)是二部图，而(b)则不是二部图。
图7-57
例7.5.1 六名间谍a,b,c,d,e,f被擒，已知a懂汉语、法语和日语，b懂德语、俄语和日语，c懂英语和法语，d懂西班牙语，e懂英语和德语，f懂俄语和西班牙语，问至少用几个房间监禁他们，能使在一个房间里的人不能直接对话。
解 以六人a,b,c,d,e,f为顶点，在懂共同语言的人的顶点间连边得图G（如图7-58(a)所示），因为G中没有奇圈，所以G是二部图（如图7-58(b)所示），故至少应有两间房间即可。
图7-58
7.5.2 匹配
二部图的主要应用是匹配，“匹配”是图论中的一个重要内容，它在所谓“人员分配问题”和“最优分配问题”等运筹学中的问题上有重要的应用。
332
首先看实际中常碰见的问题：给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，如图7-59所示，然后在G中找一个边的子集，使得每个顶点只与一条边关联（图中粗线），问题便得以解决了。这就是所谓匹配问题，下面给出匹配的基本概念和术语。
图7-59匹配问题示意图
定义7.5.2 设无向图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不饱和的。
定义7.5.3 设二部图G?V1,V2,E，M是G的一个匹配。若?v?V1，v均是M饱和的，则称M是V1对V2的完全匹配（简称V1―完全匹配）；若?v?V2，v均是M饱和的，则称M是。若M既是V1―完全匹配，又是V2―完全匹配（即V2对V1的完全匹配（简称V2—完全匹配）图G的每个顶点都是饱和的），则称M是完全匹配(Complete Matching)。
显然，完全匹配是最大匹配，但反之不然。
例7.5.2（1）在图7-59中，边集M?{(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)}是一个匹配，而且是是一个最大和完全匹配。
（2）在图7-60(a)中，边集M1?{(1,5),(2,7),(3,9),(4,8)}和M2?{(1,6),(2,7),(3,9)，
(4,8)}都是图G的最大匹配，也是V1―完全匹配，但不是完全匹配。在图7-60(b)中，边集M?{(1,4),(2,5),(3,6)}是完全匹配。
333
图7-60
为了寻求二部图的最大匹配，下面交替路和可扩路两个概念。
定义7.5.4 设G?V1,V2,E是一个二部图，M是图G的一个匹配，L是G中的一条路，如果L是由属于M和不属于M的边交替出现组成，则称L为G的M交替路(Alternating Path)。如果交替路L的始点和终点都是M不饱和点，则称L为G的M可扩路(M—Extensible Path)。
例如，在图7-60(a)中，对于匹配M?{(1,6),(2,7),(3,9)}，路L1:16273，L2:27394，
L3:5394，L4:51627394都是M交替路，其中L3,L4的始点和终点都是M不饱和点，所以这
两条路是M可扩路。
可扩路具有如下性质：可扩路的长度必为奇数，且属于M的边比不属于M的边少1条。 如果在一条可扩路中把属于M中的边从匹配中去掉，把不属于M中的边添入到匹配中， 则得到新的匹配M1，M1的边数比M多１。例如，在图7-60(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中不存在可扩
路为止。用此方法可逐步得到较大的匹配，直至得到最大匹配。这就是下面的定理。
定理7.5.2 在图G中，M为最大匹配的充分必要条件是不存在可扩路。 证明 先证必要性。
用反证法。假设G中存在一条M可扩路，则可以得到比M的边数多１的匹配，与M为最大匹配矛盾。所以G中不存在M可扩路。
再证充分性。
用反证法。假设M不是最大匹配，则存在匹配M1，使得M1?M。令M2?M?M1（?为对称差运算），设由M2导出的G的子图G[M2]?H，因为M和M1都是G的匹配，所以H的任意顶点或是只与M（或M1）中的一条边相关联，或是同时与M的一条边及M1的一条边相关联，其度数至多为2，于是H的每个连通分支或者是一个边交错地属于M与M1的长度为偶数的回路，或者是边交错地属于M与M1的长度为奇数的交错路。 由于M1?M，因而H中必有一个连通分支P，它所含的属于M1的边比属于M的边多，P不是回路（因为回路的长度均为偶数），它的起点和终点都是M不饱和的，也一定是G中的M不饱和点，因此在G中存在关于M的可扩路，这与假设矛盾。
求一般图的最大匹配过程比较复杂，下面仅讨论如何在二部图中求最大匹配的问题。 设二部图G?V1,V2,E，在G中求最大匹配的关键是寻找可扩路。通常是先构造G的一个匹配M，再看V1中有没有M不饱和点。 如果没有，那么M肯定是最大匹配了；如果有， 我们就从这些点出发找M可扩路，由M可扩路做出一个更大的匹配。寻找M可扩路的一个有效方法是标记法， 其过程如下：
首先在G中作一个匹配M，用（*）标记V1中所有M不饱和点， 然后交替地进行以下步骤（１）和（２）。
（１）选一个V1的新标记过的节点，比如xi， 用（xi）标记不通过M中的边与xi邻接且未标记过的V2的所有节点。 对V1所有新标记过的节点重复这一过程。
（２）选一个V2的新标记过的节点，比如yj， 用（yj）标记通过M中的边与yj邻接且未标记过的V1的所有节点。对V2所有新标记过的节点重复这一过程。
334
执行以上步骤， 直至标记到一个V2中的M不饱和点。从该节点倒向追踪到标记有（*）的节点，就得到一条M可扩路。于是也就得到一个边数为|M|＋１的匹配， 再返回（１）。 如果已不可能标记更多的节点，而V2的所有标记的节点均为M饱和点，则说明G中已不存在M可扩路，这时M就是最大匹配。
例7.5.3 图7-61(a)是一个二部图， 求其最大匹配。
图7-61
点x1,x2,x4。
解 取图7-61图(a)的一个匹配M?{(x3,y1),(x5,y2)}。用（*）标记V1中所有M不饱和（1）选V1的新标记过的节点x1，用（x1）标记不通过M中的边与x1邻接且未标记过的V2的节点y1；类似地，用（x2）标记y2。
(2) 选V2的新标记过的节点y1， 用（y1）标记通过M中的边与y1邻接且未标记过的V1的节点x3；类似地，用（y2）标记x5。
(3) 选V1的新标记过的节点x3，因为不存在不通过M中的边与x3邻接的V2的节点，所以不用（x3）标记V2的节点；用（x5）标记y3或y4，假定用（x5）标记y3。
y3是M不饱和点，标记结束。
从y3倒向追踪到标记有（*）的节点，就得到一条M可扩路x2y2x5y3或x4y2x5y3，取前者，由此得匹配M1?{(x2,y2),(x3,y1),(x5,y3)}。
对匹配M1再用标记法（见图7-61(b)知， 图中已不存在M1可扩路，所以M1就是最大
匹配。
定理7.5.3（霍尔定理） 二部图G?V1,V2,E有V1―完全匹配，当且仅当对V1中任一子集A，和所有与A邻接的点构成的点集N(A)，恒有
N(A)?A
证明 先证必要性。假设M是二部图G?V1,V2,E的一个V1―完全匹配，则V1中的每个顶点均是M饱和的。对V1的任一子集A，因A的每个顶点在M下和N(A)中不同的顶点配对，所以有N(A)?A。
再证充分性。假设G是满足对任何V1的子集A，N(A)?A的二部图，但G中没有使V1中每个顶点饱和的完全匹配，设M1是G的一个最大匹配，由假设，M1不使V1中所有顶点饱
335