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

第7章支配集、覆盖集、独立集与匹配本讲内容会涉及以下容易相互混淆的内容：点支配集,极小点支配集,最小点支配集,点支配数

0(G);支配的概念；点独立集,极大点独立集,最大点独立集,点独立数

0(G);点覆盖集,极小点覆盖集,最小点覆盖集,点覆盖数

0(G);覆盖的概念；边覆盖集,极小边覆盖集,最小边覆盖集,边覆盖数

1(G);边独立集(匹配),极大边独立集(极大匹配),最大边独立集(最大匹配),边独立数(或匹配数)

1(G);以上几个量存在以下关系：

0＋

0

＝n，即：点覆盖数+点独立数=n

1＋

1

＝n，即：边覆盖数+边独立数=n对二部图，还有以下关系式：二部图的最小点覆盖数

0＝等于最大匹配数

1。ZOJ1364二部图的最大点独立数

0＝顶点个数n－最大匹配数

1。(前提是该二部图没有孤立顶点，如果有孤立顶点，对这些孤立顶点要单独考虑)ZOJ11377.1点支配集、点覆盖集、点独立集

(都是顶点的集合)定义7.1

支配与支配集设图G=<V,E>,V*

V,若对于

vi

V-V*,

vj

V*,使得:(vi,vj)

E,则称vj支配vi,并称V*为G的一个支配集;若支配集V*的任何真子集都不是支配集,则称V*是极小支配集;顶点数最少的支配集称为最小支配集;最小支配集中的顶点数称为支配数,记作

0(G)或简记为

0。图(a)中，V*={v1,v5}就是一个支配集。因为V-V*={v2,v3,v4,v6,v7}中的顶点都是V*中顶点的邻接顶点。通俗地讲，所谓支配集，就是V中的顶点要么是V*集合中的元素，要么与V*中的一个顶点相邻。在图(a)中,{v1,v5},{v3,v5}和{v2,v4,v7}都是极小支配集,{v1,v5},{v4,v5}和{v3,v6}都是最小支配集,

0=2。图(b)为7阶星形图,{v0},{v1,v2,...,v6}为极小支配集,{v0}为最小支配集,

0=1。图(c)为轮图W6,{v0},{v1,v3},{v1,v4}等都是极小支配集,显然,

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

设图G=<V,E>,V*

V,若V*中任何两个顶点均不相邻,则称V*为G的点独立集,或称独立集;若在V*中加入任何顶点都不再是独立集,则称V*为极大点独立集;顶点数最多的点独立集称为最大点独立集;最大点独立集的顶点数称为点独立数,记作

0(G),简记为

0。定义7.2

点独立集图(a)中，V*={v1,v5}就是一个点独立集，因为v1和v5是不相邻的。图(a)中,{v1,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}是极大点独立集,也都是最大点独立集,

0＝2。

设G=<V,E>,V*

V,若对于

e

E,

v

V*,使得:v与e相关联,则称v覆盖e,并称V*为G的点覆盖集或简称点覆盖;若点覆盖V*的任何真子集都不是点覆盖,则称V*是极小点覆盖;顶点个数最少的点覆盖称为最小的点覆盖;最小点覆盖的顶点数称为点覆盖数,记作

0(G),简记为

0。定义7.3

