支配集、覆盖集、独立集与匹配

1、信息学院信息技术教研室VsVtV2V4V3V12484279146V1V8V9V10V7V4V3V6V5V2王桂平王桂平第第7 7章支配集、覆盖集、独立集与匹配章支配集、覆盖集、独立集与匹配2本讲内容会涉及以下容易相互混淆的内容：1.点支配集, 极小点支配集, 最小点支配集, ;v 支配的概念；2.点独立集, 极大点独立集, 最大点独立集, ;3.点覆盖集, 极小点覆盖集, 最小点覆盖集, ;v 覆盖的概念；4.边覆盖集, 极小边覆盖集, 最小边覆盖集, ;5.边独立集(匹配), 极大边独立集(极大匹配), 最大边独立集(最大匹配), ;以上几个量存在以下关系：3对二部图，还有以下关系式：二部

2、图的最小点覆盖数等于最大匹配数二部图的最大点独立数顶点个数 最大匹配数47.1 点支配集、点覆盖集、点独立集(都是顶点的集合)定义定义7.1 设图设图G = , V* V, 若对于若对于 vi V - V*, vj V*, 使得使得: (vi, vj) E, 则称则称vjvi, 并称并称V*为为G的一个的一个;若支配集若支配集V*的任何真子集都不是支配集的任何真子集都不是支配集, 则称则称V*是是;顶点数最少的支配集称为顶点数最少的支配集称为;最小支配集中的顶点数称为最小支配集中的顶点数称为, 记作记作或简记为或简记为 。图图(a)中，中，V*= v1, v5 就是一个支配集。因为就是一个支配

3、集。因为V-V*=v2, v3, v4, v6, v7中的顶点都是中的顶点都是V*中顶点中顶点的邻接顶点。的邻接顶点。5在图在图(a)中中, v1, v5 , v3, v5 和和 v2, v4, v7 都是都是, v1, v5 , v4, v5 和和 v3, v6 都是都是, 。图图(b)为为7阶星形图阶星形图, v0 , v1, v2, ., v6 为为, v0 为为, 。图图(c)为轮图为轮图W6, v0 , v1, v3 , v1, v4 等都是等都是, 显然显然, 。6支配集的性质支配集的性质1.若若G中无孤立顶点中无孤立顶点(度数为度数为0的顶点的顶点)，则，则一个支配集一个支配集V

4、*，使得，使得G中除中除V*外的所有顶点也组成一个支配集外的所有顶点也组成一个支配集(即即V - V*也是一个支配集也是一个支配集)。2.若若G中无孤立顶点中无孤立顶点(度数为度数为0的顶点的顶点)，V1*为为支配集，则支配集，则G中除中除V1*外的所有顶点外的所有顶点组成一个支配集组成一个支配集(即即V V1*也是一也是一个支配集个支配集)。(证明略证明略)在图在图(a)中，取中，取V* v3, v5 , v6 , v7 ， V*是支配集，是支配集，但但V - V*是否是支配集？是否是支配集？7极小支配集的求解参见吴文虎编著的信息学奥林匹克竞赛指导图论的算法与程序设计(PASCAL版)P54

5、8 设图设图G = , V* V, 若若, 则称则称V*为为G的的, 或称或称;若在若在V*中加入任何顶点都不再是独立集中加入任何顶点都不再是独立集, 则称则称V*为为;顶点数最多的点独立集称为顶点数最多的点独立集称为;最大点独立集的顶点数称为最大点独立集的顶点数称为, 记作记作, 简记为简记为。定义定义7.2 图图(a)中，中，V*= v1, v5 就是一个点独立集，因就是一个点独立集，因为为v1和和v5是不相邻的是不相邻的9图图(a)中中, v1, v5 , v3, v6 , v2, v4, v7 等都是极大点等都是极大点独立集独立集, 其其 v2, v4, v7 等为最大点独立集等为最大

6、点独立集, 0 = 3;图图(b)中中, v0 , v1, v2, , v6 都是极大点独立集都是极大点独立集, 其其 v1, v2, , v6 是最大点独立集是最大点独立集, 0 = 6;图图(c)中中, v1, v3 , v1, v4 是极大点独立集是极大点独立集, 也都是最也都是最大点独立集大点独立集, 02。10 设设G = , V* V, 若对于若对于 e E, v V*, 使使得得: v与与e相关联相关联, 则称则称ve, 并称并称V*为为G的的或简称或简称;若点覆盖若点覆盖V*的任何真子集都不是点覆盖的任何真子集都不是点覆盖, 则称则称V*是是;顶点个数最少的点覆盖称为顶点个数最

7、少的点覆盖称为;最小点覆盖的顶点数称为最小点覆盖的顶点数称为, 记作记作, 简记为简记为。定义定义7.3 图图(a)中，中，V*= v1, v3, v5, v7 就是一个点覆盖就是一个点覆盖集集11图图(a)中中, v2, v3, v4, v6, v7 , v1, v3, v5, v7 等都是极小等都是极小点覆盖点覆盖, v1, v3, v5, v7 是最小点覆盖是最小点覆盖, 0 = 4;图图(b)中中, v0 , v1, v2, , v6 都是极小点覆盖都是极小点覆盖, v0 是最小点覆盖是最小点覆盖, 0 = 1;图图(c)中中, v0, v1, v3, v4 , v0, v1, v3,

