支配集、覆盖集、独立集与匹配讲义.

1、信息学院信息技术教研室 Vs Vt V2V4 V3V1 2 4 8 4 2 7 9 1 4 6 V1 V8 V9V10 V7 V4V3 V6 V5 V2 王桂平王桂平 第第7 7章支配集、覆盖集、独立集与匹配章支配集、覆盖集、独立集与匹配 2 本讲内容会涉及以下容易相互混淆的内容: 1.点支配集, 极小点支配集, 最小点支配集, ; v 支配的概念; 2.点独立集, 极大点独立集, 最大点独立集, ; 3.点覆盖集, 极小点覆盖集, 最小点覆盖集, ; v 覆盖的概念; 4.边覆盖集, 极小边覆盖集, 最小边覆盖集, ; 5.边独立集(匹配), 极大边独立集(极大匹配), 最大边独立集(最大

2、匹配), ; 以上几个量存在以下关系: 3 对二部图,还有以下关系式: 二部图的最小点覆盖数等于最大匹配数 二部图的最大点独立数顶点个数 最大匹配 数 4 7.1 点支配集、点覆盖集、点独立集 (都是顶点的集合) 定义定义7.1 设图设图G = , V* V, 若对于若对于 vi V - V*, vj V*, 使得使得: (vi, vj) E, 则称则称vjvi, 并称并称V*为为G的一个的一个 ; 若支配集若支配集V*的任何真子集都不是支配集的任何真子集都不是支配集, 则称则称V*是是; 顶点数最少的支配集称为顶点数最少的支配集称为; 最小支配集中的顶点数称为最小支配集中的顶点数称为, 记作

3、记作或简记为或简记为 。 图图(a)中中,V*= v1, v5 就是一个支配集。因为就是一个支配集。因为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

4、支配集的性质支配集的性质 1.若若G中无孤立顶点中无孤立顶点(度数为度数为0的顶点的顶点),则则一个支配集一个支配集V*,使使 得得G中除中除V*外的所有顶点也组成一个支配集外的所有顶点也组成一个支配集(即即V - V*也是一也是一 个支配集个支配集)。 2.若若G中无孤立顶点中无孤立顶点(度数为度数为0的顶点的顶点),V1*为为支配集支配集,则则G中中 除除V1*外的所有顶点外的所有顶点组成一个支配集组成一个支配集(即即V V1*也是一个也是一个 支配集支配集)。 (证明略证明略) 在图在图(a)中中,取取V* v3, v5 , v6 , v7 , V*是支配集是支配集,但但V - V* 是

5、否是支配集是否是支配集? 7 极小支配集的求解 参见吴文虎编著的信息学奥林匹克竞赛指导图论的算 法与程序设计(PASCAL版)P54 8 设图设图G = , V* V, 若若 , 则称则称V*为为G的的, 或称或称; 若在若在V*中加入任何顶点都不再是独立集中加入任何顶点都不再是独立集, 则称则称V*为为; 顶点数最多的点独立集称为顶点数最多的点独立集称为; 最大点独立集的顶点数称为最大点独立集的顶点数称为, 记作记作, 简记为简记为。 定义定义7.2 图图(a)中中,V*= v1, v5 就是一个点独立集就是一个点独立集,因为因为 v1和和v5是不相邻的是不相邻的 9 图图(a)中中, v1

6、, v5 , v3, v6 , v2, v4, v7 等都是极大等都是极大 点独立集点独立集, 其其 v2, v4, v7 等为最大点独立集等为最大点独立集, 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, 并称

7、并称V*为为G的的 或简称或简称; 若点覆盖若点覆盖V*的任何真子集都不是点覆盖的任何真子集都不是点覆盖, 则称则称V*是是; 顶点个数最少的点覆盖称为顶点个数最少的点覆盖称为; 最小点覆盖的顶点数称为最小点覆盖的顶点数称为, 记作记作, 简记为简记为。 定义定义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

