Chap11 匹配与点独立集

1、第十一章第十一章匹配与点独立集匹配与点独立集1顶点和边是图的基本要素，本章将要介顶点和边是图的基本要素，本章将要介绍的匹配、点独立集、覆盖和团等概念刻画绍的匹配、点独立集、覆盖和团等概念刻画了顶点与顶点、边与边以及顶点与边之间的了顶点与顶点、边与边以及顶点与边之间的相互关系，它有助于我们了解图的结构。相互关系，它有助于我们了解图的结构。11.1 匹配匹配 匹配问题是运筹学的重要问题之一，也是匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓图论的重要内容，它在所谓“人员分配问题人员分配问题”和和“最优分配问题最优分配问题”中有重要作用。中有重要作用。配偶问题：假定配偶问题：假定有一个

2、男生有穷集合，其中有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生结婚男生都可以和他认识的女生结婚？类似类似的工作分配问题：现有的工作分配问题：现有n n个人，个人，m m份工作，份工作，每个人有其擅长的工作。在什么条件下每个每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？人都可以得到一份他擅长的工作？如何分配？配偶问题配偶问题男生 认识的女生b1g1,g4,g5b2g1b3g2,g3,g4b4g2,g4配偶问题：配偶问题：二分图是否存在一个边二分图是否存在一个边集集M使得使得其中任其中任

3、意两边不邻接，且每个结点意两边不邻接，且每个结点bi与与M的某条边的某条边关联。关联。例例b1b2g1b4g5b3g4g2g3配偶问题配偶问题求解求解配偶问题配偶问题例例b1b2g1b4g5b3g4g2g3二分图二分图G(V1,V2)的饱和匹配的饱和匹配: 是否是否存在存在单射单射f: V1V2使得使得任意任意v V1, v与与f(v)相邻。相邻。二二分图存分图存在饱和匹配在饱和匹配的的必要必要条件：条件：任意任意k个男生至少认识个男生至少认识k个女生。个女生。这个这个条件也是条件也是充分充分的。的。匹配的基本概念匹配的基本概念匹配：匹配：设设G是图，是图，M E(G)。若。若M中的边都是杆、

4、中的边都是杆、且任意两条边均不邻接，则称且任意两条边均不邻接，则称M为为G的一个匹配。的一个匹配。 易知易知一个图一个图G的匹配可能不唯一的匹配可能不唯一。最大匹配：最大匹配：G的边数最多的匹配称最大匹配的边数最多的匹配称最大匹配。最大匹配数：最大匹配数：最大匹配所含的边数称为最大匹配最大匹配所含的边数称为最大匹配数，记为数，记为 (G)。 显然显然对一个图对一个图G(p,q)， (G) p/2。6右图右图中用粗线表示的边的集合就是一中用粗线表示的边的集合就是一个匹配，且是最大个匹配，且是最大匹配，匹配， (G) =3。饱和点饱和点定义中的匹配定义中的匹配M是图是图G中一些互相不邻接的边，中一

5、些互相不邻接的边，而而M实际上描述的是图实际上描述的是图G中相互匹配的顶点对。中相互匹配的顶点对。这里的配对是严格的一夫一妻制。这里的配对是严格的一夫一妻制。7设设M是是G的一个匹配，的一个匹配，vV(G)。若若v与与M中的某边关联，则称中的某边关联，则称v是是M饱和点饱和点，否，否则称则称v为非为非M饱和点饱和点。若若uvM，则称，则称u和和v配对配对。左左图中红色的顶点是图中红色的顶点是M-饱饱和点，而每和点，而每条条黑色粗边的黑色粗边的两个顶点配对。两个顶点配对。完美匹配完美匹配设设M是是G的一个匹配，如果的一个匹配，如果G的每一个顶点都是的每一个顶点都是M-饱和点，则称饱和点，则称M为

6、为完美匹配完美匹配。8 完美匹配是让图中所有顶完美匹配是让图中所有顶点都点都成双成对成双成对的匹配。的匹配。 显然只有在偶数个顶点的显然只有在偶数个顶点的图中才会有完美匹配。图中才会有完美匹配。这是一个完美匹配。这是一个完美匹配。最大匹配与完美匹配最大匹配与完美匹配完美匹配必定是最大匹配，但反之不然。完美匹配必定是最大匹配，但反之不然。任何图任何图G一定有最大匹配，但却不一定有完美匹一定有最大匹配，但却不一定有完美匹配。配。含奇数顶点的图不可能有完美匹配，因为无论如含奇数顶点的图不可能有完美匹配，因为无论如何配对，注定有人打单身。何配对，注定有人打单身。有完美匹配的图一定是偶数个顶点，但偶数个

7、顶有完美匹配的图一定是偶数个顶点，但偶数个顶点的图中也未必能使天下人终成眷属点的图中也未必能使天下人终成眷属。9v1v2v3v6v4v5v7v8这是最大匹配而不是完美匹配这是最大匹配而不是完美匹配。此此图尽管是偶数个顶点却无完图尽管是偶数个顶点却无完美匹配。美匹配。问题：最大匹配与完美匹配之间有什么关系呢？问题：最大匹配与完美匹配之间有什么关系呢？最大匹配的判定最大匹配的判定最简单的情况最简单的情况：G是一条单通路。显然是一条单通路。显然G的边应交错地属于的边应交错地属于M(M不能有邻接的边不能有邻接的边)。G的第一条边和最后一条边中至少应有一条边属的第一条边和最后一条边中至少应有一条边属于于