覆盖与点覆盖集图(a)中，V*={v1,v3,v5,v7}就是一个点覆盖集。通俗地讲，所谓点覆盖集V*，就是G中所有的边至少有一个顶点属于V*(顶点覆盖边)。图(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。点支配集、点独立集、点覆盖集之间的联系定理7.1：设G=<V,E>中无孤立点，则G的极大点独立集都是G的极小支配集。逆命题不成立(即极小支配集未必是极大独立集)。一个独立集是极大独立集，当且仅当它是一个支配集。定理7.2：设G=<V,E>中无孤立点,V*(V*

V)为G的点覆盖,当且仅当V-V*为G的点独立集。推论：设G是n阶无孤立点的图，则V*是G的极小(最小)点覆盖，当且仅当V-V*是G的极大(最大)点独立集，从而有

0+

0=n(顶点个数)。

设G=<V,E>中无孤立点,则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*-V1*中的顶点都不受V1*中的顶点支配,即:V1*不是支配集。所以,V*是极小支配集。证：上面定理的逆命题是不成立的。在右图中,{v3,v5}是极小支配集,但它不是独立集,更不是极大独立集。定理7.1

设G=<V,E>中无孤立点,V*(V*

V)为G的点覆盖,当且仅当V-V*为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的极小(最小)点覆盖,当且仅当V-V*是G的极大(最大)点独立集,从而有

0+

0=n(顶点个数)。定理7.2极大点独立集与极小点覆盖集的求解参见吴文虎编著的《信息学奥林匹克竞赛指导－图论的算法与程序设计(PASCAL版)》P587.2边覆盖集与匹配

(都是边的集合)定义7.4

覆盖与边覆盖集

设图G=<V,E>,E*

E,若

v

V,

e

E*,使得:v与e相关联,则称e覆盖v,并称E*为边覆盖集,或简称边覆盖;若边覆盖E*的任何真子集都不是边覆盖,则称E*是极小边覆盖;边数最少的边覆盖集称为最小的边覆盖;最小的边覆盖所含的边数称为边覆盖数,记作

1(G)或简记为

1。图(a)中，E*={e1,e4,e7}就是一个边覆盖集。通俗地讲，所谓边覆盖集E*，就是G中所有的顶点都是E*中边的顶点(边覆盖顶点)。图(a)中,{e1,e4,e7}和{e2,e5,e6,e7}都是极小边覆盖,{e1,e4,e7}是最小边覆盖,

1=3。图(b)中,{e1,e3,e6}和{e2,e4,e8}都是极小边覆盖,也都是最小边覆盖,

1=3。

设G=<V,E>,若E*(E*

E)中任何两条边均不相邻,则称E*为G中边独立集,也称E*为G中的匹配(Matching);若在E*中加入任意一条边所得集合都不是匹配,则称E*为极大匹配;边数最多的匹配称为最大匹配;最大匹配的边数称为边独立数或匹配数,记作

1(G),简记为

1。定义7.5

匹配图(a)中，E*={e1,e4,e7}就是一个匹配。所谓任何两条边均不相邻，通俗地讲，就是任何两条边都没有公共顶点。图(a)中,{e2,e6},{e3,e5},{e1,e4,e7}都是极大匹配,{e1,e4,e7}是最大匹配,

1=3。图(b)中,{e1,e3},{e2,e4},{e4,e7}都是极大匹配,也都是最大匹配,

1=2。例：飞行员搭配问题1－最大匹配问题飞行大队有若干个来自各地的飞行员，专门驾驶一种型号的飞机，这种飞机每架有两个飞行员。由于种种原因，例如互相配合的问题，有些飞行员不能在同一架飞机上飞行，问如何搭配飞行员，才能使出航的飞机最多。为简单起见，设有10个飞行员，图(a)中的V1,V2,…V10就代表这10个飞行员。如果两个人可以同机飞行，就在他们之间连一条线，否则就不连。V9V3V1V2V4V5V7V6V8V10(a)图(a)中的3条蓝色的粗线代表一种搭配方案。由于一个飞行员不能同时派往两架飞机，因此任何两条粗线不能有公共端点。称一个图中没有公共端点的一组边成为一个“匹配”。因此上述问题就转化为：如何找一个包含最多边的匹配，这个问题叫图的最大匹配问题。例：飞行员搭配问题2－二部图的最大匹配问题在例1中，如果飞行员分成两部分，一部分是正驾驶员，一部分是副驾驶员。如何搭配正副驾驶员才能使得出航飞机最多的问题可以归结为一个二部图上的最大匹配问题。例如，假设有4个正驾驶员，有5个副驾驶员，飞机必须要有一名正驾驶员和一名副驾驶员才能起飞。正驾驶员和副驾驶员之间存在搭配的问题。Y1Y2Y3Y4Y5X1X2X3X4(b)图(b)中，X1,X2,X3,X4表示4个正驾驶员，Y1,Y2,Y3,Y4,Y5表示5个副驾驶员。正驾驶员之间不能搭配，副驾驶员之间也不能搭配，所以这是一个二部图。图(b)中的4条蓝色的粗线代表一种搭配方案。这个问题实际上是求一个二部图的最大匹配。定义7.6

二部图(二分图)二部图：如果图G是一个简单图，它的顶点集合V是由两个没有公共元素的子集X={X1,X2,..,Xm}与子集Y={Y1,Y2,…,Yn}，并且Xi与Xj(1≤i,j≤m)之间，Ys与Yt(1≤s,t≤m)之间没有边连接，则G称为二部图。

对于一个图G与给定的一个匹配M，如果图G中不存在M的未盖点(未盖点的定义见7.3节)，则称匹配M为图G的完美匹配。图(a)中,M={e1,e4,e7}为完美匹配(最大匹配),它也是最小边覆盖。图(b)中不可能有完美匹配,因此,对任何匹配都存在未盖点。定义7.6完美(完备)匹配任取一个最大匹配,比如:M={e2,e4},则M∪{e6},M∪{e8},M∪{e7}都是图的最小边覆盖。任取一个最小边覆盖,比如:W={e1,e3,e6},从中移去一条相邻的边,则{e1,e3}和{e1,e6}都是图的最大匹配。我们通常这样来做:用最大匹配通过增加关联未盖点的边获得最小边覆盖;用最小边覆盖通过移去相邻的一条边获得最大匹配。(详见定理7.3)定理7.3设n阶图G中无孤立点。(1)设M为G的一个最大匹配,对于G中每个M的未盖点v,由与v关联的边所组成的边集N,则W=M∪N为G中最小边覆盖;(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=M∪N为G中的边覆盖,且

|W|=|M|+|N|=

1+n-2

1=n-

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-

1=|W|

1。显然上式中各等号成立,所以,|M1|=

1,|W|=

1,且

1+

1=n。由此可知:M1是最大匹配,W是最小边覆盖,且结论(3)成立。证：由定理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阶无孤立点的图,M为G中的匹配,W是G中的边覆盖,则|M|

|W|;(|M|表示M中边的数目)

当等号成立时,M为G中完美匹配,W为G中最小边覆盖。证：右图(a)中的{e1,e4,e7}为完美匹配,也是最小边覆盖。在下图(a)中,M1={e3,e7}和M2={e2,e4,e6}都是其极大匹配。下图(b)和(c)中实线边所示。M1不是最大匹配,M2是最大匹配(也是完美匹配)。

=e2e3e4e7e6是关于M1的可增广路径。M2没有可增广路径。7.3匹配问题的求解为了求解各种匹配问题，必须引入一系列概念：V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a)

未盖点

设Vi是图G=<V,E>的一个顶点，M是图G中一个给定的匹配，如果Vi不与任意一条属于匹配M的边相关联，则称Vi是匹配M的未盖点。很形象：没有被匹配M中的边“盖住”。取定M={e4,e6,e10}(由粗线组成的匹配)，则图(a)中，V10就是M的一个未盖点。V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a)