8、, v2, , v6 都是极小点覆盖都是极小点覆盖, v0 是最小点覆盖是最小点覆盖, 0 = 1; 图图(c)中中, v0, v1, v3, v4 , v0, v1, v3, v5 都是极小点都是极小点 覆盖覆盖, 也都是最小的点覆盖也都是最小的点覆盖, 0 = 4。 12 点支配集、点独立集、点覆盖集之间的联系 1)定理定理7.1:设设G = 中中,则则G的的 。逆命题不成立。逆命题不成立(即极小支配集未必即极小支配集未必 是极大独立集是极大独立集)。 2)一个独立集是极大独立集一个独立集是极大独立集,当且仅当它是一个支配集。当且仅当它是一个支配集。 3)定理定理7.2:设设G = 中无孤

9、立点中无孤立点, V*(V* V)为为G的的 , 当且仅当当且仅当。 v 推论推论:设设G是是n阶无孤立点的图阶无孤立点的图,则则V*是是G的极小的极小(最最 小小)点覆盖点覆盖,当且仅当当且仅当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 就是就是 一个

10、更大的独立集一个更大的独立集, 这与这与V*是极大独立集相矛盾。是极大独立集相矛盾。 所以所以, V*是是G的支配集。的支配集。 由由“V*是点独立集是点独立集”可知可知: V1* V*, V* - V1*中的顶点中的顶点 都不受都不受V1*中的顶点支配中的顶点支配, 即即: V1*不是支配集。不是支配集。 所以所以, V*是极小支配集。是极小支配集。 证证: 上面定理的上面定理的的。在右图中的。在右图中 , v3, v5 是极小支配集是极小支配集, 但它不是独立集但它不是独立集, 更更 不是极大独立集。不是极大独立集。 定理定理7.1 14 设设G = 中无孤立点中无孤立点, V*(V* V

11、)为为G的的 , 当且仅当当且仅当。 证证:1) 必要性必要性 假设假设: 存在存在vi, vj V - V*, 且且(vi, vj) E。 由于顶点由于顶点vi和和vj都不在都不在V*中中, 这显然与这显然与“V*是点覆盖是点覆盖”相相 矛盾。矛盾。 所以所以, V - V*为点独立集。为点独立集。 2) 充分性充分性 假设假设: V - V*是点独立集。是点独立集。 因此因此, 任意一条边的两个端点至少有一个在任意一条边的两个端点至少有一个在V*中。中。 由定义可知由定义可知: V*是是G的点覆盖。的点覆盖。 推论推论 设设G是是n阶无孤立点的图阶无孤立点的图, 则则V*是是G的极小的极小

12、(最小最小)点覆点覆 盖盖, 当且仅当当且仅当V-V*是是G的极大的极大(最大最大)点独立集点独立集, 从而有从而有 0 + 0 = n(顶点个数顶点个数)。 定理定理7.2 15 极大点独立集与极小点覆盖集的求解 参见吴文虎编著的信息学奥林匹克竞赛指导图论的算 法与程序设计(PASCAL版)P58 16 7.2 边覆盖集与匹配 (都是边的集合) 定义定义7.4 设图设图G = , E* E, 若若 v V, e E*, 使得使得: v与与 e相关联相关联, 则称则称ev, 并称并称E*为为, 或简称或简称 ; 若边覆盖若边覆盖E*的任何真子集都不是边覆盖的任何真子集都不是边覆盖, 则称则称E

13、*是是; 边数最少的边覆盖集称为边数最少的边覆盖集称为; 最小的边覆盖所含的边数称为最小的边覆盖所含的边数称为, 记作记作或简记为或简记为。 图图(a)中中,E*= e1, e4, e7 就是一个边覆盖集就是一个边覆盖集 17 图图(a)中中, e1, e4, e7 和和 e2, e5, e6, e7 都是极小边覆都是极小边覆 盖盖, e1, e4, e7 是最小边覆盖是最小边覆盖, 1 = 3。 图图(b)中中, e1, e3, e6 和和 e2, e4, e8 都是极小边覆盖都是极小边覆盖, 也都是最小边覆盖也都是最小边覆盖, 1 = 3。 18 设设G = , 若若E*(E* E)中任何

14、两条边均不相邻中任何两条边均不相邻, 则称则称E*为为G中中, 也称也称E*为为G中的中的 (MatchingMatching); 若在若在E*中加入任意一条边所得集合都不是匹配中加入任意一条边所得集合都不是匹配, 则称则称E*为为 ; 边数最多的匹配称为边数最多的匹配称为; 最大匹配的边数称为最大匹配的边数称为或或, 记作记作, 简记为简记为。 定义定义7.5 图图(a)中中,E*= e1, e4, e7 就是一个匹配就是一个匹配 19 图图(a)中中, e2, e6 , e3, e5 , e1, e4, e7 都是极大匹都是极大匹 配配, e1, e4, e7 是最大匹配是最大匹配, 1