8、 v5 都是极小点覆都是极小点覆盖盖, 也都是最小的点覆盖也都是最小的点覆盖, 0 = 4。12点支配集、点独立集、点覆盖集之间的联系1)定理定理7.1：设设G = 中中，则，则G的的。逆命题不成立。逆命题不成立(即极小支配集未即极小支配集未必是极大独立集必是极大独立集)。2)一个独立集是极大独立集，当且仅当它是一个支配集。一个独立集是极大独立集，当且仅当它是一个支配集。3)定理定理7.2：设设G = 中无孤立点中无孤立点, V*(V* V)为为G的的, 当且仅当当且仅当。v 推论推论：设：设G是是n阶无孤立点的图，则阶无孤立点的图，则V*是是G的极小的极小(最小最小)点覆盖，当且仅当点覆盖，

9、当且仅当V-V*是是G的极大的极大(最大最大)点点独立集，从而有独立集，从而有 0 + 0 = n(顶点个数顶点个数)。13 设设G = 中中, 则则G的的。假设假设: V*是是G中的任意一个极大独立集。中的任意一个极大独立集。 v V - V*, 一定有一定有: v V*, 使得使得: (v, v) E。假设假设: u V-V*不与不与V*中任何顶点相邻中任何顶点相邻, 则则V* u 就是就是一个更大的独立集一个更大的独立集, 这与这与V*是极大独立集相矛盾。是极大独立集相矛盾。所以所以, V*是是G的支配集。的支配集。由由“V*是点独立集是点独立集”可知可知: V1* V*, V* - V

10、1*中的顶点中的顶点都不受都不受V1*中的顶点支配中的顶点支配, 即即: V1*不是支配集。不是支配集。所以所以, V*是极小支配集。是极小支配集。证：证：上面定理的上面定理的的。在右图中的。在右图中, v3, v5 是极小支配集是极小支配集, 但它不是独立集但它不是独立集, 更不更不是极大独立集。是极大独立集。定理定理7.114 设设G = 中无孤立点中无孤立点, V*(V* V)为为G的的, 当且仅当当且仅当。证：证：1) 必要性必要性假设假设: 存在存在vi, vj V - V*, 且且(vi, vj) E。由于顶点由于顶点vi和和vj都不在都不在V*中中, 这显然与这显然与“V*是点覆

11、盖是点覆盖”相相矛盾。矛盾。所以所以, V - V*为点独立集。为点独立集。 2) 充分性充分性假设假设: V - V*是点独立集。是点独立集。因此因此, 任意一条边的两个端点至少有一个在任意一条边的两个端点至少有一个在V*中。中。由定义可知由定义可知: V*是是G的点覆盖。的点覆盖。推论推论 设设G是是n阶无孤立点的图阶无孤立点的图, 则则V*是是G的极小的极小(最小最小)点覆点覆盖盖, 当且仅当当且仅当V-V*是是G的极大的极大(最大最大)点独立集点独立集, 从而有从而有 0 + 0 = n(顶点个数顶点个数)。定理定理7.215极大点独立集与极小点覆盖集的求解参见吴文虎编著的信息学奥林匹

12、克竞赛指导图论的算法与程序设计(PASCAL版)P58167.2 边覆盖集与匹配(都是边的集合)定义定义7.4 设图设图G = , E* E, 若若 v V, e E*, 使得使得: v与与e相关联相关联, 则称则称ev, 并称并称E*为为, 或简称或简称;若边覆盖若边覆盖E*的任何真子集都不是边覆盖的任何真子集都不是边覆盖, 则称则称E*是是;边数最少的边覆盖集称为边数最少的边覆盖集称为;最小的边覆盖所含的边数称为最小的边覆盖所含的边数称为, 记作记作或简记为或简记为。图图(a)中，中，E*= e1, e4, e7 就是一个边覆盖集就是一个边覆盖集17图图(a)中中, e1, e4, e7

13、和和 e2, e5, e6, e7 都是极小边覆盖都是极小边覆盖, e1, e4, e7 是最小边覆盖是最小边覆盖, 1 = 3。图图(b)中中, e1, e3, e6 和和 e2, e4, e8 都是极小边覆盖都是极小边覆盖, 也也都是最小边覆盖都是最小边覆盖, 1 = 3。18 设设G = , 若若E*(E* E)中任何两条边均不相邻中任何两条边均不相邻, 则称则称E*为为G中中, 也称也称E*为为G中的中的(MatchingMatching);若在若在E*中加入任意一条边所得集合都不是匹配中加入任意一条边所得集合都不是匹配, 则称则称E*为为;边数最多的匹配称为边数最多的匹配称为;最大匹