交错轨

设P是图G的一条轨(路径)，如果P的任意两条相邻的边一定是一条属于匹配M而另一条不属于M，则称P是一条交错轨。在图(a)中，取定M={e4,e6,e10}(由粗线组成的匹配)，则图(b)、(c)所示的路径都是交错轨。特别地，如果轨P仅含一条边，那么无论这条边是否属于匹配M，P一定是一条交错轨。V1V5V9V11V6V2e1e4e7e10e12(b)V9V6V7V3V4e3e6e8e10(c)V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(a)

可增广轨

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

对于图G的一个匹配M来说，如果能找到一条可增广轨P，那么这个匹配M一定可以通过下述方法改进成一个包含多一条边的匹配Ms(即匹配M扩充了)：把P中原来属于匹配M的边从匹配M中去掉(粗边改成细边)，而把P中原来不属于M的边加到匹配Ms中去(细边改成粗边)，变化后的匹配Ms恰好比原匹配M多一条边。如图(a)中图G的一个匹配M，找到图(b)所示的一条可增广轨，那么得到图(d)所示的新匹配Ms。Ms比M多一条边。证：1)必要性假设:M为G中最大匹配。若G中存在M的可增广路径

,则

中在M中的边比不在M中的少1。设M’=(M∪

(E))-(M∩

(E))=M