15、= 3。 图图(b)中中, e1, e3 , e2, e4 , e4, e7 都是极大匹配都是极大匹配, 也都是最大匹配也都是最大匹配, 1 = 2。 20 例例: :飞行员搭配问题飞行员搭配问题1 1最大匹配问题最大匹配问题 飞行大队有若干个来自各地的飞行员飞行大队有若干个来自各地的飞行员, ,专门驾驶一种型号的飞机专门驾驶一种型号的飞机, , 这种飞机每架有两个飞行员。由于种种原因这种飞机每架有两个飞行员。由于种种原因, ,例如互相配合的问例如互相配合的问 题题, ,有些飞行员不能在同一架飞机上飞行有些飞行员不能在同一架飞机上飞行, ,问如何搭配飞行员问如何搭配飞行员, ,才才 能使能使。

16、 为简单起见为简单起见, ,设有设有1010个飞行员个飞行员, ,图图(a)(a)中的中的V V1 1,V,V2 2, ,V V10 10就代表这 就代表这1010 个飞行员。如果个飞行员。如果, , 否则就不连。否则就不连。 V9 V3 V1 V2 V4 V5 V7 V6 V8 V10 (a) 图图(a)(a)中的中的3 3条蓝色的粗线代表条蓝色的粗线代表 一种搭配方案。由于一个飞行一种搭配方案。由于一个飞行 员不能同时派往两架飞机员不能同时派往两架飞机, ,因因 此此 。称一个图中没有公共端点。称一个图中没有公共端点 的一组边成为一个的一组边成为一个“”。 因此上述问题就转化为因此上述问题

17、就转化为: : , ,这这 个问题叫图的个问题叫图的。 21 例例: :飞行员搭配问题飞行员搭配问题2 2二部图的最大匹配问题二部图的最大匹配问题 在例在例1 1中中, ,如果飞行员分成两部分如果飞行员分成两部分, ,一部分是正驾驶员一部分是正驾驶员, ,一部一部 分是副驾驶员。如何搭配正副驾驶员才能使得出航飞机最分是副驾驶员。如何搭配正副驾驶员才能使得出航飞机最 多的问题可以归结为一个二部图上的最大匹配问题。多的问题可以归结为一个二部图上的最大匹配问题。 例如例如, ,假设有假设有4 4个正驾驶员个正驾驶员, ,有有5 5个副驾驶员个副驾驶员, ,飞机必须要有飞机必须要有 一名正驾驶员和一名

18、副驾驶员才能起飞。正驾驶员和副驾一名正驾驶员和一名副驾驶员才能起飞。正驾驶员和副驾 驶员之间存在搭配的问题。驶员之间存在搭配的问题。 Y1Y2Y3Y4Y5 X1X2X3X4 (b) 图图(b)中中,X1,X2,X3,X4表示表示4个正个正 驾驶员驾驶员,Y1,Y2,Y3,Y4,Y5表示表示5个个 副驾驶员。正驾驶员之间不能副驾驶员。正驾驶员之间不能 搭配搭配,副驾驶员之间也不能搭配副驾驶员之间也不能搭配, 所以这是一个所以这是一个。 图图(b)中的中的4条蓝色的粗线代表条蓝色的粗线代表 一种搭配方案。这个问题实际一种搭配方案。这个问题实际 上是求一个二部图的上是求一个二部图的。 22 定义定义

19、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的未盖的未盖 点点(未盖点的定义见未盖点的定义见7.3节节),则称匹配则称匹配M为图为图G的的。 图图(a)中中, M = e1, e4, e7 为完美匹为完美匹 配配(最大匹配最大匹配), 它

20、也是最小边覆盖。它也是最小边覆盖。 图图(b)中不可能有完美匹配中不可能有完美匹配, 因此因此, 对对 任何匹配都存在未盖点。任何匹配都存在未盖点。 定义定义7.6 24 任取一个最大匹配任取一个最大匹配, 比如比如: M = e2, e4 , 则则M e6 , M e8 , M e7 都是图的最小边覆盖。都是图的最小边覆盖。 任取一个最小边覆盖任取一个最小边覆盖, 比如比如: W = e1, e3, e6 , 从中移去一条相邻的边从中移去一条相邻的边, 则则 e1, e3 和和 e1, e6 都是图的最大匹配。都是图的最大匹配。 我们通常这样来做我们通常这样来做: 用最大匹配通过增加关联未盖

