jvruo

【蒟蒻图论】二分图匹配
感觉最近学的东西有点杂,最近复习了一下之前学习的匈牙利算法,突然发现,匈牙利算法解决的二分图问题竟然不只有二分图...
扫描右侧二维码阅读全文
19
2018/05

【蒟蒻图论】二分图匹配

感觉最近学的东西有点杂,最近复习了一下之前学习的匈牙利算法,突然发现,匈牙利算法解决的二分图问题竟然不只有二分图最大匹配问题!这篇Blog,我就来讲解一下匈牙利算法所解决的常见的四种模型吧!

什么是二分图

就是对于一个图中的所有点,都可以分类两个到集合X和Y,使得所有的边关联的两个顶点,恰好一个属于集合X,另一个属于集合Y。换句话说,就是集合X中任意两点间没有连边,集合Y中任意两点间也没有连边图。一般整理好之后如下:
1.png

二分图最大匹配

我们先拿出一道经典的问题,来走进神奇的二分图吧!

【问题背景】
n只公牛和m只母牛,
某些公牛和某些母牛互相喜欢。
但最后一只公牛只能和一只母牛建立一对一匹配。
要使得最后牛群匹配对数最大。
【输入】
第一行三个整数n, m,k( 1<= n, m <= 10000,0< k < 100000)。
下来k行,每行两个整数 x,y,表示一条边,连接X集合中x点和Y集合的y点。
【输出】
只有一行。输出一个整数,表示牛群匹配对数最大值.
2.png

很明显,普通的DFS已经没办法解决这样规模的数据了;所以这是我们就要推出一个神奇的算法——匈牙利算法!!!那么这种神奇的算法要如何实现呢?下面我们就来一步一步讲解:

首先和暴力一样,我们对于每个公牛逐个找母牛匹配。如果公牛x1与母牛y1有匹配关系(map[x1,y1]==true),那么我们就来采访一下这只母牛y1:

如果母牛y1尚未匹配(match[y1]==0),则恭喜这对牛,他们匹配成功了,并且把母牛的丈夫设置为x1(match[y1]:=x1);

3.png

4.png

那么如果这只母牛已经有丈夫了呢?我们就去让母牛问一下他的丈夫x2(x2=match[y1]):如果x2能匹配到其他的母牛y2,那么x2就可以离开母牛y1了,与y2匹配了;这个时候y1就没有丈夫了,就可以嫁给公牛x1了。

5.png

6.png

7.png

8.png

那么如果y1的丈夫x2找不到其他能匹配的母牛呢?那没办法,这时候公牛x1不能再打y1的主意了;这时x1,只能再去寻找其他能和他匹配的母牛y2,y3.....

9.png

10.png

11.png

12.png

那么如果所有和他互相喜欢的母牛都无法和他完成匹配,那他就无法匹配,ans不变;其余情况能匹配,则ans++。

13.png

接下来让我们一步一步写完这个程序:

数据结构:

int match[501];  //标记母牛的数组,match[i]为第i只母牛的匹配对象是第几只公牛

int n,m,ans,i; //n公牛数目,m母牛数目,ans为匹配对数

bool map[401][501] ; //map[i][j]==true表示第i只公牛和第j只母牛有匹配关系

bool chw[501];  // 也是标记母牛可否被“询问”的数组(“询问”后面有解释)。

   //如果第i只母牛chw[i]==false,表示母牛i不可被询问,否则表示母牛i可被“询问”。

   //匈牙利算法的关键点:chw数组

过程getmatch:从第1只到第n只公牛,逐个逐个寻找母牛匹配:

pvoid getmatch()

{

   ans=0;//匹配对数初始化为0

   memset(match,0,sizeof(match));//每只母牛初始化为未匹配(match[i]=0)

   for(int i=1;i<=n;i++)  //公牛逐个逐个找母牛

   {

      memset(chw,true,sizeof(chw)); //所有母牛初始化为可“询问”

      if(find_muniu(i)==true)ans++;//如果找到了,总体增加一对 find_muniu(i)表示公牛i去找母牛

   }

}

函数find(k):一个返回值函数判断第k只公牛能否匹配成功,若匹配成功返回True,若没有匹配成功返回false:

bool find_muniu(int k)

{

   for(int i=1;i<=m;i++)  //逐只母牛问

      if (map[k][i]==true)  //第k只公牛和第i只母牛有匹配关系

         if (chw[i]==true)//问母牛i能否被“询问”

         {

            chw[i]=false; //标记母牛i已被询问,不管匹配成功与否,以后其他公牛都没必要再询问母牛i

            if ( match[i]==0 || find_muniu(match[i])==true )

            // match[i]=0 该母牛单身  或者 find(match[i])如果该母牛已匹配公牛x(x==match[i]),尝试让公牛x去找其他母牛匹配

            {

                match[i]=k;

                return true; //这两句表示第i只母年匹配了第k只公牛}

            }

         }

   return false;//执行到这一步表示匹配不成功。

}