(E),则M’中边彼此不邻,且M’比M多一条边,即:M’是比M多一条边的匹配,这就与“M是最大匹配”相矛盾。所以,M不含可增广路径。定理7.4M为G的最大匹配,当且仅当G不含M可增广路径。2)充分性设:M是G中不含可增广路径的匹配,M1是G中的最大匹配。下面证明:|M|=|M1|。设:H=G[M1

M]。当H=

时显然,M=M1,所以,M为G中最大匹配。若H

时由于M和M1都是匹配,所以,H各连通分支要么是由M和M1中的边组成的交错圈,在交错圈上M和M1中的边数相等,要么为由M和M1的边组成的交错路径。由已知条件可知:M不含可增广路径,M1是最大匹配。由必要性可知:M1中也无可增广的交错路径。所以,在由M和M1组成的交错路径上,M和M1的边也相等,即:M与M1边的个数相同。因此,M为最大匹配。求最大匹配的可行方法：给定一个初始匹配M(如果没有给定，则M＝Ø)，如果图G没有未盖点，则肯定不会有可增广轨了，即M就是最大匹配。对图G的所有未盖点Vi，通过一定的方法搜索以Vi为端点的可增广轨，从而通过可增广轨逐渐把M扩大。(在扩大M的过程当中，某些未盖点会逐渐被M盖住)寻找可增广轨的方法

交错可达设M是图G的一个匹配，Vi是取定的未盖点，如果存在从Vi到Vj的交错轨，则称由Vi交错可达Vj。以图(d)为例，如果取定了未盖点V4，那么存在着交错轨P={V4,V3,V7,V6}，因此由V4交错可达V6，同样由V4还交错可达V7等等。V1V5V10V9V11V6V7V8V3V2V4e2e1e3e4e5e6e7e8e9e10e11e12e13(d)寻找以Vi为端点的可增广轨的方法：设法把由Vi交错可达的顶点都找出来，每找到一个，就检查一下它是不是未盖点，如果是，则可增广轨就找到了。如果已经把所有由Vi交错可达的顶点都找出来了，而其中没有一个是未盖点，就可以肯定以Vi为一端的可增广轨一定不存在了。为了把由Vi交错可达的顶点都找出来，需要引入交错树的概念

交错树设M是图G={V,E}的一个取定的匹配，T是图G的一个子图，如果T具有下述性质：

(1)T是一棵树；

(2)T中存在一个顶点Vi，它是未盖点；

(3)对于T的任意一个不同于Vi的顶点来说，T中连接Vi与Vj的唯一轨是交错轨。那么称T是一个以Vi为根的交错树。V15V6V5V4V3V2V1V12V13V14V11V8V7V9V10(a)V5V4V3V2V1V8V7(b)T+–+––++图(a)中粗边代表一个匹配。图(b)所示的子图就是一个以V1为根的交错树。为了描述如何扩大一个交错树，需要介绍有关顶点分类的概念