14、配的边数称为最大匹配的边数称为或或, 记作记作, 简记为简记为。定义定义7.5 图图(a)中，中，E*= e1, e4, e7 就是一个匹配就是一个匹配19图图(a)中中, e2, e6 , e3, e5 , e1, e4, e7 都是极大匹配都是极大匹配, e1, e4, e7 是最大匹配是最大匹配, 1 = 3。图图(b)中中, e1, e3 , e2, e4 , e4, e7 都是极大匹配都是极大匹配, 也也都是最大匹配都是最大匹配, 1 = 2。20例：飞行员搭配问题例：飞行员搭配问题1 1最大匹配问题最大匹配问题 飞行大队有若干个来自各地的飞行员，专门驾驶一种型号的飞飞行大队有若干个

15、来自各地的飞行员，专门驾驶一种型号的飞机，这种飞机每架有两个飞行员。由于种种原因，例如互相配机，这种飞机每架有两个飞行员。由于种种原因，例如互相配合的问题，有些飞行员不能在同一架飞机上飞行，问如何搭配合的问题，有些飞行员不能在同一架飞机上飞行，问如何搭配飞行员，才能使飞行员，才能使。 为简单起见，设有为简单起见，设有1010个飞行员，图个飞行员，图(a)(a)中的中的V V1 1,V,V2 2, ,V V1010就代表这就代表这1010个飞行员。如果个飞行员。如果，否则就不连。，否则就不连。V9V3V1V2V4V5V7V6V8V10(a) 图图(a)(a)中的中的3 3条蓝色的粗线代表条蓝色的

16、粗线代表一种搭配方案。由于一个飞行一种搭配方案。由于一个飞行员不能同时派往两架飞机，因员不能同时派往两架飞机，因此此。称一个图中没有公共端点。称一个图中没有公共端点的一组边成为一个的一组边成为一个“”。因此上述问题就转化为：因此上述问题就转化为：，这，这个问题叫图的个问题叫图的。21例：飞行员搭配问题例：飞行员搭配问题2 2二部图的最大匹配问题二部图的最大匹配问题在例在例1 1中，如果飞行员分成两部分，一部分是正驾驶员，一中，如果飞行员分成两部分，一部分是正驾驶员，一部分是副驾驶员。如何搭配正副驾驶员才能使得出航飞机部分是副驾驶员。如何搭配正副驾驶员才能使得出航飞机最多的问题可以归结为一个二部

17、图上的最大匹配问题。最多的问题可以归结为一个二部图上的最大匹配问题。例如，假设有例如，假设有4 4个正驾驶员，有个正驾驶员，有5 5个副驾驶员，飞机必须要个副驾驶员，飞机必须要有一名正驾驶员和一名副驾驶员才能起飞。正驾驶员和副有一名正驾驶员和一名副驾驶员才能起飞。正驾驶员和副驾驶员之间存在搭配的问题。驾驶员之间存在搭配的问题。Y1Y2Y3Y4Y5X1X2X3X4(b)图图(b)中，中，X1,X2,X3,X4表示表示4个个正驾驶员，正驾驶员，Y1,Y2,Y3,Y4,Y5表示表示5个副驾驶员。正驾驶员之间个副驾驶员。正驾驶员之间不能搭配，副驾驶员之间也不不能搭配，副驾驶员之间也不能搭配，所以这是一

18、个能搭配，所以这是一个。图图(b)中的中的4条蓝色的粗线代表条蓝色的粗线代表一种搭配方案。这个问题实际一种搭配方案。这个问题实际上是求一个二部图的上是求一个二部图的。22定义定义7.6 ：如果图：如果图G是一个简单图，它的顶点集合是一个简单图，它的顶点集合V是由两个没是由两个没有公共元素的子集有公共元素的子集X=X1,X2,.,Xm与子集与子集Y=Y1,Y2,Yn，并，并且且Xi与与Xj(1i,jm)之间，之间，Ys与与Yt(1s,tm)之间没有边连接，之间没有边连接，则则G称为称为。23 对于一个图对于一个图G与给定的一个匹配与给定的一个匹配M，如果图，如果图G中不存在中不存在M的未的未盖点

19、盖点(未盖点的定义见未盖点的定义见7.3节节)，则称匹配，则称匹配M为图为图G的的。图图(a)中中, M = e1, e4, e7 为完美匹配为完美匹配(最大匹配最大匹配), 它也是最小边覆盖。它也是最小边覆盖。图图(b)中不可能有完美匹配中不可能有完美匹配, 因此因此, 对对任何匹配都存在未盖点。任何匹配都存在未盖点。定义定义7.6 24任取一个最大匹配任取一个最大匹配, 比如比如: M = e2, e4 , 则则M e6 , M e8 , M e7 都都是图的最小边覆盖。是图的最小边覆盖。任取一个最小边覆盖任取一个最小边覆盖, 比如比如: W = e1, e3, e6 , 从中移去一条相邻