21、点的边获得最小边覆盖用最大匹配通过增加关联未盖点的边获得最小边覆盖; 用最小边覆盖通过移去相邻的一条边获得最大匹配。用最小边覆盖通过移去相邻的一条边获得最大匹配。 (详见定理详见定理7.3) 25 定理定理7.3 设设n阶图阶图G中无孤立点。中无孤立点。 (1) 设设M为为G的一个最大匹配的一个最大匹配, 对于对于G中每个中每个M的未盖点的未盖点v, 由与由与v关联关联 的边所组成的边集的边所组成的边集N, 则则W = MN为为G中最小边覆盖中最小边覆盖; (2) 设设W1为为G的最小边覆盖的最小边覆盖, 若若G中存在相邻的边就移去其中的一条中存在相邻的边就移去其中的一条 , 设移去的边集为设

22、移去的边集为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 - 1 由由“W1是最小边覆盖是最小边覆盖”可知可知: W1中每条边的两个端点不可能都与中每条边的两个端点不可能都与W1中的其它边相中的其它边相

23、 关联关联, 因此因此, 在由在由W1构造构造M1时时, 每移去相邻两条边中的一条时每移去相邻两条边中的一条时, 将只产生一个将只产生一个M的未盖点的未盖点 。 所以所以, |N1| = |W1| - |M1| = M1的未盖点数的未盖点数 = n - 2|M1|。 整理后整理后, 得得: |W1| = 1 = n - |M1|。 又又M1是匹配是匹配, W是边覆盖是边覆盖, 所以所以, |M1| 1, |W| 1。 通过比较可得通过比较可得: 1 = n-|M1| n - 1 = |W| 1。 显然上式中各等号成立显然上式中各等号成立, 所以所以, |M1| = 1, |W| = 1, 且且

24、 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的未盖点。的未盖点。 所以所以, M必为必为G中完美匹配。中完美匹配。 推论推论 设设G是是n阶无孤立点的图阶无孤

25、立点的图, 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)中实线边所示。中实线边所示。M1不是不是 最大匹配最大匹配, M2是最大匹配是最大匹配(也是完美匹

26、配也是完美匹配)。 = e2e3e4e7e6是关于是关于M1的可增广路径。的可增广路径。M2没有可增广没有可增广 路径。路径。 28 7.3 匹配问题的求解 为了求解各种匹配问题为了求解各种匹配问题,必须引入一系列概念必须引入一系列概念: V1 V5 V10V9 V11 V6 V7 V8 V3 V2 V4 e2e1 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 (a) 设设Vi是图是图G = 的一个顶点的一个顶点,M是图是图G中一个给定的匹中一个给定的匹 配配,如果如果Vi不与任意一条属于匹配不与任意一条属于匹配M的边相关联的边相关联,则称则称Vi是匹是匹 配配M的

27、的。很形象。很形象:没有被匹配没有被匹配M中的边中的边“盖住盖住”。 取定取定M=e4, e6, e10(由粗线组由粗线组 成的匹配成的匹配),则图则图(a)中中,V10就是就是 M的一个未盖点。的一个未盖点。 29 V1 V5 V10V9 V11 V6 V7 V8 V3 V2 V4 e2e1 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 (a) 设设P是图是图G的一条轨的一条轨(路径路径),如果如果P的任意两条相邻的边一定是一的任意两条相邻的边一定是一 条属于匹配条属于匹配M而另一条不属于而另一条不属于M,则称则称P是一条是一条。 在图在图(a)中中,取定取定M=

28、e4, e6, e10(由粗线组成的匹配由粗线组成的匹配),则图则图(b)、 (c)所示的路径都是交错轨。所示的路径都是交错轨。 特别地特别地,如果轨如果轨P仅含一条边仅含一条边,那么无论这条边是否属于匹配那么无论这条边是否属于匹配 M,P一定是一条交错轨。一定是一条交错轨。 V1 V5 V9 V11 V6 V2 e1 e4 e7 e10 e12 (b) V9 V6 V7 V3 V4 e3 e6 e8 e10 (c) 30 V1 V5 V10V9 V11 V6 V7 V8 V3 V2 V4 e2e1 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 (a) 两个端点都是