接下来我们来重点讲解一下“询问”:chw数组的意义。

意义一:如果第i只母牛 chw[i]==true ,表示第i只母牛有匹配成功的可能性。母牛i有未匹配和已匹配两种情况:

情况一:母牛i未匹配(match[i]==0),那么简单直接match[i]:=k,匹配成功;

情况二:母牛i已匹配(X1==match[i]),那么让公牛X1尝试去寻找其他母牛匹配。公牛X1不能再找母牛i,否则成死循环。

意义二:如果第i只母牛 chw[i]==false,公牛X1也不能找已经被“询问”过的母牛j,为什么?母牛j被标记为“询问”过,分两种情况:

情况一:之前被询问的时候匹配成功了,或 match[j]=0或 find_muniu(match[j])=true。但情况一是不可能的。因为如果匹配成功,那么就不会有后来的公牛X1去找母牛j的需要。

情况二:之前被询问的时候匹配不成功。这种情况只能是母牛j已匹配,且匹配对象公牛X2(X2==match[j])找不到其他母牛匹配能成功(也就是find_muniu(X2)==false)。如果之前有其他公牛询问母牛j都不能成功,那么现在的公牛X1也一定不会成功,所以没有必要询问。chw数组的第二个意义剪支省时的作用。

主函数:

int main()

{

   scanf("%d%d",&n,&m);//n只公牛,m只母年

   memset(map,false,sizeof(map));//初始化匹配关系

   for(int i=1;i<=n;i++)//读入边,构建图

   {

       int kk,y;scanf("%d",&kk); //混蛋,第i只公牛竟然能和kk只母牛匹配,她们是谁?

       for(int j=1;j<=kk;j++)

       {

           scanf("%d",&y);

           map[i][y]=true;

       }

   }

   getmatch();

   printf("%d\n",ans);//输出最大匹配对数

   for(int i=1;i<=m;i++)//询问每只母牛有没有匹配到公牛

      if(match[i]>0)   //如果母牛i已经匹配,输出匹配了哪只公牛

          printf("%d %d\n",match[i],i);

   return 0;

}

特别值得注意的是,当数据比较大时,二维数组map【n】【m】可能会超过空间限制,这时我们就要运用前向星进行存储。

二分图最小点覆盖

我们再来看一个例子:

【题目描述】
X集合有n个点(编号1,2,3,……n),
Y集合有m个点(编号1,2,3,……m),
有k条边(任意一条边的两个端点,一个来自X集合,一个来自Y集合)
如果选中一个点(可以来自X集合或Y集合)就是燃烧掉所有与该点相连的边。
问:至少选中多少个点,可以摧毁所有边(也就是k条边)
【输入】
第一行三个整数n, m,k( 0< n, m < 100,0< k < 1000)。
下来k行,每行两个整数 x,y,表示一条边,连接X集合中x点和Y集合的y点。
【输出】一个整数,为最少选中的点数目。

什么你不会做?没事我先告诉你结论:按题意构图后,用匈牙利算法求最大二分图匹配数,就是答案!什么?你不会证明,没事接下来就让我慢慢证明给你看:

König定理证明:

虽然直接应用König定理可以解决许多最小覆盖的题目,但这类题难点往往在于构图,要做到灵活构图应用König定理,则对其证明需要有一定的了解。König定理的证明是建立在匈牙利算法操作细节上的,掌握匈牙利算法的全过程很重要。

假设二分图G分为左边X和右边Y两个互不相交的点集。G经过匈牙利算法后找到一个最大匹配M=3,设红线为匹配边,黄色为匹配边两端的点如下图:

14.png

根据König定理,我们可以从最大匹配边中选M个点,使得这与这M个点相连的边刚好为总边数N。下来说明选点策略,再证明这个策略的正确性。

选点策略:

我们用绿色标记右边未匹配边的顶点,并从右边未匹配边的顶点出发,按照边:未匹配→匹配→未匹配→……的原则标记途中经过的顶点,则最后一条经过的边必定为匹配边(否则为增广路经)。重复上述过程,直到右边不再含有未匹配边的点。

也就是所,我们每次都要先把右边的白色点标记成绿色,然后进行拓展;所以对于第一次拓展,我们首先标记右边的二号点,开始走边,得到绿色路径:

15.png

对于第二次拓展,我们首先标记右边的五号点,开始走边,得到绿色路径:

16.png

这时我们右边所有点都有了颜色,选点完成!这时我们记得到的左边已用绿色标记的点和右边未标记的点为S(用粉色标记),S即为所求的最小顶点集。

17.png

以下证明S即为所求的最小顶点集:

证明选点策略:

1、点集S的元素个数=二分图的最大匹配数M:
左边标记的点全都为匹配边的顶点,右边未标记的点也为匹配边的顶点。因此,我们得到的点与匹配边一一对应。

18.png

2、点集S中的点能覆盖二分图G中所有的边。