20、的边从中移去一条相邻的边, 则则 e1, e3 和和 e1, e6 都是图的最大匹配。都是图的最大匹配。我们通常这样来做我们通常这样来做: 用最大匹配通过增加关联未盖点的边获得最小边覆盖用最大匹配通过增加关联未盖点的边获得最小边覆盖;用最小边覆盖通过移去相邻的一条边获得最大匹配。用最小边覆盖通过移去相邻的一条边获得最大匹配。(详见定理详见定理7.3)25定理定理7.3 设设n阶图阶图G中无孤立点。中无孤立点。(1) 设设M为为G的一个最大匹配的一个最大匹配, 对于对于G中每个中每个M的未盖点的未盖点v, 由与由与v关联关联的边所组成的边集的边所组成的边集N, 则则W = MN为为G中最小边覆盖

21、中最小边覆盖;(2) 设设W1为为G的最小边覆盖的最小边覆盖, 若若G中存在相邻的边就移去其中的一条中存在相邻的边就移去其中的一条, 设移去的边集为设移去的边集为N1, 则则M1 = W1 - N1为为G中一个最大匹配中一个最大匹配;(3) G中边覆盖数中边覆盖数 1与匹配数与匹配数 1, 满足满足: 1+ 1 = n。由由“M为最大匹配为最大匹配”可知可知: |M| = 1。显然显然, G中含有中含有n-2 1个个M的未盖点。的未盖点。由由“边覆盖的定义边覆盖的定义”可知可知: W = MN为为G中的边覆盖中的边覆盖, 且且|W| = |M|+|N| = 1 + n - 2 1 = n -

22、1由由“W1是最小边覆盖是最小边覆盖”可知可知: W1中每条边的两个端点不可能都与中每条边的两个端点不可能都与W1中的其它边相中的其它边相关联关联, 因此因此, 在由在由W1构造构造M1时时, 每移去相邻两条边中的一条时每移去相邻两条边中的一条时, 将只产生一个将只产生一个M的未盖点的未盖点。所以所以, |N1| = |W1| - |M1| = M1的未盖点数的未盖点数 = n - 2|M1|。整理后整理后, 得得: |W1| = 1 = n - |M1|。又又M1是匹配是匹配, W是边覆盖是边覆盖, 所以所以, |M1| 1, |W| 1。通过比较可得通过比较可得: 1 = n-|M1| n

23、 - 1 = |W| 1。显然上式中各等号成立显然上式中各等号成立, 所以所以, |M1| = 1, |W| = 1, 且且 1+ 1 = n。由此可知由此可知: M1是最大匹配是最大匹配, W是最小边覆盖是最小边覆盖, 且结论且结论(3)成立。成立。证：证：26由定理由定理7.3中的中的(1)可知可知: 1 1。由定义可知由定义可知: |M| 1 1 |W|。所以所以, |M| |W|成立。成立。当等号成立时当等号成立时, 说明说明: M是最大匹配是最大匹配, W是最小边覆盖是最小边覆盖。由定理由定理7.3中中(3)可知可知: 1 + 1 = 2 1 = n。显然显然, G中无中无M的未盖点

24、。的未盖点。所以所以, M必为必为G中完美匹配。中完美匹配。推论推论 设设G是是n阶无孤立点的图阶无孤立点的图, M为为G中的匹配中的匹配, W是是G中中的边覆盖的边覆盖, 则则|M| |W|; (|M|表示表示M中边的数目中边的数目)当等号成立时当等号成立时, M为为G中完美匹配中完美匹配, W为为G中最小边覆中最小边覆盖。盖。证：证：27右图右图(a)中的中的 e1, e4, e7 为完美匹配为完美匹配, 也是最小边覆盖。也是最小边覆盖。在下图在下图(a)中中, M1 = e3, e7 和和M2 = e2, e4, e6 都是其极大匹配。都是其极大匹配。下图下图(b)和和(c)中实线边所示

25、。中实线边所示。M1不是不是最大匹配最大匹配, M2是最大匹配是最大匹配(也是完美匹配也是完美匹配)。 = e2e3e4e7e6是关于是关于M1的可增广路径。的可增广路径。M2没有可增广没有可增广路径。路径。287.3 匹配问题的求解为了求解各种匹配问题，必须引入一系列概念：为了求解各种匹配问题，必须引入一系列概念：V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a) 设设Vi是图是图G = 的一个顶点，的一个顶点，M是图是图G中一个给定的中一个给定的匹配，如果匹配，如果Vi不与任意一条属于匹配不与任意一条属于匹配M的边相关联，则称

26、的边相关联，则称Vi是匹配是匹配M的的。很形象：没有被匹配。很形象：没有被匹配M中的边中的边“盖盖住住”。取定取定M=e4, e6, e10(由粗线组由粗线组成的匹配成的匹配)，则图，则图(a)中，中，V10就就是是M的一个未盖点。的一个未盖点。29V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a) 设设P是图是图G的一条轨的一条轨(路径路径)，如果，如果P的任意两条相邻的边一定是的任意两条相邻的边一定是一条属于匹配一条属于匹配M而另一条不属于而另一条不属于M，则称，则称P是一条是一条。在图在图(a)中，取定中，取定M=e4, e