29、未盖点的两个端点都是未盖点的称为称为。 图图(b)所示的交错轨的两个端点所示的交错轨的两个端点V2, V11都是匹配都是匹配M的未盖点的未盖点,所所 以这条轨是可增广轨以这条轨是可增广轨,而图而图(c)所示的交错轨不是可增广轨。所示的交错轨不是可增广轨。 特别地特别地,如果两个未盖点之间仅含一条边如果两个未盖点之间仅含一条边,那么单单这条边也组那么单单这条边也组 成一条可增广轨。成一条可增广轨。 V1 V5 V9 V11 V6 V2 e1 e4 e7 e10 e12 (b) V9 V6 V7 V3 V4 e3 e6 e8 e10 (c) 31 V1 V5 V10V9 V11 V6 V7 V8

30、V3 V2 V4 e2e1 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 (a) V1 V5 V9 V11 V6 V2 e1 e4 e7 e10 e12 (b) V1 V5 V10V9 V11 V6 V7 V8 V3 V2 V4 e2e1 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 (d) 对于图对于图G的一个匹配的一个匹配M来说来说,如果能找到一条如果能找到一条P,那么这那么这 个匹配个匹配M一定可以通过下述方法改进成一个包含多一条边的匹一定可以通过下述方法改进成一个包含多一条边的匹 配配Ms(即匹配即匹配M扩充了扩充了): 如图如图