8、M (否则否则M不是最大匹配不是最大匹配)。如下图所示：。如下图所示：10粗线的边集是最大匹配粗线的边集是最大匹配粗线的边集不是最大匹配粗线的边集不是最大匹配问题：图问题：图G中什么样的匹配中什么样的匹配M会是最大匹配呢？会是最大匹配呢？M交错路交错路定义定义11.1.2 设设M是是G的一个匹配，的一个匹配， 是是G的一条通路。的一条通路。如果如果 中的边依次交错地属于中的边依次交错地属于M与与E (G) M，则称，则称 是是M交错路。交错路。11v1v2v3v5v4v6v7v8在在右图的匹配右图的匹配M=v1v3，v2v5，v7v8中中， = v1v3v5v2就是一条就是一条M交错路。交错路

9、。M可增广路可增广路定义定义11.1.3 设设M是是G的一个匹配，的一个匹配， 是一条是一条M交错路。交错路。若若 的起点和终点都是非的起点和终点都是非M饱和点，则称饱和点，则称 是是M可可增广路。增广路。12v1v2v3v4v5v6v7v8在在右右图所示的匹配图所示的匹配M=v1v4, v2v3, v6v7中中, = v8v7v6v5就是一条就是一条M可增广路。可增广路。 在在M-可可增广路中，第一增广路中，第一条边与最后一条边都条边与最后一条边都不是不是M中的中的边，边，因而因而M-可可增广路中增广路中属于属于M的的边数比边数比不在不在M中中边边数少一条。数少一条。M为最大匹配的充要条件为

10、最大匹配的充要条件定理定理11.1.1 图图G的匹配的匹配M是最大匹配当且仅当是最大匹配当且仅当G中无中无M可增广路。可增广路。证明：证明：（必要性）（必要性）设设M是是G的一个最大匹配。若的一个最大匹配。若G中存在中存在M可增广路可增广路 ， 的长度必为奇数，且的长度必为奇数，且不属于不属于M的边比属于的边比属于M的边恰好多一条。令的边恰好多一条。令M = M=(M)(M)。13即即M选取的是选取的是 中中所有不属于所有不属于M的边的边显然显然M也是也是G的一个匹配，且的一个匹配，且|M| = |M| + 1|M|。此与此与M的假设矛盾。故的假设矛盾。故G中中无无M可增广路。可增广路。 任任

11、取取v H，d(v)为为1或或2。H的每个连通分支是的每个连通分支是一条一条 M边和边和M边交错出现的通路或偶数长度的回路。边交错出现的通路或偶数长度的回路。|M|M|，H包含包含M的边多于的边多于M的边，从而必的边，从而必有一个连通分支有一个连通分支P中的中的M边多于边多于M边。边。P是开始边是开始边和终止边都是和终止边都是M边的通路，即边的通路，即M可增广路。矛盾。可增广路。矛盾。故故M为最大匹配。为最大匹配。证明：证明：（充分性）（充分性）设设G中不存在中不存在M可增广路。可增广路。14 若若M不是最大匹配，则可令不是最大匹配，则可令M是最大匹配，是最大匹配，|M|M|。令。令H=GM

12、M (边导出子图边导出子图)。 M与与M都是匹配，都是匹配，v最最多只能与一条多只能与一条M中的边中的边和一条和一条M中的边关联。中的边关联。H中的边要么属于中的边要么属于M，要么属于，要么属于M。PMMM为最大匹配的充要条件（续）为最大匹配的充要条件（续）求最大匹配的方法求最大匹配的方法定理定理11.1.1实际上给出了一种求最大匹配的方法：实际上给出了一种求最大匹配的方法：任取任取G的一个匹配的一个匹配M；在在G中找一条中找一条M可增广路可增广路 ；令；令M为为 上的所有边的上的所有边的集合；集合；M:=M M; 重复第重复第步和步和第第步，直到在步，直到在G中找不到中找不到M可增广路。可增

13、广路。v1v2v3v4v5v6v7v8M=v1v4， v5v8 = v2v1v4v3M=v1v2, v3v4, v5v8 = v6v5v8v7M=v1v2, v3v4, v5v6, 7v8最最大大匹匹配配二分图的匹配二分图的匹配16 有7名研究生 A, B, C, D, E, F, G毕业寻找工作。就业处提供的公开职位是：会计师(a) ,咨询师(b),编辑(c ),程序员(d), 记者(e), 秘书(f)和教师(g)。每名学生申请的职位如下：A : b, c ; B : a, b, d, f, g ; C : b, e ; D : b, c, e ; E : a, c, d, f ; F :

14、c, e ; G : d, e, f, g ; 问：学生能找到理想工作吗？ 在日常生活，工程技术中，常常遇到在日常生活，工程技术中，常常遇到求二分图求二分图的匹配问题。下面看一个例子：的匹配问题。下面看一个例子：17 问题转化为问题转化为求饱和求饱和X中每个中每个顶点的一个匹配顶点的一个匹配！FEDCBAGabcdefg需要需要解决的问题是解决的问题是:(1) 匹配是否存在匹配是否存在？(2) 如何求出匹配？如何求出匹配？二分图饱和匹配二分图饱和匹配存在性存在性判定判定-Hall定理定理二分图的饱和匹配二分图的饱和匹配问题分析：问题分析：如果令如果令X=A, B, C, D, E, F, G,