27、6, e10(由粗线组成的匹配由粗线组成的匹配)，则图，则图(b)、(c)所示的路径都是交错轨。所示的路径都是交错轨。特别地，如果轨特别地，如果轨P仅含一条边，那么无论这条边是否属于匹配仅含一条边，那么无论这条边是否属于匹配M，P一定是一条交错轨。一定是一条交错轨。V1V5V9V11V6V2e1e4e7e10e12(b)V9V6V7V3V4e3e6e8e10(c)30V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a) 两个端点都是未盖点的两个端点都是未盖点的称为称为。图图(b)所示的交错轨的两个端点所示的交错轨的两个端点V2, V

28、11都是匹配都是匹配M的未盖点，的未盖点，所以这条轨是可增广轨，而图所以这条轨是可增广轨，而图(c)所示的交错轨不是可增广轨所示的交错轨不是可增广轨。特别地，如果两个未盖点之间仅含一条边，那么单单这条边特别地，如果两个未盖点之间仅含一条边，那么单单这条边也组成一条可增广轨。也组成一条可增广轨。V1V5V9V11V6V2e1e4e7e10e12(b)V9V6V7V3V4e3e6e8e10(c)31V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a)V1V5V9V11V6V2e1e4e7e10e12(b)V1V5V10V9V11V6V7

29、V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(d) 对于图对于图G的一个匹配的一个匹配M来说，如果能找到一条来说，如果能找到一条P，那，那么这个匹配么这个匹配M一定可以通过下述方法改进成一个包含多一条边一定可以通过下述方法改进成一个包含多一条边的匹配的匹配Ms(即匹配即匹配M扩充了扩充了)：如图如图(a)中图中图G的一个匹配的一个匹配M，找到图，找到图(b)所示的一条可增广轨所示的一条可增广轨，那么得到图，那么得到图(d)所示的新匹配所示的新匹配Ms。Ms比比M多一条边。多一条边。32证：证：1) 必要性必要性假设假设: M为为G中最大匹配。中最大匹配。若若G中