内点、外点交错树T的顶点可以分成两类：外点：即图(b)中标‘+’号的顶点，如果Vj是外点，则连接根Vi与Vj的交错轨一定含偶数条边，且P上与Vj关联的边一定属于匹配M。内点：即图(b)中标‘–’号的顶点，如果Vj是内点，则连接根Vi与Vj的交错轨一定含奇数条边，且P上与Vj关联的边一定不属于匹配M。V5V4V3V2V1V8V7(b)T+–+––++图(b)中V1、V3、V5、V7为外点，而V2、V4、V8为内点。扩大以Vi为根的交错树的方法看看图G中有没有与交错树T的外点关联而不属于T的边e，如果有，就看看e的另一个端点Vk是不是属于T(肯定不属于T)，如果Vk不属于T，那么就可以把e和Vk都加入到T中，使T扩大。在扩大的时候，还可以分为两种情况：Vk是未盖点，这时，把e与Vk加入到T中后，T中连接根Vi与Vk的交错路是一条可增广轨。(见下图(a))Vk不是未盖点，也就是说，有一条属于匹配M的边e'与Vk关联，这时，在把e与Vk加入到T中后，还可以把e'以及它的端点Vm加入到T中去，因为很显然从Vi也交错可达e'的另一端点Vm。另外，Vk应该是内点，而Vm是外点。(见下图(b))(b)Vi+–+–––++Vje+VkVme'Vi+–+–––++未盖点Vje(a)VkV1(a)+(e)V5V4V3V2V1V8V7+–+––++V15V6–+e'eV3V2V1(b)+–+e'eV5V4V3V2V1V8V7(d)+–+––++ee'V5V4V3V2V1(c)+–+–+ee'下面图(a)、(b)、(c)、(d)、(e)给出了从V1出发扩展交错树的具体过程。对于图(e)所示的交错树，不能再用上述方法扩大了，因为找不到一条不属于T的边e，这条边与T的某个外点关联，且e的另一个端点Vk也不属于T。但能不能就此断定以V1为一端的可增广轨一定不存在呢？答案是否定的(见下页)。V15V6V5V4V3V2V1V12V13V14V11V8V7V9V10(f)对于图(e)中的交错树，已经无法扩大了，但以V1为一端的可增广轨是存在的。在图(f)中用虚线标出的(V1,V2,V3,V4,V5,V7,V8,V9)就是一条连接V1和V9的可增广轨。(e)V5V4V3V2V1V8V7+–+––++V15V6–+e'e

带花树如果发现了一条不属于交错树T的边e，e的两个端点都是T的外点，那么把e加到T中去得到的图叫做带花树。(e)V5V4V3V2V1V8V7+–+––++V15V6–+e'e例如在图(e)中，连接T的两个顶点V5与V7的这条边e(图中的红边)原不属于T，现在把e加到T中去，只不过是使T增加了一条边，没有扩大由Vi交错可达的顶点的范围，反而使得T不再是树了。带花树的特点是，它恰好有一个圈，这唯一的圈称为带花树的花。圈内包含奇数条边。带花树的作用见“7.3.4任意图的最大匹配”匹配问题匹配问题可以分为如下类型：二部图的最大匹配；二部图的完备匹配；二部图的最佳匹配；任意图的最大匹配；每种匹配问题的解法不一样，难度也不一样。7.3.1二分图的最大匹配求二部图的最大匹配的算法有：网络流解法匈牙利算法Hopcroft-Karp算法(匈牙利算法的改进)1网络流解法从二部图G出发构造一个网络G’：增加一个源点S和汇点T；从S向X的每一个顶点都画一条有向弧，从Y的每一个顶点都向T画一条有向弧；原来G中的边都改成有向弧，方向是从X的顶点指向Y的顶点；令所有弧的容量都等于1。求网络G’的最大流F。从X的顶点指向Y的顶点的弧集合中，弧流量为1的弧对应二部图的匹配边，最大流值F对应二部图的最大匹配的边数。思考：为什么这样构造的网络求出来的最大流就是最大匹配？Answer:网络中所有的弧容量均为1。尽管在网络中顶点Xi可能发出多条边，但在最大流中只能选择一条边；尽管在网络中可能有多条边进入顶点Yi，但在最大流中只能选择一条边；以上第(2)、(3)点保证了最大流中二部图中的边不存在共同顶点。X1┊

Xi┊

XnSY1┊

Yi┊

YnT其中表示工人。表示工作。网络流解法实例：