31、(a)中图中图G的一个匹配的一个匹配M,找到图找到图(b)所示的一条可增广轨所示的一条可增广轨, 那么得到图那么得到图(d)所示的新匹配所示的新匹配Ms。Ms比比M多一条边。多一条边。 32 证证: 1) 必要性必要性 假设假设: M为为G中最大匹配。中最大匹配。 若若G中存在中存在M的可增广路径的可增广路径 , 则则 中在中在M中的边比不中的边比不 在在M中的少中的少1。 设设M = (M (E) - (M (E) = M(E), 则则M中边彼中边彼 此不邻此不邻, 且且M比比M多一条边多一条边, 即即: M是比是比M多一条边的匹配多一条边的匹配, 这就与这就与“M是最大匹配是最大匹配”相矛

32、盾。相矛盾。 所以所以, M不含可增广路径。不含可增广路径。 定理定理7.4 M为为G的最大匹配的最大匹配, 当且仅当当且仅当G不含不含M可增广路径。可增广路径。 33 2) 充分性充分性 设设: M是是G中不含可增广路径的匹配中不含可增广路径的匹配, M1是是G中的最大匹配。中的最大匹配。 下面证明下面证明: |M| = |M1|。 设设: H = GM1 M。 当当H = 时时 显然显然, M = M1, 所以所以, M为为G中最大匹配。中最大匹配。 若若H 时时 由于由于M和和M1都是匹配都是匹配, 所以所以, H各连通分支要么是由各连通分支要么是由M和和M1中中 的边组成的交错圈的边组

33、成的交错圈, 在交错圈上在交错圈上M和和M1中的边数相等中的边数相等, 要么为由要么为由 M和和M1的边组成的交错路径。的边组成的交错路径。 由已知条件可知由已知条件可知: M不含可增广路径不含可增广路径, M1是最大匹配。由必是最大匹配。由必 要性可知要性可知: M1中也无可增广的交错路径。中也无可增广的交错路径。 所以所以, 在由在由M和和M1组成的交错路径上组成的交错路径上, M和和M1的边也相等的边也相等, 即即: M与与M1边的个数相同。边的个数相同。 因此因此, M为最大匹配。为最大匹配。 34 求最大匹配的可行方法: 给定一个初始匹配给定一个初始匹配M(如果没有给定如果没有给定,

34、则则M),如果图如果图G没有没有 未盖点未盖点,则肯定不会有可增广轨了则肯定不会有可增广轨了,即即M就是最大匹配。就是最大匹配。 对图对图G的所有未盖点的所有未盖点Vi,通过通过搜索以搜索以Vi为端点的为端点的 可增广轨可增广轨,从而通过可增广轨逐渐把从而通过可增广轨逐渐把M扩大。扩大。(在扩大在扩大M的过的过 程当中程当中,某些未盖点会逐渐被某些未盖点会逐渐被M盖住盖住) 35 寻找可增广轨的方法 设设M是图是图G的一个匹配的一个匹配,Vi是取定的未盖点是取定的未盖点,如果存在从如果存在从Vi到到Vj的的 交错轨交错轨,则称则称。 以图以图(d)为例为例,如果取定了未盖点如果取定了未盖点V4

35、,那那 么存在着交错轨么存在着交错轨P=V4, V3, V7, V6,因因 此此,同样同样 V1 V5 V10V9 V11 V6 V7 V8 V3 V2 V4 e2e1 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 (d) 寻找以寻找以Vi为端点的可增广轨的方法为端点的可增广轨的方法:设法把由设法把由Vi交错可达的顶点都找出来交错可达的顶点都找出来 ,每找到一个每找到一个,就检查一下它是不是未盖点就检查一下它是不是未盖点,如果是如果是,则可增广轨就找到了。则可增广轨就找到了。 如果已经把所有由如果已经把所有由Vi交错可达的顶点都找出来了交错可达的顶点都找出来了,而其

36、中没有一个是未盖而其中没有一个是未盖 点点,就可以肯定以就可以肯定以Vi为一端的可增广轨一定不存在了。为一端的可增广轨一定不存在了。 36 为了把由为了把由Vi交错可达的顶点都找出来交错可达的顶点都找出来,需要引入交错树的概念需要引入交错树的概念 设设M是图是图G=V,E的一个取定的匹配的一个取定的匹配,T是图是图G的一个子图的一个子图,如果如果T 具有下述性质具有下述性质: (1) T是一棵树是一棵树; (2) T中存在一个顶点中存在一个顶点Vi,它是未盖点它是未盖点; (3) 对于对于T的任意一个不同于的任意一个不同于Vi的顶点来说的顶点来说,T中连接中连接Vi与与Vj的唯的唯 一轨是交错

37、轨。一轨是交错轨。 那么称那么称T是一个以是一个以Vi为根的为根的。 V15 V6 V5 V4 V3 V2 V1 V12 V13 V14 V11 V8 V7 V9 V10 (a) V5 V4 V3 V2 V1 V8 V7 (b) T + + + + 图图(a)中粗边代表一个匹中粗边代表一个匹 配。图配。图(b)所示的子图就所示的子图就 是一个以是一个以V1为根的交错为根的交错 树。树。 37 为了描述如何扩大一个交错树为了描述如何扩大一个交错树,需要介绍有关顶点分类的概念需要介绍有关顶点分类的概念 交错树交错树T的顶点可以分成两类的顶点可以分成两类: 外点外点:即图即图(b)中标中标+号的顶点

38、号的顶点,如果如果Vj是外点是外点,则连接根则连接根Vi与与Vj 的交错轨一定的交错轨一定,且且P上与上与Vj关联的边一定关联的边一定 。 内点内点:即图即图(b)中标中标号的顶点号的顶点,如果如果Vj是内点是内点,则连接根则连接根Vi与与Vj 的交错轨一定的交错轨一定,且且P上与上与Vj关联的边一定关联的边一定 。 V5 V4 V3 V2 V1 V8 V7 (b) T + + + + 图图(b)中中V1、V3、V5、V7为外为外 点点,而而V2、V4、V8为内点。为内点。 38 扩大以Vi为根的交错树的方法 看看图看看图G中有没有与交错树中有没有与交错树T的外点关联而不属于的外点关联而不属于

39、T的边的边e,如果有如果有, 就看看就看看e的另一个端点的另一个端点Vk是不是属于是不是属于T(肯定不属于肯定不属于T),如果如果Vk不属不属 于于T,那么就可以把那么就可以把e和和Vk都加入到都加入到T中中,使使T扩大。在扩大的时候扩大。在扩大的时候,还还 可以分为两种情况可以分为两种情况: Vk是未盖点是未盖点,这时这时,把把e与与Vk加入到加入到T中后中后,T中连接根中连接根Vi与与Vk的交错路是一的交错路是一 条可增广轨。条可增广轨。(见下图见下图(a) Vk不是未盖点不是未盖点,也就是说也就是说,有一条属于匹配有一条属于匹配M的边的边与与Vk关联关联,这时这时,在把在把e 与与Vk加

40、入到加入到T中后中后,还可以把还可以把以及它的端点以及它的端点Vm加入到加入到T中去中去,因为很因为很 显然从显然从Vi也交错可达也交错可达的另一端点的另一端点Vm。另外。另外,Vk应该是内点应该是内点,而而Vm是是 外点。外点。(见下图见下图(b) (b) Vi + + + + Vj e + Vk Vm e Vi + + + + 未盖点未盖点Vj e (a) Vk 39 V1 (a) + (e) V5 V4 V3 V2 V1 V8 V7 + + + + V15 V6 + e e V3 V2 V1 (b) + + e e V5 V4 V3 V2 V1 V8 V7 (d) + + + + e e

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

42、5 V4 V3 V2 V1 V12 V13 V14 V11 V8 V7 V9 V10 (f) 对于图对于图(e)中的交错树中的交错树,已经无法扩大了已经无法扩大了,但以但以 V1为一端的可增广轨是存在的。在图为一端的可增广轨是存在的。在图(f)中用中用 虚线标出的虚线标出的(V1,V2,V3,V4,V5,V7,V8,V9)就是一就是一 条连接条连接V1和和V9的可增广轨。的可增广轨。 (e) V5 V4 V3 V2 V1 V8 V7 + + + + V15 V6 + e e 41 如果发现了一条不属于交错树如果发现了一条不属于交错树T的边的边e,e的两个端点都是的两个端点都是T的外的外 点点,

43、那么把那么把e加到加到T中去得到的图叫做中去得到的图叫做。 (e) V5 V4 V3 V2 V1 V8 V7 + + + + V15 V6 + e e 例如在图例如在图(e)中中,连接连接T的两个顶点的两个顶点V5与与V7的这条边的这条边 e(图中的红边图中的红边)原不属于原不属于T,现在把现在把e加到加到T中去中去,只只 不过是使不过是使T增加了一条边增加了一条边,没有扩大由没有扩大由Vi交错可达交错可达 的顶点的范围的顶点的范围,反而使得反而使得T不再是树了。不再是树了。 带花树的特点是带花树的特点是,它恰好有一个圈它恰好有一个圈,这唯一的圈称这唯一的圈称 为带花树的花。圈内包含奇数条边。

44、为带花树的花。圈内包含奇数条边。 带花树的作用见带花树的作用见“7.3.4 任意图的最大匹配任意图的最大匹配” 42 匹配问题 匹配问题可以分为如下类型匹配问题可以分为如下类型: 1.二部图的最大匹配二部图的最大匹配; 2.二部图的完备匹配二部图的完备匹配; 3.二部图的最佳匹配二部图的最佳匹配; 4.任意图的最大匹配任意图的最大匹配; 每种匹配问题的解法不一样每种匹配问题的解法不一样,难度也不一样。难度也不一样。 43 7.3.1 二分图的最大匹配 求二部图的最大匹配的算法有求二部图的最大匹配的算法有: 1.网络流解法网络流解法 2.匈牙利算法匈牙利算法 3.Hopcroft-Karp算法算

45、法(匈牙利算法的改进匈牙利算法的改进) 44 1 网络流解法 1)从二部图从二部图G出发构造一个网络出发构造一个网络G: a)增加一个源点增加一个源点S和汇点和汇点T; b)从从S向向X的每一个顶点都画一条有向弧的每一个顶点都画一条有向弧,从从Y的每一个顶点都的每一个顶点都 向向T画一条有向弧画一条有向弧; c)原来原来G中的边都改成有向弧中的边都改成有向弧,方向是从方向是从X的顶点指向的顶点指向Y的顶点的顶点; d)令所有弧的容量都等于令所有弧的容量都等于1。 2)求网络求网络G的最大流的最大流F。 3)从从X的顶点指向的顶点指向Y的顶点的弧集合中的顶点的弧集合中,弧流量为弧流量为1的弧对应