30、存在中存在M的可增广路径的可增广路径 , 则则 中在中在M中的边比不中的边比不在在M中的少中的少1。设设M = (M (E) - (M (E) = M(E), 则则M中边中边彼此不邻彼此不邻, 且且M比比M多一条边多一条边, 即即: M是比是比M多一条边的多一条边的匹配匹配, 这就与这就与“M是最大匹配是最大匹配”相矛盾。相矛盾。所以所以, M不含可增广路径。不含可增广路径。定理定理7.4 M为为G的最大匹配的最大匹配, 当且仅当当且仅当G不含不含M可增广路径。可增广路径。332) 充分性充分性设设: M是是G中不含可增广路径的匹配中不含可增广路径的匹配, M1是是G中的最大匹配。中的最大匹配

31、。下面证明下面证明: |M| = |M1|。设设: H = GM1 M。当当H = 时时显然显然, M = M1, 所以所以, M为为G中最大匹配。中最大匹配。若若H 时时由于由于M和和M1都是匹配都是匹配, 所以所以, H各连通分支要么是由各连通分支要么是由M和和M1中的边组成的交错圈中的边组成的交错圈, 在交错圈上在交错圈上M和和M1中的边数相等中的边数相等, 要么为要么为由由M和和M1的边组成的交错路径。的边组成的交错路径。由已知条件可知由已知条件可知: M不含可增广路径不含可增广路径, M1是最大匹配。由必是最大匹配。由必要性可知要性可知: M1中也无可增广的交错路径。中也无可增广的交

32、错路径。所以所以, 在由在由M和和M1组成的交错路径上组成的交错路径上, M和和M1的边也相等的边也相等, 即即: M与与M1边的个数相同。边的个数相同。因此因此, M为最大匹配。为最大匹配。34求最大匹配的可行方法：给定一个初始匹配给定一个初始匹配M(如果没有给定，则如果没有给定，则M)，如果图，如果图G没有未盖点，则肯定不会有可增广轨了，即没有未盖点，则肯定不会有可增广轨了，即M就是最大匹就是最大匹配。配。对图对图G的所有未盖点的所有未盖点Vi，通过，通过搜索以搜索以Vi为端点的为端点的可增广轨，从而通过可增广轨逐渐把可增广轨，从而通过可增广轨逐渐把M扩大。扩大。(在扩大在扩大M的的过程当

33、中，某些未盖点会逐渐被过程当中，某些未盖点会逐渐被M盖住盖住)35寻找可增广轨的方法 设设M是图是图G的一个匹配，的一个匹配，Vi是取定的未盖点，如果存在从是取定的未盖点，如果存在从Vi到到Vj的交错轨，则称的交错轨，则称。以图以图(d)为例，如果取定了未盖点为例，如果取定了未盖点V4，那么存在着交错轨那么存在着交错轨P=V4, V3, V7, V6，因此，因此，同样，同样V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(d)寻找以寻找以Vi为端点的可增广轨的方法：设法把由为端点的可增广轨的方法：设法把由Vi交错可达的顶点都找出交错可

34、达的顶点都找出来，每找到一个，就检查一下它是不是未盖点，如果是，则可增广轨就来，每找到一个，就检查一下它是不是未盖点，如果是，则可增广轨就找到了。如果已经把所有由找到了。如果已经把所有由Vi交错可达的顶点都找出来了，而其中没有交错可达的顶点都找出来了，而其中没有一个是未盖点，就可以肯定以一个是未盖点，就可以肯定以Vi为一端的可增广轨一定不存在了。为一端的可增广轨一定不存在了。36为了把由为了把由Vi交错可达的顶点都找出来，需要引入交错树的概念交错可达的顶点都找出来，需要引入交错树的概念 设设M是图是图G=V,E的一个取定的匹配，的一个取定的匹配，T是图是图G的一个子图，如的一个子图，如果果T具

35、有下述性质：具有下述性质： (1) T是一棵树；是一棵树； (2) T中存在一个顶点中存在一个顶点Vi，它是未盖点；，它是未盖点； (3) 对于对于T的任意一个不同于的任意一个不同于Vi的顶点来说，的顶点来说，T中连接中连接Vi与与Vj的的唯一轨是交错轨。唯一轨是交错轨。 那么称那么称T是一个以是一个以Vi为根的为根的。V15V6V5V4V3V2V1V12V13V14V11V8V7V9V10(a)V5V4V3V2V1V8V7(b) T+图图(a)中粗边代表一个匹中粗边代表一个匹配。图配。图(b)所示的子图就所示的子图就是一个以是一个以V1为根的交错为根的交错树。树。37为了描述如何扩大一个交错

36、树，需要介绍有关顶点分类的概念为了描述如何扩大一个交错树，需要介绍有关顶点分类的概念 交错树交错树T的顶点可以分成两类：的顶点可以分成两类： 外点：即图外点：即图(b)中标中标+号的顶点，如果号的顶点，如果Vj是外点，则连接根是外点，则连接根Vi与与Vj的交错轨一定的交错轨一定，且，且P上与上与Vj关联的边一定关联的边一定。 内点：即图内点：即图(b)中标中标号的顶点，如果号的顶点，如果Vj是内点，则连接根是内点，则连接根Vi与与Vj的交错轨一定的交错轨一定，且，且P上与上与Vj关联的边一定关联的边一定。V5V4V3V2V1V8V7(b) T+图图(b)中中V1、V3、V5、V7为外为外点，而

37、点，而V2、V4、V8为内点。为内点。38扩大以Vi为根的交错树的方法看看图看看图G中有没有与交错树中有没有与交错树T的外点关联而不属于的外点关联而不属于T的边的边e，如果，如果有，就看看有，就看看e的另一个端点的另一个端点Vk是不是属于是不是属于T(肯定不属于肯定不属于T)，如果，如果Vk不属于不属于T，那么就可以把，那么就可以把e和和Vk都加入到都加入到T中，使中，使T扩大。在扩扩大。在扩大的时候，还可以分为两种情况：大的时候，还可以分为两种情况：Vk是未盖点，这时，把是未盖点，这时，把e与与Vk加入到加入到T中后，中后，T中连接根中连接根Vi与与Vk的交错路的交错路是一条可增广轨。是一条

38、可增广轨。(见下图见下图(a)Vk不是未盖点，也就是说，有一条属于匹配不是未盖点，也就是说，有一条属于匹配M的边的边 与与Vk关联，这时，关联，这时，在把在把e与与Vk加入到加入到T中后，还可以把中后，还可以把 以及它的端点以及它的端点Vm加入到加入到T中去中去，因为很显然从，因为很显然从Vi也交错可达也交错可达 的另一端点的另一端点Vm。另外，。另外，Vk应该是内应该是内点，而点，而Vm是外点。是外点。(见下图见下图(b)(b)Vi+Vje+VkVmeVi+未盖点未盖点Vje(a)Vk39V1(a)+(e)V5V4V3V2V1V8V7+V15V6+eeV3V2V1(b)+eeV5V4V3V2

39、V1V8V7(d)+eeV5V4V3V2V1(c)+ee下面图下面图(a)、(b)、(c)、(d)、(e)给出了从给出了从V1出发扩展交错树的具体过程。出发扩展交错树的具体过程。对于图对于图(e)所示的交错树，不能再用上述方法扩大了，因为找不到一条所示的交错树，不能再用上述方法扩大了，因为找不到一条不属于不属于T的边的边e，这条边与，这条边与T的某个外点关联，且的某个外点关联，且e的另一个端点的另一个端点Vk也不也不属于属于T。但能不能就此断定以但能不能就此断定以V1为一端的可增广轨一定不存在呢？答案是否定为一端的可增广轨一定不存在呢？答案是否定的的(见下页见下页)。40V15V6V5V4V3

40、V2V1V12V13V14V11V8V7V9V10(f)对于图对于图(e)中的交错树，已经无法扩大了，但中的交错树，已经无法扩大了，但以以V1为一端的可增广轨是存在的。在图为一端的可增广轨是存在的。在图(f)中中用虚线标出的用虚线标出的(V1,V2,V3,V4,V5,V7,V8,V9)就是就是一条连接一条连接V1和和V9的可增广轨。的可增广轨。(e)V5V4V3V2V1V8V7+V15V6+ee41 如果发现了一条不属于交错树如果发现了一条不属于交错树T的边的边e，e的两个端点都是的两个端点都是T的外的外点，那么把点，那么把e加到加到T中去得到的图叫做中去得到的图叫做。(e)V5V4V3V2V

41、1V8V7+V15V6+ee例如在图例如在图(e)中，连接中，连接T的两个顶点的两个顶点V5与与V7的这条的这条边边e(图中的红边图中的红边)原不属于原不属于T，现在把，现在把e加到加到T中去中去，只不过是使，只不过是使T增加了一条边，没有扩大由增加了一条边，没有扩大由Vi交交错可达的顶点的范围，反而使得错可达的顶点的范围，反而使得T不再是树了。不再是树了。带花树的特点是，它恰好有一个圈，这唯一的圈带花树的特点是，它恰好有一个圈，这唯一的圈称为带花树的花。圈内包含奇数条边。称为带花树的花。圈内包含奇数条边。带花树的作用见带花树的作用见“7.3.4 任意图的最大匹配任意图的最大匹配”42匹配问题

42、匹配问题可以分为如下类型：匹配问题可以分为如下类型：1.二部图的最大匹配；二部图的最大匹配；2.二部图的完备匹配；二部图的完备匹配；3.二部图的最佳匹配；二部图的最佳匹配；4.任意图的最大匹配；任意图的最大匹配；每种匹配问题的解法不一样，难度也不一样。每种匹配问题的解法不一样，难度也不一样。437.3.1 二分图的最大匹配求二部图的最大匹配的算法有：求二部图的最大匹配的算法有：1.网络流解法网络流解法2.匈牙利算法匈牙利算法3.Hopcroft-Karp算法算法(匈牙利算法的改进匈牙利算法的改进)441 网络流解法1)从二部图从二部图G出发构造一个网络出发构造一个网络G：a)增加一个源点增加一

43、个源点S和汇点和汇点T；b)从从S向向X的每一个顶点都画一条有向弧，从的每一个顶点都画一条有向弧，从Y的每一个顶点的每一个顶点都向都向T画一条有向弧；画一条有向弧；c)原来原来G中的边都改成有向弧，方向是从中的边都改成有向弧，方向是从X的顶点指向的顶点指向Y的顶的顶点；点；d)令所有弧的容量都等于令所有弧的容量都等于1。2)求网络求网络G的最大流的最大流F。3)从从X的顶点指向的顶点指向Y的顶点的弧集合中，弧流量为的顶点的弧集合中，弧流量为1的弧对应二部图的的弧对应二部图的匹配边，最大流值匹配边，最大流值F对应二部图的最大匹配的边数。对应二部图的最大匹配的边数。为什么这样构造的网络求出来的最为