根据左右端点是否被标记,G中所有的边有以下四种情况:
① 左右均被绿色标记;
② 左右均无绿色标记;
③ 左边被绿色标记,右边未绿色标记;
④ 左边未绿色标记,右边被绿色标记;

19.png

前三种,运用S中的点(包含:左边的点(标记)+右边的点(未标记))都能得到的,除了④。下面证明④不存在。

假如存在一条边e,使得e的两端都不在点集S当中,由于当时选点的时候选了二分图当中:左边为绿色的点和右边不为绿色的点;所以此时e的两个端点左边未绿色标记,右边被绿色标记;

如果e不属于被匹配的边(也就是之前过程中的绿色边),那么左端点就可以通过这条边右端点到达(从而得到标记);

如果e属于匹配边(也就是之前过程中的绿色边),那么右端点的标记从哪里来?它的标记只能是从这条匹配边的左端点过来,那么左端点就应该有标记。

3、S是最小的覆盖。

因为最大匹配M中,M条边两两之间没有共同交点,所以要覆盖这M条匹配边至少就需要M个点。

至此证明完成!

二分图最小边覆盖

我们再来看一个例子:

【题目描述】
X集合有n个点(编号1,2,3,……n),
Y集合有m个点(编号1,2,3,……m),
有k条边(任意一条边的两个端点,一个来自X集合,一个来自Y集合)
如果选中一个点(可以来自X集合或Y集合)就是燃烧掉所有与该点相连的边。
问:至少选中多少个边,可以摧毁所有点
【输入】
第一行三个整数n, m,k( 0< n, m < 100,0< k < 1000)。
下来k行,每行两个整数 x,y,表示一条边,连接X集合中x点和Y集合的y点。
【输出】一个整数,为最少选中的边数目。

什么你又不会做,没关系,我们先把结论告诉你——我们先用匈牙利算法求最大二分图匹配数,再用总点数减去最大匹配数就是我们要求的的答案了。这是为什么呢?别急这就证明给你看:

我们首先设最大匹配数为m,总顶点数为n。为了使边数最少,又因为一条边最多能干掉两个点,所以尽量用边干掉两个点。也就是取有匹配的那些边,当然这些边是越多越好,那就是最大匹配了,所以先用最大匹配数目的边干掉大多数点。剩下的解决没有被匹配的点,就只能一条边干掉一个点了,设这些数目为a,显然,2m+a=n,而最小边覆盖=m+a,所以最小边覆盖=(2m+a)-m=n-m。

正如下图,我们先用最大匹配选出的三条边解决了黄色标记的六个点,剩下蓝色的三个点就没有办法了,没办法做到一条边覆盖两个蓝色点了,只好小亏一波,一条边去覆盖一个点。

kq.png

得证。

二分图最大独立集

我们同样的先引入一道例题:

题目描述
X集合有n个点,Y集合有m个点,同个集合内的任意两点没有边,
有k条边,每条边的两个端点一个来自X集合,另一个来自Y集合。
问题:选出某些点组成一个集合,使得集合中的任意两点之间没有边相连,问这个集合最多可以包含多少个点?
Input
数据第一行三个整数n, m (1 ≤ n, m ≤ 10000) and k (0 ≤ k ≤ n × m 且 k<= 10^6),
下来k行,每行两个整数 x and y (1 ≤ x ≤ n,1 ≤ y ≤ m), 表示一条边的两个端点。
Output
输出一行,一个整数,即集合最多可以包含点的个数。

还是先告诉你结论吧:
最大独立集=总点数 - 最小点覆盖=总点数 - 最大匹配数;
现在我们进入证明:

20.png

上图,我们用两个红色的点覆盖了所有边。我们证明的前提条件是已经达到最小覆盖(即满足:条件1.已经覆盖所有边;条件2.所用的点数最小)

首先我们来证明蓝色点组成的是一个独立集:
如果有两个蓝色点间有边相连,那么这条边则没有被覆盖,则与条件1矛盾。因此是独立集。

再来证明这个独立集最大:
如果我们要再增加这个独立集中的点,则需要把某个红点变成蓝点;那么此时我们就要把和这个红点相连的所用蓝点变为红点;

而由最小覆盖数=最大匹配数的证明我们知道,每一个红点是最大匹配中的一个匹配点;也就是说每个红点至少连接了一条边。因此当我们将某个红点变成蓝点时,我们需要牺牲的蓝点的个数是大于等于1的。也就是说,我们最多只能找到数量相等的其他独立集,而无法找到数量更大的。因此蓝色点集必定为最大独立集。

所以我们可以发现,蓝色点数 =总点数 - 红色点数,即最大独立集=总数-最小覆盖集。

至此证明完成!

结语

到这里,二分图的三种常见运用我们都已经讲完了,如果存在什么问题,请在下方留言中告诉我。希望你喜欢这篇BLOG!

foot.gif

Last modification:July 23rd, 2018 at 08:45 am
If you think my article is useful to you, please feel free to appreciate

One comment

  1. gay

    guy

Leave a Comment