15、Y=a, b, c, d, e, f , g，X中顶点与中顶点与Y中顶点连线当且仅当学生中顶点连线当且仅当学生申请了该工作。于是，得到反映学生和职位之间的状申请了该工作。于是，得到反映学生和职位之间的状态图态图：邻集邻集定义定义11.1.4 设设G是一个图，是一个图，V0 V(G)。G中与中与V0中的中的顶点邻接的所有顶点之集合，称为顶点邻接的所有顶点之集合，称为V0的邻集，记为的邻集，记为NG(V0)。18v1v2v3v4v5v6NG(V0)=v2,v4,v5下面下面我们我们讨论讨论二二分图分图G有饱和匹配的充要条件。有饱和匹配的充要条件。V0=v3,v6二分图饱和匹配的充要条件二分图饱和匹

16、配的充要条件定理定理11.1.2(Hall定理定理) 设设G是具有二划分是具有二划分(X, Y)的二的二分图，分图，G有饱和有饱和X中每个顶点的匹配当且仅当对任何中每个顶点的匹配当且仅当对任何S X，有，有 | S | | NG(S) | (11.1)证明证明：（必要性）必要性）设匹配设匹配M饱和饱和X所有顶点的，所有顶点的，则则X的每一个顶点在的每一个顶点在Y中至少有一个邻接中至少有一个邻接点，点，任取任取S X，S的顶点在的顶点在M中与中与NG(S) 的顶点配对，且这些顶点互的顶点配对，且这些顶点互不相同，因此不相同，因此| S | | NG(S) |。19二分图饱和匹配的充要条件二分图饱

17、和匹配的充要条件（续续1）证明：证明：（充分性）反证法，充分性）反证法，假设最大匹配假设最大匹配M*也也不饱和不饱和X的所有顶点。的所有顶点。20 设设u是是X的一个非的一个非M*饱和点，并设饱和点，并设Z是是G中通中通过过M*交错路与交错路与u相连接的顶点的集合。由相连接的顶点的集合。由M*的性的性质及定理质及定理11.1.1知知，u是是Z中唯一非中唯一非M*饱和点饱和点。uSXT= NG(S) Y令令S=ZX， T=ZY。显然，显然，Su中的顶点在中的顶点在M*下与下与T中的顶点两两相互中的顶点两两相互配对。因此配对。因此|S|1=|T| (11.2)。下证下证T=NG(S)。 二分图饱和

18、匹配的充要条件（续二分图饱和匹配的充要条件（续2）21证明：证明：（下证（下证T=NG(S)）对对 v T，G中有由中有由u到到v的的M*交错路交错路P，而，而G是二分图，于是是二分图，于是P上与上与v邻接邻接的顶点必是的顶点必是S中的顶点，从而中的顶点，从而v NG(S)。 反之，对反之，对 v NG(S)，设，设S中中v的邻接点是的邻接点是w，而而P是由是由u到到w的的M*交错路交错路。若。若v P，则，则P上由上由u到到v的一节是的一节是M*交错路，交错路，v Z；否则，因；否则，因P的长的长度为偶数且度为偶数且最后一条最后一条边属于边属于M*，有有wv M*，从，从而而P+wv是是M*

19、交错路，亦有交错路，亦有v Z；又因；又因G是二分是二分图，所以图，所以v T( =ZY )。于是。于是T=NG(S)。 (11.3) uwvSNG(S)PvP+wv二分图饱和匹配的充要条件（续二分图饱和匹配的充要条件（续3）定理定理11.1.2(Hall定理定理)：设：设G是具有二划分是具有二划分(X, Y)的的二分图，二分图，G有饱和有饱和X中每个顶点的匹配当且当对任中每个顶点的匹配当且当对任何何S X，有，有| S | | NG(S) | 。 (11.1)证明：证明：（充分性）（充分性）因此因此|S|1=|T|。 (11.2) 于是于是T=NG(S)。 (11.3) 最后，由最后，由(1

20、1.2)和和(11.3)有有 | NG(S) | = | T | = | S | 1 | S | 此与此与(11.1)矛盾。故矛盾。故G有饱和有饱和X的所有顶点的匹配。的所有顶点的匹配。2223FEDCBAGabcdefg解解: (1) 当当S取取X中单元点时，容易验证中单元点时，容易验证：|S|N(S)| (2) 当当S取取X中二元点集时，中二元点集时，容易验证：容易验证：|S|N(S)| (3) 当当S取取X中三元点集时，中三元点集时，容易验证容易验证：|S|N(S)| (4) 当当S取取X中四元点集时中四元点集时，若若取取S=A,C,D,F,则有则有3=|N(S)|S|=4所以所以，不存

21、在饱和，不存在饱和X每个顶点的匹配。每个顶点的匹配。运用运用Hall定理求解例题定理求解例题例题：例题：是否是否存在饱和存在饱和X=A, B, C, D, E, F, G的每的每个顶点的匹配？个顶点的匹配？几个充要条件几个充要条件uM是是G的的最大匹配最大匹配 G中不存在中不存在M-可增广路可增广路u二二分分图图G具有具有饱和饱和X的匹配的匹配 对任意对任意S X，有有| S | | NG(S) |问题：那么完美匹配的充要条件又是什么呢？问题：那么完美匹配的充要条件又是什么呢？ 完美匹配是特殊的最大匹配，所以它的判定完美匹配是特殊的最大匹配，所以它的判定条件肯定比最大匹配的判定条件要强。条件肯

