《支配集、覆盖集、独立集与匹配讲义.课件》由会员分享，可在线阅读，更多相关《支配集、覆盖集、独立集与匹配讲义.课件（71页珍藏版）》请在金锄头文库上搜索。
1、信息学院信息技术教研室VsVtV2V4V3V12484279146V1V8V9V10V7V4V3V6V5V2图论算法理论、实现及应用王桂平王桂平第第7 7章支配集、覆盖集、独立集与匹配章支配集、覆盖集、独立集与匹配2本讲内容会涉及以下容易相互混淆的内容：1.点支配集, 极小点支配集, 最小点支配集, 点支配数点支配数点支配数点支配数 0 0(G)(G);v支配的概念；2.点独立集, 极大点独立集, 最大点独立集, 点独立数点独立数点独立数点独立数 0 0(G)(G);3.点覆盖集, 极小点覆盖集, 最小点覆盖集, 点覆盖数点覆盖数点覆盖数点覆盖数 0 0(G)(G);v覆盖的概念；4.边覆盖集
2、, 极小边覆盖集, 最小边覆盖集, 边覆盖数边覆盖数边覆盖数边覆盖数 1 1(G)(G);5.边独立集(匹配), 极大边独立集(极大匹配), 最大边独立集(最大匹配), 边独立数边独立数边独立数边独立数( (或匹配数或匹配数或匹配数或匹配数) ) 1 1(G)(G);以上几个量存在以下关系： 0 0 0 0 n n，即：点覆盖数，即：点覆盖数，即：点覆盖数，即：点覆盖数 + + 点独立数点独立数点独立数点独立数 = n= n 1 1 1 1 n n，即：边覆盖数，即：边覆盖数，即：边覆盖数，即：边覆盖数 + + 边独立数边独立数边独立数边独立数 = n= n3对二部图，还有以下关系式：二部图的
3、最小点覆盖数 0 0 等于最大匹配数 1 1。ZOJ 1364ZOJ 1364二部图的最大点独立数 0 0顶点个数n n最大匹配数 1 1。( (前提是该二部图没有孤立顶点，如果有孤立顶点，前提是该二部图没有孤立顶点，如果有孤立顶点，前提是该二部图没有孤立顶点，如果有孤立顶点，前提是该二部图没有孤立顶点，如果有孤立顶点，对这些孤立顶点要单独考虑对这些孤立顶点要单独考虑对这些孤立顶点要单独考虑对这些孤立顶点要单独考虑) )ZOJ 1137ZOJ 113747.1 点支配集、点覆盖集、点独立集(都是顶点的集合)定义定义7.1 支配与支配集支配与支配集支配与支配集支配与支配集 设图设图G = , V
4、* V, 若对于若对于 vi V - V*, vj V*, 使得使得: (vi, vj) E, 则称则称vj支配支配支配支配vi, 并称并称V*为为G的一个的一个支支支支配集配集配集配集;若支配集若支配集V*的任何真子集都不是支配集的任何真子集都不是支配集, 则称则称V*是是极小极小极小极小支配集支配集支配集支配集;顶点数最少的支配集称为顶点数最少的支配集称为最小最小最小最小支配集支配集支配集支配集;最小支配集中的顶点数称为最小支配集中的顶点数称为支配数支配数支配数支配数, 记作记作 0 0(G)(G)或简记为或简记为 0 0。图图(a)中，中，V*= v1, v5 就是一个支配集。因为就是一
5、个支配集。因为V-V*=v2, v3, v4, v6, v7中的顶点都是中的顶点都是V*中顶点中顶点的邻接顶点。的邻接顶点。通俗地讲，所谓支配集，就是通俗地讲，所谓支配集，就是通俗地讲，所谓支配集，就是通俗地讲，所谓支配集，就是V V中的顶点要么是中的顶点要么是中的顶点要么是中的顶点要么是V*V*集合中的元素，要么与集合中的元素，要么与集合中的元素，要么与集合中的元素，要么与V*V*中的一个顶点相邻。中的一个顶点相邻。中的一个顶点相邻。中的一个顶点相邻。5在图在图(a)中中, v1, v5 , v3, v5 和和 v2, v4, v7 都是都是极小支极小支极小支极小支配集配集配集配集, v1,
6、 v5 , v4, v5 和和 v3, v6 都是都是最小支配集最小支配集最小支配集最小支配集, 0 0 = 2 = 2。图图(b)为为7阶星形图阶星形图, v0 , v1, v2, ., v6 为为极小支配集极小支配集极小支配集极小支配集, v0 为为最小支配集最小支配集最小支配集最小支配集, 0 0 = 1 = 1。图图(c)为轮图为轮图W6, v0 , v1, v3 , v1, v4 等都是等都是极小支极小支极小支极小支配集配集配集配集, 显然显然, 0 01 1。6支配集的性质支配集的性质1.若若G中无孤立顶点中无孤立顶点(度数为度数为0的顶点的顶点)，则，则存在存在存在存在一个支配集
7、一个支配集V*，使得，使得G中除中除V*外的所有顶点也组成一个支配集外的所有顶点也组成一个支配集(即即V - V*也是一个支配集也是一个支配集)。2.若若G中无孤立顶点中无孤立顶点(度数为度数为0的顶点的顶点)，V1*为为极小极小极小极小支配集，则支配集，则G中除中除V1*外的所有顶点外的所有顶点也也也也组成一个支配集组成一个支配集(即即V V1*也是一也是一个支配集个支配集)。(证明略证明略)思考：思考：思考：思考：在图在图(a)中，取中，取V* v3, v5 , v6 , v7 ， V*是支配集，是支配集，但但V - V*是否是支配集？是否是支配集？7极小支配集的求解参见吴文虎编著的信息学
8、奥林匹克竞赛指导图论的算法与程序设计(PASCAL版)P54有有有有电电子版子版子版子版8 设图设图G = , V* V, 若若V*V*中任何两个顶点均不相中任何两个顶点均不相中任何两个顶点均不相中任何两个顶点均不相邻邻邻邻, 则称则称V*为为G的的点独立集点独立集点独立集点独立集, 或称或称独立集独立集独立集独立集;若在若在V*中加入任何顶点都不再是独立集中加入任何顶点都不再是独立集, 则称则称V*为为极大极大极大极大点独立集点独立集点独立集点独立集;顶点数最多的点独立集称为顶点数最多的点独立集称为最大最大最大最大点独立集点独立集点独立集点独立集;最大点独立集的顶点数称为最大点独立集的顶点数
9、称为点独立数点独立数点独立数点独立数, 记作记作 0 0(G)(G), 简记为简记为 0 0。定义定义7.2 点独立集点独立集点独立集点独立集图图(a)中，中，V*= v1, v5 就是一个点独立集，因就是一个点独立集，因为为v1和和v5是不相邻的是不相邻的。9图图(a)中中, v1, v5 , v3, v6 , v2, v4, v7 等都是极大点等都是极大点独立集独立集, 其其 v2, v4, v7 等为最大点独立集等为最大点独立集, 0 = 3;图图(b)中中, v0 , v1, v2, , v6 都是极大点独立集都是极大点独立集, 其其 v1, v2, , v6 是最大点独立集是最大点独
10、立集, 0 = 6;图图(c)中中, v1, v3 , v1, v4 是极大点独立集是极大点独立集, 也都是最也都是最大点独立集大点独立集, 02。10 设设G = , V* V, 若对于若对于 e E, v V*, 使得使得: v与与e相关联相关联, 则称则称v覆盖覆盖覆盖覆盖e, 并称并称V*为为G的的点点点点覆盖集覆盖集覆盖集覆盖集或简称或简称点覆盖点覆盖点覆盖点覆盖;若点覆盖若点覆盖V*的任何真子集都不是点覆盖的任何真子集都不是点覆盖, 则称则称V*是是极小极小极小极小点覆盖点覆盖点覆盖点覆盖;顶点个数最少的点覆盖称为顶点个数最少的点覆盖称为最小最小最小最小的点覆盖的点覆盖的点覆盖的点
11、覆盖;最小点覆盖的顶点数称为最小点覆盖的顶点数称为点覆盖数点覆盖数点覆盖数点覆盖数, 记作记作 0 0(G)(G), 简记为简记为 0 0。定义定义7.3 覆盖与点覆盖集覆盖与点覆盖集覆盖与点覆盖集覆盖与点覆盖集图图(a)中，中，V*= v1, v3, v5, v7 就是一个点覆盖就是一个点覆盖集集。通俗地讲，所谓点覆盖集通俗地讲，所谓点覆盖集通俗地讲，所谓点覆盖集通俗地讲，所谓点覆盖集V*V*，就是，就是，就是，就是GG中所中所中所中所有的边至少有一个顶点属于有的边至少有一个顶点属于有的边至少有一个顶点属于有的边至少有一个顶点属于V*V*( (顶点覆盖边顶点覆盖边顶点覆盖边顶点覆盖边) )。
12、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, v5 都是极小点覆都是极小点覆盖盖, 也都是最小的点覆盖也都是最小的点覆盖, 0 = 4。12点支配集、点独立集、点覆盖集之间的联系1)定理定理7.1：设设G = 中中无孤立点无孤立点无孤立点
13、无孤立点，则，则G的的极大点独立极大点独立极大点独立极大点独立集都是集都是集都是集都是GG的极小支配集的极小支配集的极小支配集的极小支配集。逆命题不成立。逆命题不成立(即极小支配集未即极小支配集未必是极大独立集必是极大独立集)。2)一个独立集是极大独立集，当且仅当它是一个支配集。一个独立集是极大独立集，当且仅当它是一个支配集。3)定理定理7.2：设设G = 中无孤立点中无孤立点, V*(V* V)为为G的的点点点点覆盖覆盖覆盖覆盖, 当且仅当当且仅当V-V*V-V*为为为为GG的点独立集的点独立集的点独立集的点独立集。v推论推论：设：设G是是n阶无孤立点的图，则阶无孤立点的图，则V*是是G的极
14、小的极小(最小最小)点覆盖，当且仅当点覆盖，当且仅当V-V*是是G的极大的极大(最大最大)点点独立集，从而有独立集，从而有 0 + 0 = n(顶点个数顶点个数)。13 设设G = 中中无孤立点无孤立点无孤立点无孤立点, 则则G的的极大点独立集极大点独立集极大点独立集极大点独立集都是都是都是都是GG的极小支配集的极小支配集的极小支配集的极小支配集。假设假设: V*是是G中的任意一个极大独立集。中的任意一个极大独立集。 v V - V*, 一定有一定有: v V*, 使得使得: (v, v) E。假设假设: u V-V*不与不与V*中任何顶点相邻中任何顶点相邻, 则则V* u 就是就是一个更大的
15、独立集一个更大的独立集, 这与这与V*是极大独立集相矛盾。是极大独立集相矛盾。所以所以, V*是是G的支配集。的支配集。由由“V*是点独立集是点独立集”可知可知: V1* V*, V* - V1*中的顶点中的顶点都不受都不受V1*中的顶点支配中的顶点支配, 即即: V1*不是支配集。不是支配集。所以所以, V*是极小支配集。是极小支配集。证：证：上面定理的上面定理的逆命题是不成立逆命题是不成立逆命题是不成立逆命题是不成立的。在右图中的。在右图中, v3, v5 是极小支配集是极小支配集, 但它不是独立集但它不是独立集, 更不更不是极大独立集。是极大独立集。定理定理7.114 设设G = 中无孤
16、立点中无孤立点, V*(V* V)为为G的的点覆点覆点覆点覆盖盖盖盖, 当且仅当当且仅当V-V*V-V*为为为为GG的点独立集的点独立集的点独立集的点独立集。证：证：1) 必要性必要性假设假设: 存在存在vi, vj V - V*, 且且(vi, vj) E。由于顶点由于顶点vi和和vj都不在都不在V*中中, 这显然与这显然与“V*是点覆盖是点覆盖”相相矛盾。矛盾。所以所以, V - V*为点独立集。为点独立集。 2) 充分性充分性假设假设: V - V*是点独立集。是点独立集。因此因此, 任意一条边的两个端点至少有一个在任意一条边的两个端点至少有一个在V*中。中。由定义可知由定义可知: V*
17、是是G的点覆盖。的点覆盖。推论推论 设设G是是n阶无孤立点的图阶无孤立点的图, 则则V*是是G的极小的极小(最小最小)点覆点覆盖盖, 当且仅当当且仅当V-V*是是G的极大的极大(最大最大)点独立集点独立集, 从而有从而有 0 + 0 = n(顶点个数顶点个数)。定理定理7.215极大点独立集与极小点覆盖集的求解参见吴文虎编著的信息学奥林匹克竞赛指导图论的算法与程序设计(PASCAL版)P58167.2 边覆盖集与匹配(都是边的集合)定义定义7.4 覆盖与边覆盖集覆盖与边覆盖集覆盖与边覆盖集覆盖与边覆盖集 设图设图G = , E* E, 若若 v V, e E*, 使得使得: v与与e相关联相关
18、联, 则称则称e覆盖覆盖覆盖覆盖v, 并称并称E*为为边覆盖集边覆盖集边覆盖集边覆盖集, 或简称或简称边边边边覆盖覆盖覆盖覆盖;若边覆盖若边覆盖E*的任何真子集都不是边覆盖的任何真子集都不是边覆盖, 则称则称E*是是极小边覆盖极小边覆盖极小边覆盖极小边覆盖;边数最少的边覆盖集称为边数最少的边覆盖集称为最小的边覆盖最小的边覆盖最小的边覆盖最小的边覆盖;最小的边覆盖所含的边数称为最小的边覆盖所含的边数称为边覆盖数边覆盖数边覆盖数边覆盖数, 记作记作 1 1(G)(G)或简记为或简记为 1 1。图图(a)中，中，E*= e1, e4, e7 就是一个边覆盖集就是一个边覆盖集。通俗地讲，所谓边覆盖集通
19、俗地讲，所谓边覆盖集通俗地讲，所谓边覆盖集通俗地讲，所谓边覆盖集E*E*，就是，就是，就是，就是GG中所有中所有中所有中所有的顶点都是的顶点都是的顶点都是的顶点都是E*E*中边的顶点中边的顶点中边的顶点中边的顶点( (边覆盖顶点边覆盖顶点边覆盖顶点边覆盖顶点) ) 。17图图(a)中中, e1, e4, e7 和和 e2, e5, e6, e7 都是极小边覆盖都是极小边覆盖, e1, e4, e7 是最小边覆盖是最小边覆盖, 1 = 3。图图(b)中中, e1, e3, e6 和和 e2, e4, e8 都是极小边覆盖都是极小边覆盖, 也也都是最小边覆盖都是最小边覆盖, 1 = 3。18 设设
20、G = , 若若E*(E* E)中任何两条边均不相邻中任何两条边均不相邻, 则称则称E*为为G中中边独立集边独立集边独立集边独立集, 也称也称E*为为G中的中的匹配匹配匹配匹配(Matching);若在若在E*中加入任意一条边所得集合都不是匹配中加入任意一条边所得集合都不是匹配, 则称则称E*为为极大极大极大极大匹匹匹匹配配配配;边数最多的匹配称为边数最多的匹配称为最大最大最大最大匹配匹配匹配匹配;最大匹配的边数称为最大匹配的边数称为边独立数边独立数边独立数边独立数或或匹配数匹配数匹配数匹配数, 记作记作 1 1(G)(G), 简记为简记为 1 1。定义定义7.5 匹配匹配匹配匹配图图(a)中
21、，中，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 都是极大匹配都是极大匹配, 也也都是最大匹
22、配都是最大匹配, 1 = 2。20例：飞行员搭配问题例：飞行员搭配问题1 1最大匹配问题最大匹配问题飞行大队有若干个来自各地的飞行员，专门驾驶一种型号的飞机，飞行大队有若干个来自各地的飞行员，专门驾驶一种型号的飞机，这种飞机每架有两个飞行员。由于种种原因，例如互相配合的这种飞机每架有两个飞行员。由于种种原因，例如互相配合的问题，有些飞行员不能在同一架飞机上飞行，问如何搭配飞行问题，有些飞行员不能在同一架飞机上飞行，问如何搭配飞行员，才能使员，才能使出航的飞机最多出航的飞机最多出航的飞机最多出航的飞机最多。为简单起见，设有为简单起见，设有1010个飞行员，图个飞行员，图(a)(a)中的中的V V
23、1 1,V,V2 2, ,V V1010就代表这就代表这1010个飞行员。如果个飞行员。如果两个人可以同机飞行，就在他们之间连一条两个人可以同机飞行，就在他们之间连一条两个人可以同机飞行，就在他们之间连一条两个人可以同机飞行，就在他们之间连一条线线线线，否则就不连。，否则就不连。V9V3V1V2V4V5V7V6V8V10(a)图图(a)(a)中的中的3 3条蓝色的粗线代表条蓝色的粗线代表一种搭配方案。由于一个飞行一种搭配方案。由于一个飞行员不能同时派往两架飞机，因员不能同时派往两架飞机，因此此任何两条粗线不能有公共端任何两条粗线不能有公共端任何两条粗线不能有公共端任何两条粗线不能有公共端点点点
24、点。称一个图中没有公共端点。称一个图中没有公共端点的一组边成为一个的一组边成为一个“匹配匹配匹配匹配”。因此上述问题就转化为：因此上述问题就转化为：如何如何如何如何找一个包含最多边的匹配找一个包含最多边的匹配找一个包含最多边的匹配找一个包含最多边的匹配，这，这个问题叫图的个问题叫图的最大匹配问题最大匹配问题最大匹配问题最大匹配问题。21例：飞行员搭配问题例：飞行员搭配问题2 2二部图的最大匹配问题二部图的最大匹配问题在例在例1 1中，如果飞行员分成两部分，一部分是正驾驶员，一中，如果飞行员分成两部分，一部分是正驾驶员，一部分是副驾驶员。如何搭配正副驾驶员才能使得出航飞机部分是副驾驶员。如何搭配
25、正副驾驶员才能使得出航飞机最多的问题可以归结为一个二部图上的最大匹配问题。最多的问题可以归结为一个二部图上的最大匹配问题。例如，假设有例如，假设有4 4个正驾驶员，有个正驾驶员，有5 5个副驾驶员，飞机必须要个副驾驶员，飞机必须要有一名正驾驶员和一名副驾驶员才能起飞。正驾驶员和副有一名正驾驶员和一名副驾驶员才能起飞。正驾驶员和副驾驶员之间存在搭配的问题。驾驶员之间存在搭配的问题。Y1Y2Y3Y4Y5X1X2X3X4(b)图图(b)中，中，X1,X2,X3,X4表示表示4个个正驾驶员，正驾驶员，Y1,Y2,Y3,Y4,Y5表示表示5个副驾驶员。正驾驶员之间个副驾驶员。正驾驶员之间不能搭配，副驾驶
26、员之间也不不能搭配，副驾驶员之间也不能搭配，所以这是一个能搭配，所以这是一个二部图二部图二部图二部图。图图(b)中的中的4条蓝色的粗线代表条蓝色的粗线代表一种搭配方案。这个问题实际一种搭配方案。这个问题实际上是求一个二部图的上是求一个二部图的最大匹配最大匹配最大匹配最大匹配。22定义定义7.6 二部图二部图二部图二部图( (二分图二分图二分图二分图) )二部图二部图二部图二部图：如果图：如果图G是一个简单图，它的顶点集合是一个简单图，它的顶点集合V是由两个没是由两个没有公共元素的子集有公共元素的子集X=X1,X2,.,Xm与子集与子集Y=Y1,Y2,Yn，并，并且且Xi与与Xj(1i,jm)之
27、间，之间，Ys与与Yt(1s,tm)之间没有边连接，则之间没有边连接，则G称为称为二部图二部图二部图二部图。23 对于一个图对于一个图G与给定的一个匹配与给定的一个匹配M，如果图，如果图G中不存在中不存在M的未的未盖点盖点(未盖点的定义见未盖点的定义见7.3节节)，则称匹配，则称匹配M为图为图G的的完美匹配完美匹配完美匹配完美匹配。图图(a)中中, M = e1, e4, e7 为完美匹配为完美匹配(最大匹配最大匹配), 它也是最小边覆盖。它也是最小边覆盖。图图(b)中不可能有完美匹配中不可能有完美匹配, 因此因此, 对对任何匹配都存在未盖点。任何匹配都存在未盖点。定义定义7.6 完美完美完美
28、完美( (完备完备完备完备) )匹配匹配匹配匹配24任取一个最大匹配任取一个最大匹配, 比如比如: M = e2, e4 , 则则M e6 , M e8 , M e7 都都是图的最小边覆盖。是图的最小边覆盖。任取一个最小边覆盖任取一个最小边覆盖, 比如比如: W = e1, e3, e6 , 从中移去一条相邻的边从中移去一条相邻的边, 则则 e1, e3 和和 e1, e6 都是图的最大匹配。都是图的最大匹配。我们通常这样来做我们通常这样来做: 用最大匹配通过增加关联未盖点的边获得最小边覆盖用最大匹配通过增加关联未盖点的边获得最小边覆盖;用最小边覆盖通过移去相邻的一条边获得最大匹配。用最小边覆
29、盖通过移去相邻的一条边获得最大匹配。(详见定理详见定理7.3)25定理定理7.3 设设n阶图阶图G中无孤立点。中无孤立点。(1) 设设M为为G的一个最大匹配的一个最大匹配, 对于对于G中每个中每个M的未盖点的未盖点v, 由与由与v关联关联的边所组成的边集的边所组成的边集N, 则则W = MN为为G中最小边覆盖中最小边覆盖;(2) 设设W1为为G的最小边覆盖的最小边覆盖, 若若G中存在相邻的边就移去其中的一条中存在相邻的边就移去其中的一条, 设移去的边集为设移去的边集为N1, 则则M1 = W1 - N1为为G中一个最大匹配中一个最大匹配;(3) G中边覆盖数中边覆盖数 1与匹配数与匹配数 1,
30、 满足满足: 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中的其它边相中的其它边相关联关联, 因此因此, 在由在由W1构造构造M1时时, 每移去相邻两条边中的一条时每移去相邻两条边中的一条时, 将只产生一个将只产生一个M的未盖点。的未
31、盖点。所以所以, |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, 且且 1+ 1 = n。由此可知由此可知: M1是最大匹配是最大匹配, W是最小边覆盖是最小边覆盖, 且结论且结论(3)成立。成立。证：证：26由定理由定理7.3中的中
32、的(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阶无孤立点的图阶无孤立点的图, M为为G中的匹配中的匹配, W是是G中中的边覆盖的边覆盖, 则则|M| |W|; (|M|表示表示M中边的数目中边的数目)当等号成立时当等号成立时, M为为G中完美匹配中完
33、美匹配, W为为G中最小边覆中最小边覆盖。盖。证：证：27右图右图(a)中的中的 e1, e4, e7 为完美匹配为完美匹配, 也是最小边覆盖。也是最小边覆盖。在下图在下图(a)中中, M1 = e3, e7 和和M2 = e2, e4, e6 都是其极大匹配。都是其极大匹配。下图下图(b)和和(c)中实线边所示。中实线边所示。M1不是不是最大匹配最大匹配, M2是最大匹配是最大匹配(也是完美匹配也是完美匹配)。 = e2e3e4e7e6是关于是关于M1的可增广路径。的可增广路径。M2没有可增广没有可增广路径。路径。287.3 匹配问题的求解为了求解各种匹配问题，必须引入一系列概念：为了求解各
34、种匹配问题，必须引入一系列概念：V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a) 未盖点未盖点未盖点未盖点 设设Vi是图是图G = 的一个顶点，的一个顶点，M是图是图G中一个给定的匹中一个给定的匹配，如果配，如果Vi不与任意一条属于匹配不与任意一条属于匹配M的边相关联，则称的边相关联，则称Vi是匹配是匹配M的的未盖点未盖点未盖点未盖点。很形象：没有被匹配。很形象：没有被匹配M中的边中的边“盖住盖住”。取定取定M=e4, e6, e10(由粗线组由粗线组成的匹配成的匹配)，则图，则图(a)中，中，V10就就是是M的一个未盖点。的一
35、个未盖点。29V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a) 交错轨交错轨交错轨交错轨 设设P是图是图G的一条轨的一条轨(路径路径)，如果，如果P的任意两条相邻的边一定是的任意两条相邻的边一定是一条属于匹配一条属于匹配M而另一条不属于而另一条不属于M，则称，则称P是一条是一条交错轨交错轨交错轨交错轨。在图在图(a)中，取定中，取定M=e4, e6, e10(由粗线组成的匹配由粗线组成的匹配)，则图，则图(b)、(c)所示的路径都是交错轨。所示的路径都是交错轨。特别地，如果轨特别地，如果轨P仅含一条边，那么无论这条边是否属于匹配
36、仅含一条边，那么无论这条边是否属于匹配M，P一定是一条交错轨。一定是一条交错轨。V1V5V9V11V6V2e1e4e7e10e12(b)V9V6V7V3V4e3e6e8e10(c)30V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a) 可增广轨可增广轨可增广轨可增广轨 两个端点都是未盖点的两个端点都是未盖点的交错轨交错轨交错轨交错轨称为称为可增广轨可增广轨可增广轨可增广轨。图图(b)所示的交错轨的两个端点所示的交错轨的两个端点V2, V11都是匹配都是匹配M的未盖点，的未盖点，所以这条轨是可增广轨，而图所以这条轨是可增广轨，而图(
37、c)所示的交错轨不是可增广轨。所示的交错轨不是可增广轨。特别地，如果两个未盖点之间仅含一条边，那么单单这条边特别地，如果两个未盖点之间仅含一条边，那么单单这条边也组成一条可增广轨。也组成一条可增广轨。V1V5V9V11V6V2e1e4e7e10e12(b)V9V6V7V3V4e3e6e8e10(c)31V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a)V1V5V9V11V6V2e1e4e7e10e12(b)V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(d)可增广轨的含
38、义可增广轨的含义可增广轨的含义可增广轨的含义 对于图对于图G的一个匹配的一个匹配M来说，如果能找到一条来说，如果能找到一条可增广轨可增广轨可增广轨可增广轨P，那么，那么这个匹配这个匹配M一定可以通过下述方法改进成一个包含多一条边的一定可以通过下述方法改进成一个包含多一条边的匹配匹配Ms(即匹配即匹配M扩充了扩充了)：把把把把P P中原来属于匹配中原来属于匹配中原来属于匹配中原来属于匹配MM的边从匹配的边从匹配的边从匹配的边从匹配MM中去掉中去掉中去掉中去掉( (粗边改成细边粗边改成细边粗边改成细边粗边改成细边) )，而把而把而把而把P P中原来不属于中原来不属于中原来不属于中原来不属于MM的边
39、加到匹配的边加到匹配的边加到匹配的边加到匹配MsMs中去中去中去中去( (细边改成粗边细边改成粗边细边改成粗边细边改成粗边) )，变化后的匹配变化后的匹配变化后的匹配变化后的匹配MsMs恰好比原匹配恰好比原匹配恰好比原匹配恰好比原匹配MM多一条边。多一条边。多一条边。多一条边。如图如图(a)中图中图G的一个匹配的一个匹配M，找到图，找到图(b)所示的一条可增广轨，所示的一条可增广轨，那么得到图那么得到图(d)所示的新匹配所示的新匹配Ms。Ms比比M多一条边。多一条边。32证：证：1) 必要性必要性假设假设: M为为G中最大匹配。中最大匹配。若若G中存在中存在M的可增广路径的可增广路径 , 则则
40、 中在中在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中的最大匹配。中的最大匹配。下面证明下面证明: |M| = |M1|。设
41、设: H = GM1 M。当当H = 时时显然显然, M = M1, 所以所以, M为为G中最大匹配。中最大匹配。若若H 时时由于由于M和和M1都是匹配都是匹配, 所以所以, H各连通分支要么是由各连通分支要么是由M和和M1中中的边组成的交错圈的边组成的交错圈, 在交错圈上在交错圈上M和和M1中的边数相等中的边数相等, 要么为由要么为由M和和M1的边组成的交错路径。的边组成的交错路径。由已知条件可知由已知条件可知: M不含可增广路径不含可增广路径, M1是最大匹配。由必是最大匹配。由必要性可知要性可知: M1中也无可增广的交错路径。中也无可增广的交错路径。所以所以, 在由在由M和和M1组成的交
42、错路径上组成的交错路径上, M和和M1的边也相等的边也相等, 即即: M与与M1边的个数相同。边的个数相同。因此因此, M为最大匹配。为最大匹配。34求最大匹配的可行方法：给定一个初始匹配给定一个初始匹配M(如果没有给定，则如果没有给定，则M)，如果图，如果图G没有未盖点，则肯定不会有可增广轨了，即没有未盖点，则肯定不会有可增广轨了，即M就是最大匹就是最大匹配。配。对图对图G的所有未盖点的所有未盖点Vi，通过，通过一定的方法一定的方法一定的方法一定的方法搜索以搜索以Vi为端点的为端点的可增广轨，从而通过可增广轨逐渐把可增广轨，从而通过可增广轨逐渐把M扩大。扩大。(在扩大在扩大M的的过程当中，某
43、些未盖点会逐渐被过程当中，某些未盖点会逐渐被M盖住盖住)35寻找可增广轨的方法 交错可达交错可达交错可达交错可达 设设M是图是图G的一个匹配，的一个匹配，Vi是取定的未盖点，如果存在从是取定的未盖点，如果存在从Vi到到Vj的交错轨，则称的交错轨，则称由由由由V Vi i交错可达交错可达交错可达交错可达V Vj j。以图以图(d)为例，如果取定了未盖点为例，如果取定了未盖点V4，那么存在着交错轨那么存在着交错轨P=V4, V3, V7, V6，因此，因此由由由由V V4 4交错可达交错可达交错可达交错可达V V6 6，同样，同样由由由由V V4 4还还还还交错可达交错可达交错可达交错可达V V7
44、 7等等。等等。等等。等等。V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(d)寻找以寻找以Vi为端点的可增广轨的方法：设法把由为端点的可增广轨的方法：设法把由Vi交错可达的顶点都找出交错可达的顶点都找出来，每找到一个，就检查一下它是不是未盖点，如果是，则可增广轨就来，每找到一个，就检查一下它是不是未盖点，如果是，则可增广轨就找到了。如果已经把所有由找到了。如果已经把所有由Vi交错可达的顶点都找出来了，而其中没有交错可达的顶点都找出来了，而其中没有一个是未盖点，就可以肯定以一个是未盖点，就可以肯定以Vi为一端的可增广轨一定不存在了。
45、为一端的可增广轨一定不存在了。36为了把由为了把由Vi交错可达的顶点都找出来，需要引入交错树的概念交错可达的顶点都找出来，需要引入交错树的概念 交错树交错树交错树交错树 设设M是图是图G=V,E的一个取定的匹配，的一个取定的匹配，T是图是图G的一个子图，如的一个子图，如果果T具有下述性质：具有下述性质： (1) T是一棵树；是一棵树； (2) T中存在一个顶点中存在一个顶点Vi，它是未盖点；，它是未盖点； (3) 对于对于T的任意一个不同于的任意一个不同于Vi的顶点来说，的顶点来说，T中连接中连接Vi与与Vj的唯的唯一轨是交错轨。一轨是交错轨。 那么称那么称T是一个以是一个以Vi为根的为根的交
46、错树交错树交错树交错树。V15V6V5V4V3V2V1V12V13V14V11V8V7V9V10(a)V5V4V3V2V1V8V7(b) T+图图(a)中粗边代表一个匹中粗边代表一个匹配。图配。图(b)所示的子图就所示的子图就是一个以是一个以V1为根的交错为根的交错树。树。37为了描述如何扩大一个交错树，需要介绍有关顶点分类的概念为了描述如何扩大一个交错树，需要介绍有关顶点分类的概念 内点、外点内点、外点内点、外点内点、外点 交错树交错树T的顶点可以分成两类：的顶点可以分成两类： 外点：即图外点：即图(b)中标中标+号的顶点，如果号的顶点，如果Vj是外点，则连接根是外点，则连接根Vi与与Vj的
47、交错轨一定的交错轨一定含偶数条边含偶数条边含偶数条边含偶数条边，且，且P上与上与Vj关联的边一定关联的边一定属于属于属于属于匹配匹配匹配匹配MM。 内点：即图内点：即图(b)中标中标号的顶点，如果号的顶点，如果Vj是内点，则连接根是内点，则连接根Vi与与Vj的交错轨一定的交错轨一定含奇数条边含奇数条边含奇数条边含奇数条边，且，且P上与上与Vj关联的边一定关联的边一定不属不属不属不属于匹配于匹配于匹配于匹配MM。V5V4V3V2V1V8V7(b) T+图图(b)中中V1、V3、V5、V7为外为外点，而点，而V2、V4、V8为内点。为内点。38扩大以Vi为根的交错树的方法看看图看看图G中有没有与交
48、错树中有没有与交错树T的外点关联而不属于的外点关联而不属于T的边的边e，如果有，如果有，就看看就看看e的另一个端点的另一个端点Vk是不是属于是不是属于T(肯定不属于肯定不属于T)，如果，如果Vk不属不属于于T，那么就可以把，那么就可以把e和和Vk都加入到都加入到T中，使中，使T扩大。在扩大的时候，扩大。在扩大的时候，还可以分为两种情况：还可以分为两种情况：Vk是未盖点，这时，把是未盖点，这时，把e与与Vk加入到加入到T中后，中后，T中连接根中连接根Vi与与Vk的交错路的交错路是一条可增广轨。是一条可增广轨。(见下图见下图(a)Vk不是未盖点，也就是说，有一条属于匹配不是未盖点，也就是说，有一条
49、属于匹配M的边的边e e 与与Vk关联，这时，关联，这时，在把在把e与与Vk加入到加入到T中后，还可以把中后，还可以把e e 以及它的端点以及它的端点Vm加入到加入到T中去，中去，因为很显然从因为很显然从Vi也交错可达也交错可达e e 的另一端点的另一端点Vm。另外，。另外，Vk应该是内点，应该是内点，而而Vm是外点。是外点。(见下图见下图(b)(b)Vi+Vje+VkVmeVi+未盖点未盖点Vje(a)Vk39V1(a)+(e)V5V4V3V2V1V8V7+V15V6+eeV3V2V1(b)+eeV5V4V3V2V1V8V7(d)+eeV5V4V3V2V1(c)+ee下面图下面图(a)、(b
50、)、(c)、(d)、(e)给出了从给出了从V1出发扩展交错树的具体过程。出发扩展交错树的具体过程。对于图对于图(e)所示的交错树，不能再用上述方法扩大了，因为找不到一条所示的交错树，不能再用上述方法扩大了，因为找不到一条不属于不属于T的边的边e，这条边与，这条边与T的某个外点关联，且的某个外点关联，且e的另一个端点的另一个端点Vk也不也不属于属于T。但能不能就此断定以但能不能就此断定以V1为一端的可增广轨一定不存在呢？答案是否定为一端的可增广轨一定不存在呢？答案是否定的的(见下页见下页)。40V15V6V5V4V3V2V1V12V13V14V11V8V7V9V10(f)对于图对于图(e)中的交
51、错树，已经无法扩大了，但中的交错树，已经无法扩大了，但以以V1为一端的可增广轨是存在的。在图为一端的可增广轨是存在的。在图(f)中中用虚线标出的用虚线标出的(V1,V2,V3,V4,V5,V7,V8,V9)就是就是一条连接一条连接V1和和V9的可增广轨。的可增广轨。(e)V5V4V3V2V1V8V7+V15V6+ee41 带花树带花树带花树带花树 如果发现了一条不属于交错树如果发现了一条不属于交错树T的边的边e，e的两个端点都是的两个端点都是T的外的外点，那么把点，那么把e加到加到T中去得到的图叫做中去得到的图叫做带花树带花树带花树带花树。(e)V5V4V3V2V1V8V7+V15V6+ee例
52、如在图例如在图(e)中，连接中，连接T的两个顶点的两个顶点V5与与V7的这条的这条边边e(图中的红边图中的红边)原不属于原不属于T，现在把，现在把e加到加到T中去，中去，只不过是使只不过是使T增加了一条边，没有扩大由增加了一条边，没有扩大由Vi交错交错可达的顶点的范围，反而使得可达的顶点的范围，反而使得T不再是树了。不再是树了。带花树的特点是，它恰好有一个圈，这唯一的圈带花树的特点是，它恰好有一个圈，这唯一的圈称为带花树的花。圈内包含奇数条边。称为带花树的花。圈内包含奇数条边。带花树的作用见带花树的作用见“7.3.4 任意图的最大匹配任意图的最大匹配”42匹配问题匹配问题可以分为如下类型：匹配
53、问题可以分为如下类型：1.二部图的最大匹配；二部图的最大匹配；2.二部图的完备匹配；二部图的完备匹配；3.二部图的最佳匹配；二部图的最佳匹配；4.任意图的最大匹配；任意图的最大匹配；每种匹配问题的解法不一样，难度也不一样。每种匹配问题的解法不一样，难度也不一样。437.3.1 二分图的最大匹配求二部图的最大匹配的算法有：求二部图的最大匹配的算法有：1.网络流解法网络流解法2.匈牙利算法匈牙利算法3.Hopcroft-Karp算法算法(匈牙利算法的改进匈牙利算法的改进)441 网络流解法1)从二部图从二部图G出发构造一个网络出发构造一个网络G：a)增加一个源点增加一个源点S和汇点和汇点T；b)从
54、从S向向X的每一个顶点都画一条有向弧，从的每一个顶点都画一条有向弧，从Y的每一个顶点的每一个顶点都向都向T画一条有向弧；画一条有向弧；c)原来原来G中的边都改成有向弧，方向是从中的边都改成有向弧，方向是从X的顶点指向的顶点指向Y的顶的顶点；点；d)令所有弧的容量都等于令所有弧的容量都等于1。2)求网络求网络G的最大流的最大流F。3)从从X的顶点指向的顶点指向Y的顶点的弧集合中，弧流量为的顶点的弧集合中，弧流量为1的弧对应二部图的的弧对应二部图的匹配边，最大流值匹配边，最大流值F对应二部图的最大匹配的边数。对应二部图的最大匹配的边数。思考：思考：思考：思考：为什么这样构造的网络求出来的最为什么这
55、样构造的网络求出来的最大流就是最大匹配？大流就是最大匹配？Answer:Answer:(1)网络中所有的弧容量均为网络中所有的弧容量均为1。(2)尽管在网络中顶点尽管在网络中顶点Xi可能发出多条边，但可能发出多条边，但在最大流中只能选择一条边；在最大流中只能选择一条边；(3)尽管在网络中可能有多条边进入顶点尽管在网络中可能有多条边进入顶点Yi，但在最大流中只能选择一条边；但在最大流中只能选择一条边；(4)以上第以上第(2)、(3)点保证了最大流中二部图中点保证了最大流中二部图中的边不存在共同顶点。的边不存在共同顶点。X1 Xi XnSY1 Yi YnT45其中其中 表示工人。表示工人。 表示工
56、作。表示工作。网络流解法实例：网络流解法实例：网络流解法实例：网络流解法实例：例：设有例：设有5位待业者，位待业者，5项工作，他们各自能胜任工作的情况项工作，他们各自能胜任工作的情况如下图所示，要求设计一个就业方案，使尽量多的人能就业。如下图所示，要求设计一个就业方案，使尽量多的人能就业。46按照前面描述的方法构造网络流按照前面描述的方法构造网络流(如上图所示如上图所示)：在二部图中：在二部图中增加两个顶点增加两个顶点 分别作为源点、汇点。并用有向分别作为源点、汇点。并用有向边把它们与原二部图中顶点相连，令全部边上的容量均为边把它们与原二部图中顶点相连，令全部边上的容量均为1。当网络流达到最大
57、时，如果在最大流中当网络流达到最大时，如果在最大流中 上的流上的流量为量为1，就让，就让 作作 工作，此即为最大匹配方案。工作，此即为最大匹配方案。47第一次标号。第一次标号。调整调整48第二次标号。第二次标号。再调整。再调整。49第三次标号。第三次标号。50调整。调整。51第四次标号。第四次标号。52调整调整53第五次标号。第五次标号。54标号过程已无法再继续。标号过程已无法再继续。55工人工人分别作分别作故最多安排四个人工作。故最多安排四个人工作。流量为流量为1的画彩线即所求的最大匹配。的画彩线即所求的最大匹配。562 匈牙利算法(Edmonds, 1965)匈牙利算法的原理为：从当前匹配
58、匈牙利算法的原理为：从当前匹配(如果没有匹配，则初如果没有匹配，则初始匹配为始匹配为0)出发，检查每一个未盖点，然后从它出发寻找可增出发，检查每一个未盖点，然后从它出发寻找可增广路，找到可增广路，则沿着这条可增广路进行扩充，直到不广路，找到可增广路，则沿着这条可增广路进行扩充，直到不存在可增广路为止。存在可增广路为止。根据从未盖点出发寻找可增广路搜索的方法，可以分为：根据从未盖点出发寻找可增广路搜索的方法，可以分为：1) DFS 增广增广2) BFS增广增广3) 多增广路多增广路(Hopcroft-Karp算法算法)在算法中用到的一些变量如下：在算法中用到的一些变量如下：int nx, ny;
59、/X和和Y集合中顶点的个数集合中顶点的个数int gmaxnmaxn;/邻接矩阵邻接矩阵, X集合和集合和Y集合中顶点间边的信息集合中顶点间边的信息int cxmaxn , cymaxn;/cxi表示最终求得的最大匹配中与表示最终求得的最大匹配中与Xi匹配的匹配的Y顶点顶点, cyi同理同理571) DFS 增广/DFS算法中记录顶点访问的状态算法中记录顶点访问的状态/如果如果mki=0表示未访问过，如果为表示未访问过，如果为1表示访问过表示访问过int mkmaxn ;/从从X集合中的顶点集合中的顶点u出发用深度优先的策略寻找增广路出发用深度优先的策略寻找增广路/(这种增广路只能使当前的匹配
60、数增加这种增广路只能使当前的匹配数增加1)int path(int u)for(int v = 0 ; v ny ; v+) /考虑所有考虑所有Yi顶点顶点vif(guv & !mkv)mkv = 1; /如果如果v没有匹配没有匹配,或者如果或者如果v已经匹配了，已经匹配了，/但从但从yv出发可以找到一条增广路出发可以找到一条增广路if(cyv = -1 | path(cyv)cxu = v; /把把v匹配给匹配给ucyv = u; /把把u匹配给匹配给vreturn 1; /找到可增广路找到可增广路return 0 ; /如果不存在从如果不存在从u出发的增广路出发的增广路58int MaxM
61、atch() /求二部图最大匹配的匈牙利算法求二部图最大匹配的匈牙利算法int res(0) ;memset(cx , 0xff , sizeof(cx) ; /从从0匹配开始增广匹配开始增广memset(cy , 0xff , sizeof(cy) ;for(int i = 0 ; i = nx ; i+)if(cxi = -1) /从每个未盖点出发进行寻找增广路从每个未盖点出发进行寻找增广路memset(mk , 0 , sizeof(mk) ;res += path(i) ; /每找到一条增广路，可使得匹配数加每找到一条增广路，可使得匹配数加1return res ;优点：实现简洁，理解
62、容易优点：实现简洁，理解容易适用：稠密图，由于边多，适用：稠密图，由于边多，dfs找增广路很快找增广路很快复杂度：复杂度：O(n3)59例题：ZOJ 1654 解题报告602) BFS 增广int predmaxn , mkmaxn , openmaxn ;int MaxMatch() int i , u , v , t , d , e , cur , tail , res(0); memset(mk , 0xff , sizeof(mk) ; memset(cx , 0xff , sizeof(cx) ; memset(cy , 0xff , sizeof(cy) ;适用：稀疏二分图，边少，
63、增广路短适用：稀疏二分图，边少，增广路短复杂度：复杂度：O(n3)61 for (i = 0 ; i nx ; i+) predi = -1 ; for (opencur = tail = 0 = i ; cur = tail & cxi = -1 ; cur+) for (u = opencur , v = 0 ; v = 0) predopentail = u ; continue ; for (d = u , e = v ; d != -1 ; t = cxd, cxd = e, cye = d, e = t, d = predd); if (cxi != -1) res+ ; /end
64、 of for return res ;623)多增广路：Hopcroft-Karp算法(1972)int predmaxn , mkmaxn , openmaxn , srcmaxn ;int MaxMatch() int i , u , v , t , d , e , cur , tail , res(0) , p , flag ; memset(mk , 0xff , sizeof(mk); memset(cx , 0xff , sizeof(cx); memset(cy , 0xff , sizeof(cy) ; for (p = 1 , flag = 1 ; flag ; p+) f
65、lag = 0 ; for (cur = tail = 0 , i = 0 ; i nx ; i +) if (cxi = -1) open+tail = i , predi = -1 , srci = i ; 这是一类方法，每次增广同时寻找多条不相交增广路，由这是一类方法，每次增广同时寻找多条不相交增广路，由Hopcroft和和Karp于于1973年提出，有非常优秀的时间界。年提出，有非常优秀的时间界。以下代码由以下代码由BFS的框架直接修改而来：的框架直接修改而来：63 for ( ; cur = tail ; cur+) u = opencur ; if (cxsrcu != -1) c
66、ontinue ; for (v = 0 ; v = 0) predopentail = u ; srcopentail = srcu ; continue ; for (tail- , flag = 1 , d = u , e = v ; d != -1 ; t = cxd , cxd = e , cye = d , e = t , d = predd) ; /end of for /end of for for (i = 0 ; i n ; i+) res += (cxi != -1) ; return res ;还可以用还可以用DFS来找多增广路。根据图的稠密程度，来考虑用哪种实现。来找
67、多增广路。根据图的稠密程度，来考虑用哪种实现。优点：复杂度低，实现相对简单优点：复杂度低，实现相对简单复杂度：复杂度：O(n2.5)应用：这种方法还可以应用到类似二分图的网络中，或者多部的网络中，求最应用：这种方法还可以应用到类似二分图的网络中，或者多部的网络中，求最大流。可以极高的加快程序的运行。大流。可以极高的加快程序的运行。647.3.2 二部图的完备匹配问题的提出：某公司有工作人员X1,X2,Xm，他们去做工作Y1,Y2,Y3,Yn，每个人适合做其中一项或几项工作，问能否每个人都分配到一都分配到一都分配到一都分配到一项项合适的工作合适的工作合适的工作合适的工作？65定义定义7.7 完备
68、匹配完备匹配完备匹配完备匹配 设设G = 为二部图为二部图, |V1| |V2|, M为为G中中一个最大匹配一个最大匹配, 且且|M| = |V1|, 则称则称M为为V1到到V2的的完备匹配完备匹配;若若|V1| = |V2|, 则完备匹配为完美匹配则完备匹配为完美匹配;若若|V1| |V2|, 则完备匹配为则完备匹配为G中最大匹配。中最大匹配。下图下图(a)和和(b)都存在完备匹配都存在完备匹配(实线边所示实线边所示)。图图(c)中没有完备匹配中没有完备匹配, 实线边组成集合是最大匹配实线边组成集合是最大匹配, 但不是完备匹配。但不是完备匹配。667.3.3 二部图的最佳匹配问题的提出：在第
69、3节完备匹配中例举的分工问题中，工作人员可以做各项工作，但效率未必一致，我们需要制定一个分工方案，使公司的总总效益最大效益最大效益最大效益最大，这就是最佳分配最佳分配最佳分配最佳分配问题问题。数学模型：G是加权二部图，顶点划分成两个集合，工作人员集合X=X1,X2,.,Xm，工作集合Y=Y1, Y2 , Yn，W(Xi,Yj)0表示工作人员Xi做工作Yj时的效益，求权值总权值总和最大和最大和最大和最大的完备匹配称为二部二部二部二部图图的最佳匹配的最佳匹配的最佳匹配的最佳匹配。67KM算法(Kuhn和Munkres, 1957)687.3.4 任意图的最大匹配69ZOJ试题(图的匹配)1059 Whats In a Name1137 Girls and Boys1140 Courses1197 Sorting Slides1525 Air Raid70人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。71