46、二部图的匹的弧对应二部图的匹 配边配边,最大流值最大流值F对应二部图的最大匹配的边数。对应二部图的最大匹配的边数。 为什么这样构造的网络求出来的最大为什么这样构造的网络求出来的最大 流就是最大匹配流就是最大匹配? (1) 网络中所有的弧容量均为网络中所有的弧容量均为1。 (2) 尽管在网络中顶点尽管在网络中顶点Xi可能发出多条边可能发出多条边,但在但在 最大流中只能选择一条边最大流中只能选择一条边; (3) 尽管在网络中可能有多条边进入顶点尽管在网络中可能有多条边进入顶点Yi,但但 在最大流中只能选择一条边在最大流中只能选择一条边; (4) 以上第以上第(2)、(3)点保证了最大流中二部图中点

47、保证了最大流中二部图中 的边不存在共同顶点。的边不存在共同顶点。 X1 Xi Xn S Y1 Yi Yn T 45 其中其中 表示工人。表示工人。 表示工作。表示工作。 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y 51 ,xx 51 ,yy 例例:设有设有5位待业者位待业者,5项工作项工作,他们各自能胜任工作的情况如下他们各自能胜任工作的情况如下 图所示图所示,要求设计一个就业方案要求设计一个就业方案,使尽量多的人能就业。使尽量多的人能就业。 46 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v 按照前面描述的