22、定比最大匹配的判定条件要强。考虑完美匹配考虑完美匹配G有偶数个顶点；且每个连通分支有完美匹配。有偶数个顶点；且每个连通分支有完美匹配。若从若从G中删去一个顶点，只会使中删去一个顶点，只会使G中的一个顶点失去中的一个顶点失去其匹配。其匹配。若从若从G中删去一个顶点，会使中删去一个顶点，会使G成为奇数个顶点。若成为奇数个顶点。若因此使因此使G不连通的话，也只会产生一个具有奇数个顶不连通的话，也只会产生一个具有奇数个顶点的连通分支。点的连通分支。25如果图如果图G具有完美匹配，则具有完美匹配，则如果继续从如果继续从G中删去顶点，每删去一个顶点至多会增中删去顶点，每删去一个顶点至多会增加一个具有奇数个

23、顶点的连通分支。加一个具有奇数个顶点的连通分支。奇奇(偶偶)分支分支 为方便起见，我们称具有奇为方便起见，我们称具有奇(偶偶) 数个顶点的连通数个顶点的连通分支为奇分支为奇(偶偶)分支。并用分支。并用O(G)表示图表示图G中奇分支的个中奇分支的个数。数。26从上边的讨论中，我们看到具有完美匹配的图从上边的讨论中，我们看到具有完美匹配的图G的一的一个重要性质：个重要性质： 从从G中删去若干顶点，所产生的具有奇数个顶点中删去若干顶点，所产生的具有奇数个顶点的连通分支不多于删去的顶点数。的连通分支不多于删去的顶点数。完美匹配的必要条件完美匹配的必要条件引理引理11.1.1 如果图如果图G存在完美匹配

24、，则对任意存在完美匹配，则对任意S V(G)，有有 O(GS) | S | (11.4) 证明：设证明：设G有一个完美匹配。令有一个完美匹配。令S V(G)，并设，并设G1,Gn是是GS的所有奇分支。的所有奇分支。27G1v1Gnvnu1un S奇分支偶分支 Gi是奇分支是奇分支, Gi的某顶点的某顶点vi必在必在M下匹下匹配配S的某顶点的某顶点ui，即，即uivi M。 (见右图见右图) O(GS)=|u1, , un |S|。再考虑完美匹配的必要条件再考虑完美匹配的必要条件G具有完美匹配的必要条件具有完美匹配的必要条件(11.4)是：是： S V(G)，有有O(GS) | S |。28若若

25、 S V (G) ，使，使GS有：有：每个偶分支有完美匹配；每个偶分支有完美匹配；每个每个Givi有完美匹配。有完美匹配。S只含有只含有u1, ,un；能够使得能够使得ui和和vi配对。配对。则则G就具有了完美匹配。就具有了完美匹配。再次考虑上图。再次考虑上图。它会不会也是充分条件呢？它会不会也是充分条件呢？条件条件(11.4)若能保证以上若能保证以上4点，也就是充分条件。点，也就是充分条件。G1v1Gnvnu1un S奇分支偶分支回顾几个引理回顾几个引理引理引理11.1.1 如果图如果图G存在完美匹配，则对任意存在完美匹配，则对任意S V(G)，有，有O(GS) | S |。 (11.4)

26、引理引理11.1.2 若图若图G满足条件满足条件(11.4)，则，则 S V(G)，使，使得得O(GS)=|S|。引理引理11.1.3 若图若图G满足条件满足条件(11.4)，设，设S0是使得是使得O(GS)=|S|的的S中顶点数最多的，中顶点数最多的， GS0的所有偶分的所有偶分支仍然满足条件支仍然满足条件(11.4)。引理引理11.1.4 设图设图G满足条件满足条件(11.4)且使且使O(GS)=|S|的的S中顶点数最多的为中顶点数最多的为S0， 则则 GS0 的每个奇分支减去的每个奇分支减去其任意一个顶点后满足条件其任意一个顶点后满足条件(11.4)。29完美匹配的充要条件完美匹配的充要

27、条件定理定理11.1.3：图：图G存在完美匹配，当且仅当对任意存在完美匹配，当且仅当对任意S V(G)，有，有O(GS) | S |。 (11.4) 证明：由引理证明：由引理11.1.1可知必要性成立。可知必要性成立。30 下面对下面对|V(G)|作归纳证明充分性成立作归纳证明充分性成立。归纳基础：归纳基础：当当|V(G)|=2时，由时，由( 11.4 )式可推出式可推出G有完美匹有完美匹配。配。 归纳步骤：归纳步骤：假设假设|V(G)|n时，时，G有完美匹配有完美匹配。当。当|V(G)|=n时，由引理时，由引理11.1.2知道存在着知道存在着S使得使得O(GS) =|S|。令。令S0为为其中

28、顶点数最多者其中顶点数最多者。由引理由引理11.1.3和和11.1.4，G S0的每个偶分支的每个偶分支Di和奇分支和奇分支Givi 仍然满足条件仍然满足条件(11.4)，由归纳假设可知它们都有完美，由归纳假设可知它们都有完美匹配。又由引理匹配。又由引理11.1.5有，每个奇分支有，每个奇分支Gi中的中的vi和和S0中的中的ui匹配。因此匹配。因此G也有完美匹配也有完美匹配。由由数学归纳法可知充分性也成立。数学归纳法可知充分性也成立。练一练练一练先考虑最简单的情况先考虑最简单的情况让我们先考虑满足让我们先考虑满足O(GS) | S | (11.4)的最简单的情况：的最简单的情况：31 满足满足