44、什么这样构造的网络求出来的最大流就是最大匹配？大流就是最大匹配？(1) 网络中所有的弧容量均为网络中所有的弧容量均为1。(2) 尽管在网络中顶点尽管在网络中顶点Xi可能发出多条边，但可能发出多条边，但在最大流中只能选择一条边；在最大流中只能选择一条边；(3) 尽管在网络中可能有多条边进入顶点尽管在网络中可能有多条边进入顶点Yi，但在最大流中只能选择一条边；但在最大流中只能选择一条边；(4) 以上第以上第(2)、(3)点保证了最大流中二部图中点保证了最大流中二部图中的边不存在共同顶点。的边不存在共同顶点。X1 Xi XnSY1 Yi YnT45其中其中 表示工人。表示工人。 表示工作。表示工作。

45、1x2x3x4x5x1y2y3y4y5y51,xx 51,yy 例：设有例：设有5位待业者，位待业者，5项工作，他们各自能胜任工作的情况项工作，他们各自能胜任工作的情况如下图所示，要求设计一个就业方案，使尽量多的人能就业。如下图所示，要求设计一个就业方案，使尽量多的人能就业。461x2x3x4x5x1y2y3y4y5ysvtv按照前面描述的方法构造网络流按照前面描述的方法构造网络流(如上图所示如上图所示)：在二部图中：在二部图中增加两个顶点增加两个顶点 分别作为源点、汇点。并用有向边把分别作为源点、汇点。并用有向边把它们与原二部图中顶点相连，令全部边上的容量均为它们与原二部图中顶点相连，令全部

46、边上的容量均为1。当。当网络流达到最大时，如果在最大流中网络流达到最大时，如果在最大流中 上的流量为上的流量为1，就让就让 作作 工作，此即为最大匹配方案。工作，此即为最大匹配方案。,svtv),(jiyxixjy)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (471x2x3x4x5x1y2y3y4y5ysvtv),() 1 ,(sv)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 ,(1x) 1 ,(1y第一次标号。第一次标号。调整调整)0 , 1 ()0 , 1 ()0 , 1 ()0 ,