例：设有5位待业者，5项工作，他们各自能胜任工作的情况如下图所示，要求设计一个就业方案，使尽量多的人能就业。按照前面描述的方法构造网络流(如上图所示)：在二部图中增加两个顶点分别作为源点、汇点。并用有向边把它们与原二部图中顶点相连，令全部边上的容量均为1。当网络流达到最大时，如果在最大流中上的流量为1，就让作工作，此即为最大匹配方案。第一次标号。调整第二次标号。再调整。第三次标号。调整。第四次标号。调整第五次标号。标号过程已无法再继续。工人分别作故最多安排四个人工作。流量为1的画彩线即所求的最大匹配。2匈牙利算法(Edmonds,1965)匈牙利算法的原理为：从当前匹配(如果没有匹配，则初始匹配为0)出发，检查每一个未盖点，然后从它出发寻找可增广路，找到可增广路，则沿着这条可增广路进行扩充，直到不存在可增广路为止。根据从未盖点出发寻找可增广路搜索的方法，可以分为：1)DFS增广2)BFS增广3)多增广路(Hopcroft-Karp算法)在算法中用到的一些变量如下：intnx,ny; //X和Y集合中顶点的个数intg[maxn][maxn]; //邻接矩阵,X集合和Y集合中顶点间边的信息intcx[maxn],cy[maxn];//cx[i]表示最终求得的最大匹配中与Xi匹配的Y顶点,cy[i]同理1)DFS增广//DFS算法中记录顶点访问的状态//如果mk[i]=0表示未访问过，如果为1表示访问过intmk[maxn];//从X集合中的顶点u出发用深度优先的策略寻找增广路//(这种增广路只能使当前的匹配数增加1)intpath(intu){

for(intv=0;v<ny;v++)//考虑所有Yi顶点v {

if(g[u][v]&&!mk[v]) { mk[v]=1;

//如果v没有匹配,或者如果v已经匹配了，

//但从y[v]出发可以找到一条增广路

if(cy[v]==-1||path(cy[v])) { cx[u]=v;//把v匹配给u cy[v]=u;//把u匹配给v

return1;//找到可增广路

} } }

return0;//如果不存在从u出发的增广路}intMaxMatch()//求二部图最大匹配的匈牙利算法{

intres(0); memset(cx,0xff,sizeof(cx));//从0匹配开始增广

memset(cy,0xff,sizeof(cy));

for(inti=0;i<=nx;i++) {

if(cx[i]==-1)//从每个未盖点出发进行寻找增广路

{ memset(mk,0,sizeof(mk)); res+=path(i);//每找到一条增广路，可使得匹配数加1 } }

returnres;}优点：实现简洁，理解容易适用：稠密图，由于边多，dfs找增广路很快复杂度：O(n^3)例题：ZOJ1654解题报告2)BFS增广intpred[maxn],mk[maxn],open[maxn];intMaxMatch(){

inti,u,v,t,d,e,cur,tail,res(0);memset(mk,0xff,sizeof(mk));memset(cx,0xff,sizeof(cx));memset(cy,0xff,sizeof(cy));适用：稀疏二分图，边少，增广路短复杂度：O(n^3)for(i=0;i<nx;i++){pred[i]=-1;

for(open[cur=tail=0]=i;cur<=tail&&cx[i]==-1;cur++){

for(u=open[cur],v=0;v<ny&&cx[i]==-1;v++){

if(g[u][v]&&mk[v]!=i){mk[v]=i;open[++tail]=cy[v];

if(open[tail]>=0){pred[open[tail]]=u;continue;}

for(d=u,e=v;d!=-1;t=cx[d],cx[d]=e,cy[e]=d,e=t,d=pred[d]);}}}

if(cx[i]!=-1)res++;}//endoffor

returnres;}3)多增广路：Hopcroft-Karp算法(1972)intpred[maxn],mk[maxn],open[maxn],src[maxn];intMaxMatch(){

inti,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++){flag=0;

for(cur=tail=0,i=0;i<nx;i++){

if(cx[i]==-1)open[++tail]=i,pred[i]=-1,src[i]=i;}这是一类方法，每次增广同时寻找多条不相交增广路，由Hopcroft和Karp于1973