29、(11.4)的图的图G有偶数个顶点。有偶数个顶点。 若若|V(G)|为为奇数，则本身是奇分支，取奇数，则本身是奇分支，取S=，则则O(G)=10=|S|，不，不满足满足(11.4)，矛盾。，矛盾。 图图G应该是连通的。应该是连通的。 若若G不连通，则不连通，则G有两个奇分支，同样也不满有两个奇分支，同样也不满足足(11.4)。所以所以最简单情况是最简单情况是|V(G)|=2；简单情况的成功增加了我们的信心，也启示我们用简单情况的成功增加了我们的信心，也启示我们用归纳法归纳法去考虑更复杂的去考虑更复杂的情况情况。两两个顶点的连通图个顶点的连通图G显然有显然有G完美完美匹配。匹配。偶分支仍满足条件

30、偶分支仍满足条件(11.4)引理引理11.1.3 若图若图G满足条件满足条件(11.4)，设，设S0是使得是使得O(GS)=|S|的的S中顶点数最多的，则中顶点数最多的，则 GS0的所有偶的所有偶分支仍然满足条件分支仍然满足条件(11.4)。32证明：设证明：设D1, Dr是是GS0的所有偶分支，的所有偶分支，r0。 事实上事实上，设，设 S V(Di)，则则O(G S0) + O(Di S) = O(G (S0S) | S0S | = | S0 | + | S |。而而O(G S0) = | S0 |，因此，因此 O(Di S) | S | 。奇分支减一点满足条件奇分支减一点满足条件(11.

31、4)引理引理11.1.4 设图设图G满足条件满足条件(11.4)且使且使O(GS)=|S|的的S中顶点数最多的为中顶点数最多的为S0， 则则 GS0 的每个奇分支减去的每个奇分支减去其任意一个顶点后满足条件其任意一个顶点后满足条件(11.4)。33证明：设证明：设G1, , Gm是是GS0的所有奇分支。的所有奇分支。 假设假设 Gi和和 vV(Gi)，使得，使得Giv不满足条件不满足条件(11.4)，则则 SV(Gi v)，使得，使得O(GivS)|S|。 V(Giv)是偶数是偶数 O(GiviS)与与|S|同奇偶性。同奇偶性。则则O(GiviS) |S| + 2。于是。于是 O(G(S0vS

32、) = |S0vS|为什么为什么这与这与S0的最大性矛盾，所以的最大性矛盾，所以Giv满足满足(11.4)。 奇分支减一点满足条件奇分支减一点满足条件(11.4)34因为，一方面有因为，一方面有 O(G(S0vS)=O(GS0)1+O(GivS) | S0 | 1 + | S | + 2 = | S0 | + 1 + | S | (vGi,G-S0有有m个奇分支，个奇分支， Gi是其中之一，但是其中之一，但Gi-v已不是奇分支，故已不是奇分支，故G-S0的奇分支数要少的奇分支数要少1。)这里，已有这里，已有O(GS0)=| S0 |和和O(GivS)| S |+2。而另一方面由而另一方面由G满

33、足条件满足条件(11.4)又有又有 O(G(S0vS) | S0vS| = | S0 | + 1 + | S | 所以有所以有O(G(S0vS) = |S0vS|。存在存在S使得使得O(GS)=|S|我们先证明：我们先证明： S ：S只含有只含有v1, ,vn。35引理引理11.1.2 若若图图G满足条件满足条件(11.4)，则，则 S V(G)，使得使得O(GS)=|S|。证明证明：若若图图G满足条件满足条件(11.4)，则图，则图G具有偶数个顶点具有偶数个顶点。任任取取vV(G)，令，令S=v，则，则GS是奇数顶点是奇数顶点。从而从而有有O(GS) 1 = |S|，而而由条件由条件(11.

34、4) O(GS) |S|，可知可知，O(GS) = | S |。考虑考虑ui和和vi的配对的配对因为因为vi可以是奇分支可以是奇分支Gi中的任意顶点，所以这中的任意顶点，所以这个问题可以看作是：个问题可以看作是：能否使得能否使得ui和和Gi配对呢？配对呢？如果把每个如果把每个Gi看作一个点，令看作一个点，令X=G1,Gm，Y=u1, , um=S0，于是我们便构造了一个二分图，于是我们便构造了一个二分图H = X, Y ，并且，并且H依然满足依然满足条件条件(11.4) 。问题又转化为满足问题又转化为满足条件条件(11.4)的二分图的二分图 X, Y 中中是否存在匹配是否存在匹配M*使得使得X

35、中的每个顶点都是中的每个顶点都是M*饱和饱和点点(即饱和即饱和X的匹配的匹配)。还记得定理还记得定理11.1.2吗？吗？Hall定理定理。36让让ui和和vi配对配对引理引理11.1.5 设图设图G满足条件满足条件(11.4)且使且使O(GS)=|S|的的S中中顶点数最多的为顶点数最多的为S0， 则存在匹配则存在匹配M使得使得 GS0 的每个奇的每个奇分支和分支和S0的一个顶点匹配。的一个顶点匹配。37证明：令证明：令X=G1,Gn，Y=u1, , un=S0，而而Gi与与vS0邻接当且仅当在邻接当且仅当在G中中v与与Gi中的中的某顶点邻接。某顶点邻接。于是构造二于是构造二分图分图H = X,

36、 Y 。 对对 S X，令，令NH(S)=v V(S0)|v邻接邻接S中中的顶点的顶点。易证。易证|S|NH(S)|。即图。即图H满足满足Hall定理的条件。定理的条件。 从而从而存在饱和存在饱和X的匹配的匹配M，即，即GS0 的每个奇分的每个奇分支和支和S0的一个顶点匹配。的一个顶点匹配。G1Gnu1 v un S0X为什么？为什么？38对对 S X，令，令S=NH(S)=v V(S0)|v邻接邻接S中的顶点中的顶点。|S|是是G删去删去S0中某些顶点后的奇分支的数目，而中某些顶点后的奇分支的数目，而S中的点还可能与中的点还可能与X-S中的点中的点(奇分支奇分支)邻接。邻接。而而G满满足条件

37、足条件(11.4)。|S|O (G S) |S| =NH(S) 。SSXY=S0练一练练一练某工厂生产由六种不同颜色的纱织成的双色布，由这个某工厂生产由六种不同颜色的纱织成的双色布，由这个工厂所生产的双色布中，每一种颜色至少和其它三种颜工厂所生产的双色布中，每一种颜色至少和其它三种颜色搭配。证明：可以挑选出三种不同的双色布，它们含色搭配。证明：可以挑选出三种不同的双色布，它们含有所有的六种颜色。有所有的六种颜色。证明步骤：证明步骤： 建立建立图图G(V,E)：一个点代表一种颜色，两个点相邻当：一个点代表一种颜色，两个点相邻当且仅当这个工厂生产出一种由这两个点所对应的这两且仅当这个工厂生产出一种

38、由这两个点所对应的这两种颜色搭配而成的双色布；种颜色搭配而成的双色布； 由由题意，所得图是题意，所得图是6阶简单图，且每个点的度至少为阶简单图，且每个点的度至少为3； 证明证明这个图有一个这个图有一个完美匹配。完美匹配。 对任意对任意S V(G)，有，有O(GS) | S |11.2 独立集和覆盖独立集和覆盖对比：对比：匹配匹配是图是图G中互相不邻接的边的子集。中互相不邻接的边的子集。边数最多的匹配称为边数最多的匹配称为最大匹配最大匹配，其边数称为其边数称为最大匹配数最大匹配数，记为，记为 (G)。40独立集：独立集：设设S是图是图G的顶点的子集。如果的顶点的子集。如果S中任意中任意两个顶点都

39、不邻接，则称两个顶点都不邻接，则称S是是G的一个点独立集，的一个点独立集，简称简称独立集独立集。最大独立集：最大独立集：若不存在若不存在|S|S|的独立集的独立集S，则称，则称S为为G的的最大独立集。最大独立集。点点独立数：独立数：最大独立集所含的最大独立集所含的顶点数称为点独立顶点数称为点独立数，记为数，记为 (G)。 覆盖覆盖覆盖：覆盖：设设G是图，是图，K V(G)。若若G的每条边都至少的每条边都至少有一个端点在有一个端点在K中，则称中，则称K是是G的一个覆盖。的一个覆盖。最小覆盖：最小覆盖：如果没有覆盖如果没有覆盖K满足满足|K|K|，则称，则称K为最小覆盖。为最小覆盖。点覆盖数：点覆

40、盖数：最小覆盖所包含的顶点数称为点覆盖最小覆盖所包含的顶点数称为点覆盖数，记为数，记为 (G)。41边覆盖边覆盖边覆盖：边覆盖：设设G是一个图，是一个图，L E(G)。如果。如果G的每个的每个顶点都是顶点都是L中某边的端点，则称中某边的端点，则称L为为G的边覆盖。的边覆盖。最小边覆盖：最小边覆盖：如果没有边覆盖如果没有边覆盖L满足满足|L|L|，则称则称L为最小边覆盖。为最小边覆盖。边覆盖数：边覆盖数：最小边覆盖所含最小边覆盖所含边数称为边覆盖数，边数称为边覆盖数，记为记为 (G)。42v1v4v2v3Lmin=v1v2, v3 v4L=v1v3, v1v2, v3 v4 (G)=2并非任何图

41、都存在边覆盖并非任何图都存在边覆盖并非任何图都存在边覆盖，例如包含孤立点的非平并非任何图都存在边覆盖，例如包含孤立点的非平凡图。凡图。43图图G存在边覆盖的充要条件是存在边覆盖的充要条件是 (G)0。独立集和覆盖的例子独立集和覆盖的例子44fdeabc 独立集独立集 a,b,等等含含单个单个顶点顶点的的子集；子集；a,c,d,f是一个是一个最小覆盖；最小覆盖； a,c,b,d,等含有两个不邻接顶等含有两个不邻接顶点的点的子集；且为最大独立集；子集；且为最大独立集； (G) = 2。 覆盖覆盖 a,b,c,d,e是一个覆盖；是一个覆盖； (G) = 4。 匹配匹配 ab,cf,de是一个最大匹配

42、是一个最大匹配; (G) = 3。ab,cf,de是一是一个最小边覆盖个最小边覆盖; (G) = 3。练一练练一练求下图求下图G的点独立数的点独立数 (G)、覆盖数、覆盖数 (G)、最大匹配、最大匹配数数 (G)、边覆盖数、边覆盖数 (G) (G)=3 (G)=4 (G)=3思考：思考：独立集与覆盖都是顶点集的子集，它们之间有什么关系呢？独立集与覆盖都是顶点集的子集，它们之间有什么关系呢？最大匹配与边覆盖都是边集的子集，它们之间又有什么关系最大匹配与边覆盖都是边集的子集，它们之间又有什么关系呢？呢？ (G)=4独立集与点覆盖互补独立集与点覆盖互补定理定理11.2.1 设设S V(G)，于是，于

43、是S是是G的独立集当且仅的独立集当且仅当当V(G) S是是G的一个覆盖。的一个覆盖。证明：证明：S是是G的独立集的独立集 G的每条边的两端点不同时属于的每条边的两端点不同时属于S G的每条边至少有一个端点属于的每条边至少有一个端点属于V(G) S V(G) S是是G的一个覆盖。的一个覆盖。46v1v2v3v4v5点独立集点独立集S=v1,v3V(G)-S 是一个点覆盖是一个点覆盖最大匹配数最大匹配数点覆盖数点覆盖数定理定理11.2.2 对任何图对任何图G均有均有 (G) (G)， 特别，若特别，若G是二分图，是二分图，则则 (G)= (G) 。证明：设证明：设M是是G的任意匹配，的任意匹配，K

44、是是G的任意覆盖。的任意覆盖。K包含包含M中每条边至少一个端点，中每条边至少一个端点，|M|K|。再由再由M和和K的任意性可知：的任意性可知： (G) (G)。 当当G是二分图是二分图 X, Y 时，类似于时，类似于Hall定理的证明，定理的证明，略。略。47点独立数与点覆盖数之和为阶数点独立数与点覆盖数之和为阶数 定理定理11.2.3 设图设图G中有中有p个顶点，则个顶点，则 p = (G) + (G)其中其中 (G)是点独立数，是点独立数， (G)是点覆盖数。是点覆盖数。48证明：设证明：设S是是G的最大独立集，的最大独立集，K是是G的最小覆盖，的最小覆盖，则则V(G)S是是G的覆盖，的覆

45、盖，V(G)K是是G的独立集的独立集(定理定理11.2.1)。因此。因此p (G) = | V(G)S | (G)；p (G) = | V(G)K | (G)。由此两式可得由此两式可得p = (G) + (G)。最大匹配数最大匹配数与与边覆盖数之和为阶数边覆盖数之和为阶数定理定理11.2.4 设设G是无孤立点的是无孤立点的p阶图，则阶图，则 (G) + (G) = p 其中其中 (G)为最大匹配数，为最大匹配数， (G) 为边覆盖数。为边覆盖数。49注意：虽然独立集和覆盖互补，但对于匹配和边覆注意：虽然独立集和覆盖互补，但对于匹配和边覆盖，二者之间却没有类似的结论。盖，二者之间却没有类似的结论

46、。G1 G1的边覆盖的补不是匹配的边覆盖的补不是匹配， G2的匹配的补也不是边覆盖。的匹配的补也不是边覆盖。G2点独立数点独立数 (G) 互不邻接的点集（最大）互不邻接的点集（最大）点覆盖数点覆盖数 (G) 覆盖所有边的点集（最小）覆盖所有边的点集（最小）最大匹配最大匹配数数 (G) 互不邻接的边集（最大）互不邻接的边集（最大）边覆盖数边覆盖数 (G) 覆盖所有点的边集（最小）覆盖所有点的边集（最小）所以，对于没有所以，对于没有孤立点孤立点的的二分图二分图，得到了，得到了最大最大匹配数匹配数，其他三个参数都可以得到。，其他三个参数都可以得到。小结小结设设G是无孤立点的是无孤立点的p阶图，则阶图

47、，则(G)+(G)=p(G)+(G)=p(G)=(G)若若G是无孤立点的二分图，则是无孤立点的二分图，则(G) =(G)最大、最大、最小；没加最小；没加的是点集，加的是点集，加的是边集。的是边集。打猎问题打猎问题猎人猎人要在要在n*n的格子里打的格子里打鸟，鸟，红红格为鸟格为鸟。他可以在。他可以在某一行中打一某一行中打一枪，这样枪，这样此行中的所有鸟都被打掉，此行中的所有鸟都被打掉，也可以在某一列中也可以在某一列中打，这样打，这样此列中的所有鸟都此列中的所有鸟都打掉。打掉。问问至少打几至少打几枪，才能枪，才能打光所有的鸟打光所有的鸟？思考题思考题解题方法（解题方法（1）第一步：建图。第一步：建

48、图。二二分分图图中中X为为每一行，每一行，Y为为每一列，如果每一列，如果(i,j)有一只鸟，那么连接有一只鸟，那么连接X中的中的i与与Y中的中的j。x1x2x3x4x5 y1 y2 y3 y4 y5y1 y2 y3 y4 y5 x1 x2 x3 x4 x5解题方法（解题方法（2）第二步：分析。第二步：分析。每一条边为一只鸟，每一个顶点为打一枪；每一条边为一只鸟，每一个顶点为打一枪；求打光所有鸟的最少枪数，即求覆盖所有边的最小点求打光所有鸟的最少枪数，即求覆盖所有边的最小点集，即求点覆盖数集，即求点覆盖数(G) ；二二分分图的图的(G)=(G)，即求最大匹配数，即求最大匹配数(G)。y1 y2

49、y3 y4 y5 x1 x2 x3 x4 x5解题方法（解题方法（3）第三步：求最大匹配数第三步：求最大匹配数(G) 。还还记得方法吗？记得方法吗？破破M-可增广路可增广路 法。法。y1 y2 y3 y4 y5 x1 x2 x3 x4 x5M=x1y2,x2y3,x3y5 =y1x2 y3x4M=x1y2,x2y1,x3y5, x4y3无M-可增广路，求得最大匹配(G)=4解题方法（解题方法（4）第四步：求得原问题的解。第四步：求得原问题的解。最少开最少开4枪可将所有鸟打中。枪可将所有鸟打中。x1x2x3x4x5 y1 y2 y3 y4 y511.4 应用应用人员分配问题人员分配问题设某单位有

50、设某单位有n名工作人员名工作人员x1 , , xn 和和n项工作项工作y1, , yn，已知每个工作人员可以至少胜任一项工作，每，已知每个工作人员可以至少胜任一项工作，每项工作都至少有一人能胜任，但不是每人都能胜任项工作都至少有一人能胜任，但不是每人都能胜任各项工作。能否给出一个工作安排，使每人恰好分各项工作。能否给出一个工作安排，使每人恰好分配到一项他所胜任的工作。配到一项他所胜任的工作。建图：建图：令令X=x1, , xn，Y=y1, , yn。令二分图。令二分图G为为 ，规定，规定xi与与yj邻接当且仅当工作人员邻接当且仅当工作人员xi胜胜任工作任工作yj，1i, jn。分析：分析：人员

51、分配问题便抽象为求二分图人员分配问题便抽象为求二分图G的一个完的一个完美匹配。美匹配。57匈牙利匈牙利算法算法1965年，匈牙利著名数学家年，匈牙利著名数学家Edmonds设计了一种设计了一种求完美求完美匹配（最大匹配）的匹配（最大匹配）的算法，称为算法，称为匈牙利匈牙利算法。算法。基本思想基本思想：从一个初始匹配：从一个初始匹配M开始（可以是一条边），开始（可以是一条边），系统地寻找系统地寻找M的可增广路的可增广路P，然后扩展为更大的匹配，然后扩展为更大的匹配M=P M，直至不存在可增广路。，直至不存在可增广路。方法方法：从从一个不饱和一个不饱和结点结点u开始，开始，寻找一条寻找一条M-可可

52、增广路增广路P：构造一棵以构造一棵以u为根的交错树，即根出发的道路是为根的交错树，即根出发的道路是M交错路交错路 (i) 如果如果叶结点均为饱和的，换另一个不饱和结点；叶结点均为饱和的，换另一个不饱和结点；(ii)如果如果某个叶是不饱和的某个叶是不饱和的 ，则有可增广路，则有可增广路P, 置置M=P M;重复上述过程，直至尝试过所有不饱和结点。重复上述过程，直至尝试过所有不饱和结点。匈牙利算法匈牙利算法步骤步骤初始化：任取一个初始匹配初始化：任取一个初始匹配M( (可以是一条边可以是一条边) )。若若M饱和饱和X的所有顶点，则算法终止；的所有顶点，则算法终止； 否则设否则设u是是X的非的非M饱

53、和点，令饱和点，令S=u，T=。若若NG(S)=T，则，则|NG(S)|n) q=false; /若若X全部饱和则终止全部饱和则终止 else /u为起点寻找交错路为起点寻找交错路 p=Mixed-Route(u); /有交错路时有交错路时p为真为真 if (p) NewMatch( ); /有交错路就更新匹配有交错路就更新匹配 else q= false; /无完美匹配而终止无完美匹配而终止 /注：程序中只给出注：程序中只给出终止终止处而省略了其输出处而省略了其输出66初始匹配初始匹配InitialMatch( ) /产生初始匹配产生初始匹配 for(i=1;i=n;i+) Xi=Yi=0；

54、 /将将X和和Y置零置零 for(i=1;i=n;i+) q = true; j=1； while(q&j=n) /Yj=0表示表示yj尚未匹配尚未匹配 if (Wi, j=1&Yj=0) Xi=j; Yj=i; q=false else j=j+1; /依据依据W取出若干不相邻接的边取出若干不相邻接的边 67更新匹配更新匹配RenewMatch( ) /用用M可增广路更新匹配的子可增广路更新匹配的子过程过程 for (j=1;j=|Y|;j+) XPj, 1 = Pj, 2; /修改修改xi的匹配的匹配 YPj, 2 = Pj, 1; /同步修改同步修改Y 68两个检测子程序

55、两个检测子程序Check(X) /检查检查X中是否有未饱和顶点中是否有未饱和顶点 q=true; i=1; while(q&i=n) if (Xi=0) q=false; else i=i+1; return(i)； /若若X中无未饱和顶点返回中无未饱和顶点返回n+1， /否则否则给出未饱和顶点给出未饱和顶点xi的位置的位置i。NS(u) /比较比较|NG(S)|和和|S|的大小的大小 Su=1; s=0; for(i=1;i=n;i+) s=s+Si;/计算计算|S| for(i=1;i=n;i+) if (Wu, i=1) Ni=1;/扩展扩展N g:=0; for(i=1;i=n;i+)