47、 1 (481x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(4y) 1 , 1 () 1 , 1 (第二次标号。第二次标号。) 1 ,(sv) 1 ,(2x)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (再调整。再调整。491x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 (第三次标号。第三次标号。)0 , 1 ()0 , 1 ()0

48、 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 (501x2x3x4x5x1y2y3ysvtv),()0 , 1 ()0 , 1 ()0 , 1 () 1 ,(5y) 1 , 1 () 1 ,(sv)0 , 1 ()0 , 1 () 1 ,(3x调整。调整。) 1 , 1 ()0 , 1 ()0 , 1 (5y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 (4y)0 , 1 (511x2x3x4x5x1y2y3y5ysvtv)0 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1

49、(第四次标号。第四次标号。)0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 (4y) 1 , 1 (521x3x5x2y3y5ysvtv),()0 , 1 ()0 , 1 () 1 ,(2y) 1 , 1 ()0 , 1 () 1 , 1 () 1 ,(sv)0 , 1 () 1 ,(4x) 1 ,(5y) 1 ,(3x) 1 ,(4y)0 , 1 () 1 ,(2x) 1 ,(1y) 1 ,(4x)0 , 1 (调整调整) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1

50、(1y4x) 1 , 1 (4y2x531x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 (第五次标号。第五次标号。541x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 ,

51、1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 () 1 ,(5x) 1 ,(4y)0 , 1 () 1 ,(3x) 1 ,(5y标号过程已无法再继续。标号过程已无法再继续。551x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1

52、 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 (工人工人,1x,2x,3x4x分别作分别作,2y,1y,4y5y故最多安排四个人工作。故最多安排四个人工作。流量为流量为1的画彩线即所求的最大匹配。的画彩线即所求的最大匹配。562 匈牙利算法(Edmonds, 1965)匈牙利算法的原理为：从当前匹配匈牙利算法的原理为：从当前匹配(如果没有匹配，则初如果没有匹配，则初始匹配为始匹配为0)出发，检查每一个未盖点，然后从它出发寻找可增出发，检查每一个未盖点，然后从它出发寻找可增广路，找到可增广路，则沿着这条可增广路进行扩充，直到广路，找到可增广路，则沿着这条可

53、增广路进行扩充，直到不存在可增广路为止。不存在可增广路为止。根据从未盖点出发寻找可增广路搜索的方法，可以分为：根据从未盖点出发寻找可增广路搜索的方法，可以分为：1) DFS 增广增广2) BFS增广增广3) 多增广路多增广路(Hopcroft-Karp算法算法)在算法中用到的一些变量如下：在算法中用到的一些变量如下：int nx, ny;/X和和Y集合中顶点的个数集合中顶点的个数int gmaxnmaxn;/邻接矩阵邻接矩阵, X集合和集合和Y集合中顶点间边的信息集合中顶点间边的信息int cxmaxn , cymaxn;/cxi表示最终求得的最大匹配中与表示最终求得的最大匹配中与Xi匹配的匹

54、配的Y顶点顶点, cyi同理同理571) DFS 增广/DFS算法中记录顶点访问的状态算法中记录顶点访问的状态/如果如果mki=0表示未访问过，如果为表示未访问过，如果为1表示访问过表示访问过int mkmaxn ;/从从X集合中的顶点集合中的顶点u出发用深度优先的策略寻找增广路出发用深度优先的策略寻找增广路/(这种增广路只能使当前的匹配数增加这种增广路只能使当前的匹配数增加1)int path(int u)for(int v = 0 ; v ny ; v+) /考虑所有考虑所有Yi顶点顶点vif(guv & !mkv)mkv = 1; /如果如果v没有匹配没有匹配,或者如果或者如果v

55、已经匹配了，已经匹配了，/但从但从yv出发可以找到一条增广路出发可以找到一条增广路if(cyv = -1 | path(cyv)cxu = v; /把把v匹配给匹配给ucyv = u; /把把u匹配给匹配给vreturn 1; /找到可增广路找到可增广路return 0 ; /如果不存在从如果不存在从u出发的增广路出发的增广路58int MaxMatch() /求二部图最大匹配的匈牙利算法求二部图最大匹配的匈牙利算法int res(0) ;memset(cx , 0 xff , sizeof(cx) ; /从从0匹配开始增广匹配开始增广memset(cy , 0 xff , sizeof(cy

56、) ;for(int i = 0 ; i = nx ; i+)if(cxi = -1) /从每个未盖点出发进行寻找增广路从每个未盖点出发进行寻找增广路memset(mk , 0 , sizeof(mk) ;res += path(i) ; /每找到一条增广路，可使得匹配数加每找到一条增广路，可使得匹配数加1return res ;优点：实现简洁，理解容易优点：实现简洁，理解容易适用：稠密图，由于边多，适用：稠密图，由于边多，dfs找增广路很快找增广路很快复杂度：复杂度：O(n3)59例题：ZOJ 1654 解题报告602) BFS 增广int predmaxn , mkmaxn , openm

57、axn ;int MaxMatch() int i , u , v , t , d , e , cur , tail , res(0); memset(mk , 0 xff , sizeof(mk) ; memset(cx , 0 xff , sizeof(cx) ; memset(cy , 0 xff , sizeof(cy) ;适用：稀疏二分图，边少，增广路短适用：稀疏二分图，边少，增广路短复杂度：复杂度：O(n3)61 for (i = 0 ; i nx ; i+) predi = -1 ; for (opencur = tail = 0 = i ; cur = tail & cxi = -1 ; cur+) for