第5章+匹配

第五章匹配5.1匹配5.2独立集、团、覆盖、和匹配间的关系5.3偶图的匹配和覆盖5.4完美匹配5.5人员分派问题5.6最优分配问题5.7稳定匹配5.1匹配匹配（matching）MEM中的边都是link，且互不相邻接。当边uvM时，称u与v在M下相匹配；称M饱和（saturated）u与v。也称u与v为M-饱和的。类似地，可给出一顶点x为M-不饱和的的定义。M为图G的完美匹配G中每个顶点都是M-饱和的。M为图G的最大匹配（maximummatching）…P为G中的M-交错路(M-alternatingpath)P的边交替地属于M及E\M。P为G中的M-可扩路（M-augmentingpath)P为M-交错路，且起点与终点都是M-不饱和的。定理5.1(Berge,1957)M为G中的最大匹配G中不存在M-可扩路。证明：：假设G中有M-可扩路P，则M’=ME(P)也是G的匹配，且M’=M+1，这与M为最大匹配相矛盾。：反证，假设M不是最大匹配，取G中任一最大匹配M*。令H=G[MM*]。显然，dH(v)=1or2vV(H)。因此，H的每个分支都是一圈或路，由M及M*的边交错组成。但M*M，H中一定有一分支是一条路P，且其起点与终点都是M*饱和的。从而P是G中的M-可扩路，矛盾。习题5.1.1(a)证明：每个k-方体都有完美匹配(k3)。(b)求K2n与Kn,n中不同的完美匹配的个数。5.1.2证明：一树中最多只有一个完美匹配。5.1.3对每个k1，找出一个无完美匹配的k-正则简单图的例子。5.1.4两人在图G上做游戏，交替地选取不同的顶点v0,v1,v2,.........，使对每个i0，都有vi与vi-1相邻。最后一个顶点的选择者胜。证明：第一个选点人有一得胜策略当且仅当G没有完美匹配。5.1.5G的k-正则生成子图称为G的k-因子。若G存在边不重的k-因子H1，H2，……，Hn，使得G=H1H2……Hn，则称G为k-可因子分解的。(a)证明：①Kn,n与K2n是1-可因子分解的；②Peterson图不是1-可因子分解的。(b)下面的图中哪些有2-因子：(c)用Dirac定理若G是简单图，(4)是偶数，且1+/2，则G有3-因子。5.1.6*证明：K2n+1可表为n个连通的2-因子的并。5.2偶图的匹配和覆盖邻集（neighbourset）N(S)（SV）：G中所有与S中顶点相邻接的顶点集合。定理5.2（Hall’stheorem,1935)在偶图G=(X,Y,E)中G包含使X中每个顶点都饱和的匹配N（S）SSX证明：：显然。：反证，假设存在偶图G，它满足条件（*）但不包含使X中每个顶点都饱和的匹配。令M*为G的最大匹配，u为X中M*不饱和的顶点。记Z={vM*-交错（u，v）-路}由于M*为最大匹配，由定理5.1，u为Z中唯一M*-不饱和顶点。令S=Z∩X，T=Z∩Y。显然，S\U与T的顶点在M*下相匹配（注意到：任一M*-边若有一端点在Z中，则其另一端一定也在Z中）。因此，T=S-1；N(S)T。但N(S)中每个顶点都有M*-交错路连到u，因此N(S)T，故N(S)=T，从而N(S)=T=S-1S。矛盾。定理5.2（Hall’stheorem,1935)在偶图G=(X,Y,E)中G包含使X中每个顶点都饱和的匹配N（S）SSX推论5.2(marriagetheorem)若G为k-正则偶图（k0)，则G有完美匹配。证明：设G的2-划分为(X,Y)，则kX=E=kY，X=Y。又，对任SX，令E1和E2分别为与S和N(S)相关联的边集。易见，E1E2。∴kS=E1E2=kN(S)∴SN(S)SX。故G中有使X中每个顶点都饱和的匹配M，它也是完美匹配。称K（V）为G的一个覆盖（covering）G中每边至少有一端在K中。最小覆盖（minimumcovering）。对G中任一覆盖K及任一匹配M，显然，恒有MK。特别地，有M*。~K~K引理5.3设M与K分别为G中的匹配与覆盖，如果M=K则M为最大匹配，K为最小覆盖。定理5.3(Konig’stheorem,1931)设M*，分别为偶图G的最大匹配和最小覆盖，则M*=。~K~K定理5.3(Konig’stheorem,1931)设M*，分别为偶图G的最大匹配和最小覆盖，则M*=。证明：设G的2-划分为（X，Y）。记U={uXu为M*-不饱和的}Z={vVM*-交错（u，v）-路，uU}S=Z∩X，T=Z∩Y。与定理5.2之证明类似，我们有：T中每顶点都是M*-饱和的；T与S\U中顶点在M*下相匹配；N(S)=T。记=(X\S)∪T。易见，G中每边至少有一端在中，即为G的覆盖（不然，G中就有一边其两端分别在S与Y\T中，这与N(S)=T相矛盾）。又，显然，=X\S+T=X\S+S\U=X-U=M*。再由引理5.3知为最小覆盖。~K~K~K~K~K习题5.2.1证明：一个55方格棋盘去掉其对角上的两个11方格之后，不可能用12长方格恰好添满。5.2.2(a)证明：偶图G有完美匹配当且仅当对所有SV都有N(S)S。(b)举例说明：去掉偶图这个条件之后，上述不成立。5.2.3对于k0，证明：(a)每个k-正则偶图都是1-可因子分解的；(b)*每个2k-正则图都是2-可因子分解的。5.2.4设A1，A2，……，An是某集S的子集。族（A1，A2，……，An）的一个相异代表系是指S的一个子集{a1，a2，……，an}使aiAi（1in），且aiaj（当ij）。证明：（A1，A2，……，An）有一个相异代表系当且仅当JJ{1,2,...,n}。5.2.5矩阵的一行或一列统称一条线。证明：一（0,1）-矩阵中，含所有1元素的线的最小条数=两两都不在相同线上的1元素的最大个数。5.2.6(a)证明Hall定理的一个推广：偶图G=（X,Y;E)的最大匹配的边数是X-{S-N(S)}。(b)试证：若G为简单偶图，且X=Y=n及(k-1)n，则G有边数为k的匹配。AiiJmaxSX5.2.7由Konig定理推导Hall定理。5.2.8*若非负实数矩阵Q的每行元素之和均为1，每列元素之和也均为1，则称Q为双随机矩阵。称一矩阵为置换矩阵如果它是每行和每列均恰只有一个1元素的（0，1）-矩阵（∴是双随机的）。证明：(a)每个双随机矩阵一定是个方阵；（注：(a)与(b)无直接联系。）(b)每个双随机矩阵Q都可表为置换矩阵的凸线性组合，即Q=c1P1+c2P2+……+ckPk。其中每个Pi都是置换矩阵，每个ci都是非负实数，且。5.2.9若偶图G=(X,Y,E)中，X中每个顶点的度Y中每个顶点的度，则G有使X每顶点ciik115.2.10*设偶图G=(X,Y,E)中，Y’为匹配M在Y中的端点集，则存在G的最大匹配M*，其端点集包含Y’。5.2.11简单偶图G=(X,Y;E)中，若对任二顶点xX,yY，都有d(x)d(y)，则G中有一匹配饱和X中每一顶点。5.2.12设简单偶图G=(X,Y;E)中，X’为X中所有度为的顶点子集，则G中存在饱和X’中每个顶点的匹配5.2.13有m对夫妻，今将男女各随意分成r组（rm）。今欲从每组选一代表，问该2r个代表恰为r对夫妻的充要条件是什么？5.2.14设A为mn(0,1)-矩阵，mn。如果A的每行恰有k(m)个1，每列有k个1，证明：A=P1+P2++Pk，其中每个Pi为mn(0,1)-矩阵，每行恰有一个1，每列至多有一个1。5.2.15一rn矩阵A=[aij]，rn，称为拉定矩形，如果每个元素aijN={1,2,,n}，且在每行每列中，每个整数kN至多出现一次。试证：A恒可延伸为一nn拉定方。（提示：先证明A可延伸为(r+1)n拉定矩阵。）5.2.16用Menger定理证明Hall定理。5.4完美匹配称H为G的奇分支（oddcomponent）H为G的分支，且其顶点数为奇数。称H为G的偶分支（evencomponent）……。记o(G)=G中奇分支数。定理5.4(Tutte,1947)G有完美匹配o(G-S)SSV证明：（Lavasz证法）只要对简单图情形加以证明即可。：设G有完美匹配M。对任SV，令G1，……，Gn为G-S中的奇分支。因每个Gi的顶点数都是奇数，每个Gi中至少有一顶点ui与S中一顶点vi在M下相匹配。从而o(G-S)=n={v1，……，vn}S。：反证。假设存在图G满足条件（*），但不含完美匹配。令G*为G的不含完美匹配的极大生成母图。由于G-S是G*-S的生成子图，o(G*-S)o(G-S)SSV。即G*满足条件（*），又，上式中令S=得o(G*)=0，因此(G*)=偶数。令。因G不含完美匹配，UV。1)()({**vdGVvUG断言G*-S是一些完全图的不相交并。于是，由于o(G*-U)U，G*-U中至多有U个奇分支。从而，由断言易见，G*中有完美匹配，这与G*之假设矛盾。来证断言反证。假设G*-U有一分支不是完全图，则其中一定存在3个顶点x，y，z使xy,yzE(G*)，而xzE(G*)（习题1.6.9）。又，因yU，一定存在wV(G*-U)使ywE(G*)。令M1与M2分别为G*+xz与G*+yw中的完美匹配。考虑G*+{xz，yw}中M1M2的边导出子图H。显然，H中顶点的度都是2，因而H是一些圈的不相交并。且每圈都是偶圈，由M1与M2的边交错组成。情况1xz与yw不在H的同一圈中：设yw在圈C上，则C中所有M1边及C外所有M2边一起构成G*的一个完美匹配，矛盾。情况2xz与yw同在H的某一圈C上：不妨设x，y，w，z以这顺序出现于C上。这时，C的yw……z节中的所有M1边，及不在该节中的所有M2边，以及边yz，一起构成G*的一个完美匹配，矛盾。推论5.4(Peterson,1891)每一不含割边的3-正则图都有一完美匹配。证明：对任SV，令G1，……，Gn为G-S中的所有奇分支。记mi为一端在Gi中而另一端在S中的边数。则。但G中无割边，因此mi3。从而3S=。∴Sn=o(G-S)SV。故由定理5.4，G有完美匹配。mdvGGGivVGiiii()()()()()232奇数dvmnvSiin()13例。以下前4图满足定理5.4条件；而最后一图不满足定理5.4条件：习题5.3.1*用Tutte定理推导Hall定理。5.3.2推广推论5.4：若G是（k-1）边连通的k-正则图，且是偶数，则G有完美匹配。5.3.3设G为一树，证明：G有完美匹配o(G-v)=1vV。5.3.4*证明Tutte定理的推广：G的最大匹配的边数=(-d)/2，其中doGSSSVmax{()}5.4人员分派问题（（thepersonnel）assignmentprob.）问题n个工人x1，……，xn及n个工作y1，……，yn，已知每个工人各胜任一些工作。能否使每个工人都分派到一件他胜任的工作？解：在偶图G=(X,Y,E),X=Y,中求出其完美匹配（若存在的话）。以下是其算法：Hungarianmethod(Edmonds,1965)以任一匹配M作为开始。（可取M=）①若M饱和X的每个顶点，停止（M为完美匹配）。否则，取X中M-不饱和顶点u，S{u}，T。②若N(S)T,转到③；否则，N(