§6.3 完美对集
°奇分支和偶分支：奇数个顶点的分支称为奇分支；偶数个顶点的分支称为偶分支。用o(G)表示G的奇分支的个数。 定理6.4(Tutte定理)：图G有完美对集当且仅当
o(G?S)≤|S|,对所有S?V成立。 (6.6)
证：显然只要对简单图证明这个定理就行了。
首先假设G有完美对集M。设S是V的一个真子集，并设G1,G2, ?,Gn是G?S的奇分支，因为Gi是奇分支，所以Gi的某一顶点ui一定在M下和S的一个顶点vi配对(见图6.6)。所以，由于{v1,v2,?,vn} ?S，因而有
o(G?S)=n=|{v1,v2,?,vn}|≤|S|。
反之，假设G满足(6.6)式，但没有完美对集，则G是没有完美对集的极大图G?的生成子图。由于G?S是G??S的生成子图，所以 o(G??S)≤o(G?S)。因而由(6.6)式有
o(G??S)≤|S|,对所有S?V(G?)成立。 (6.7)
特别地，置S=?,o(G?)=0，因而υ(G?)是偶数。
用U表示G?中度为υ?1的顶点集。由于当U=V时，G?显然有完美对集，因此可以假定U≠V。我们将证明：G??U是完全图的不相交的并图。假若不然，G??U的某一分支不是完全图，则在此分支里存在顶点x,y和z，使得xy∈E(G?),yz∈E(G?)和xz?E(G?)。此外，由于y?U，在G??U中存在顶点w，使得yw?E(G?)。这种情形直观地
表示在图6.7中。
由于G?是不包含完美对集的极大图，所以对于所有e?E(G?)，G?+e都有完美对集。设M1和M2分别是G?+xz和G?+yw的完美对集， 并且用H表示由M1?M2导出的G?∪{xz,yw}的子图。由于H的每个顶点的度均为2，所以H是圈的不相交的并图。进而，由于沿着这些圈的M1的边和M2的边是交错的，所以所有这些圈都是偶圈。我们分两种情形讨论：（见图6.8）
情形1：xz和yw在H的不同分支中(图6.8 (a))。于是，若yw在H的圈C中，则M1在C中的边连同M2不在C中的边一起组成G?的一个完美对集，这和G?的定义矛盾。
情形2：xz和yw在H的同一分支C中。根据x和z的对称性，可以假定顶点x,y,w,z依次出现在C中(图6.8 (b))。于是M1在C的yw?z节中的边连同yz以及M2不在C的yw?z节中的边一起组成G?的一个完美对集，再次与G?的定义矛盾。
因此不论情形1或情形2都导致矛盾，由此可知G??U确是完全图的不相交的并图。
现在，根据(6.7)式有o(G??U)≤|U|。因此G??U的奇分支个数最多是|U|，但这样一来，G?显然就有一个完美对集：G??U的各奇分支中的一个顶点和U的一个顶点配对，U的余下的顶点以及G??U的各分支中余下的顶点，则也相互配对，正如图6.9所表示的那样。
由于假定G?是没有完美对集的，因而得到了希望出现的矛盾。于是G确实有完美对集。 ?
推论6.4：每个没有割边的3正则图都有完美对集。
证明：设G是没有割边的3正则图，S是V的真子集，用G1,G2,?, Gn表示G?S的奇分支，并设mi是一个端点在Gi中，另一个端点在S中的那些边的条数。由于G是3正则的，所以
∑d(v)=3υ(Gi), 对1≤i≤n成立 (6.8)
v∈V(Gi)
并且
∑d(v)=3|S| (6.9)
v∈S
由(6.8)式，mi=∑v∈V(Gi)d(v)?2ε(Gi)是奇数，又由于G没有割边，所以mi≠1。因此，
mi≥3 对1≤i≤n成立 (6.10)
从(6.10)式和(6.9)式即可推出
o(G?S)=n≤
1 1
∑mi≤∑d(v)=|S| 33i=1
v∈S
n
所以，根据定理6.4，G有完美对集。
*具有割边的3正则图不一定有完美对集。（见图6.10）
§6.4 人员分派问题
°问题：某公司准备分派n个工人X1,X2,?,Xn做n件工作Y1,Y2,?,Yn, 已知这些工人中每个人都胜任一件或几件工作。试问能不能把所有工
人都分派做一件他所胜任的工作？这就是人员分派问题。 °转化为图论问题：构作一个具有二分类(X, Y)的偶图G，这里X={ x1,x2,?,xn},Y={y1,y2,?,yn}, 并且xi与yj相连当且仅当工人xi胜任工作yj。于是问题转化为确定G是否有完美对集的问题。
°算法的基本思想：从任一对集M开始，若M饱和X中每个顶点，则M就是所需要的对集。如果不是这样，则在X中选择一个M非饱和顶点u，并且系统地寻找一条以u为起点的M-可扩路，寻找方法下?=M? 面再详述。找出这样一条路P，如果它存在的话；这时，M
?代替E(P)就是比M更大的对集，因而饱和X中更多的顶点。然后以MM，并重复这个程序。如果这样的路不存在，则通过M交错路与u相连接的那些顶点的集合Z就可找到。于是(如同定理6.2的证明那样)，S=Z∩X满足|N(S)|<|??|。
°扎根于顶点u的M-交错树：(见图6.11)
°匈牙利算法：
从任意一个对集M开始。
1. 若M饱和X的每个顶点，则停止。否则，设u是X中的M非饱和顶点。置S={u}及T=?。
2. 若N(S)=T,由于|T|=|S|?1,所以|N(S)|<|S|，因而停止，因为根据Hall定理，不存在饱和X的每个顶点的对集。否则，设y∈ N(S)\\T。
3. 若y是M饱和的。设yz∈M,用S∪{z}代替S，T∪{y}代替T，并
转到第2步(注意这样替换后，|T|=|S|?1依然成立)。否则，设?=M?E(P)代替M，并转到第1步。 P是M-可扩(u, y)路，用M°例子：(见图6.11)
§6.5 最优分派问题
°问题：在人员分派问题中，考虑每个工人做每一项工作的效率，找一个工作安排使得总效率最大。寻找这种分派的问题称为最优分派问题。
°图论问题：考察一个具有二分类(X,Y)的赋权完全偶图，这里X={x1, x2,?,xn},Y={y1,y2,?,yn}，边xiyj有权wij=w(xi,yj)，表示工人xi做工作yj时的效率。最优分派问题显然等价于在这个赋权图中寻找一个有最大权的完美对集。这种对集称为最优对集。
°可行顶点标号：在X∪Y上定义实值函数l，适合下述条件：对任意x ∈X和y∈Y，均有
l(x)+l(y)≥w(xy) (6.11)
则把函数l称为该偶图的一个可行顶点标号。l(v)称为v的标号。 可行顶点标号总是存在的，例如：
l(x)=max w(xy),若x∈Xy∈Y (6.12) {
l(y)=0 ,若y∈Y
°相等子图：若l是可行顶点标号，则用El表示使(6.11)式中等式成立的那些边的集合，即
El={xy∈E | l(x)+l(y)=w(xy)}
图论及其应用9