48、方法构造网络流按照前面描述的方法构造网络流(如上图所示如上图所示)：在二部图中：在二部图中 增加两个顶点增加两个顶点 分别作为源点、汇点。并用有向边把分别作为源点、汇点。并用有向边把 它们与原二部图中顶点相连，令全部边上的容量均为它们与原二部图中顶点相连，令全部边上的容量均为1。当。当 网络流达到最大时，如果在最大流中网络流达到最大时，如果在最大流中 上的流量为上的流量为1， 就让就让 作作 工作，此即为最大匹配方案。工作，此即为最大匹配方案。 , s v t v ),( ji yx i x j y )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( 47

49、 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v ),( ) 1 ,( s v )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( ) 1 ,( 1 x ) 1 ,( 1 y 第一次标号。第一次标号。调整调整 )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( 48 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v ),( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( ) 1 , 1

50、 ( ) 1 ,( 4 y ) 1 , 1 () 1 , 1 ( 第二次标号。第二次标号。 ) 1 ,( s v ) 1 ,( 2 x )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( 再调整。再调整。 49 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v )0 , 1 ( )0 , 1 ( )0 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( 第三次标号。第三次标号。 )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0

51、 , 1 ( ) 1 , 1 ( ) 1 , 1 ( 50 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y s v t v ),( )0 , 1 ( )0 , 1 ( )0 , 1 ( ) 1 ,( 5 y ) 1 , 1 ( ) 1 ,( s v )0 , 1 ( )0 , 1 ( ) 1 ,( 3 x 调整。调整。 ) 1 , 1 ( )0 , 1 ( )0 , 1 ( 5 y ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( 4 y )0 , 1 ( 51 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 5 y s v t v

52、 )0 , 1 ( )0 , 1 ( ) 1 , 1 ( )0 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( 第四次标号。第四次标号。 )0 , 1 ( )0 , 1 ( )0 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( 4 y ) 1 , 1 ( 52 1 x 3 x 5 x 2 y 3 y 5 y s v t v ),( )0 , 1 ( )0 , 1 ( ) 1 ,( 2 y ) 1 , 1 ( )0 , 1 ( ) 1 , 1 ( ) 1 ,( s v )0 , 1 ( ) 1 ,( 4 x ) 1 ,( 5 y

53、 ) 1 ,( 3 x ) 1 ,( 4 y )0 , 1 ( ) 1 ,( 2 x ) 1 ,( 1 y ) 1 ,( 4 x )0 , 1 ( 调整调整 ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 () 1 , 1 ( 1 y 4 x ) 1 , 1 ( 4 y 2 x 53 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v )0 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( )0 , 1

54、 ( ) 1 , 1 ( ) 1 , 1 ( )0 , 1 ( ) 1 , 1 ( )0 , 1 ( ) 1 , 1 ( ) 1 , 1 ( )0 , 1 ( )0 , 1 ( 第五次标号。第五次标号。 54 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v ),( )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

55、 ( ) 1 , 1 ( ) 1 ,( s v )0 , 1 ( ) 1 ,( 5 x ) 1 ,( 4 y )0 , 1 ( ) 1 ,( 3 x ) 1 ,( 5 y 标号过程已无法再继续。标号过程已无法再继续。 55 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v ),( )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 (

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

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

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

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

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