文档章节

二分图的最大匹配

秋岛流云
 秋岛流云
发布于 2014/08/03 09:11
字数 1797
阅读 91
收藏 0

二分图;

大意: 

  二分图指的是这样一种图,其所有顶点可以分成两个集合X和Y,其中X或Y中任意两个在同一集合中的点都不相连,所有的边关联在两个顶点中,恰好一个属于集合X,另一个属于集合Y。给定一个二分图G,M为G边集的一个子集,如果M满足当中的任意两条边都不依附于同一个顶点,则称M是一个匹配。图中包含边数最多的匹配称为图的最大匹配。

   二分图的最大匹配有两种求法,第一种是最大流;第二种就是我现在要讲的匈牙利算法。这个算法说白了就是最大流的算法,但是它跟据二分图匹配这个问题的特点,把最大流算法做了简化,提高了效率。

 增广路径的定义(也称增广轨或交错轨):

一条增广路径(Augmenting Path)是指从 M 中没有用到的顶点开始,并从 M 中没有用到的顶点结束的交替路径。(PS:一条交替路径(Alternating Path)是指这样一条路径,其中的每一条边交替地属于或不属于匹配 M。比如说,第一、三、五条边属于 M,而第二、四、六条不属于 M,等等。)

所以如下图(3)中所示即为一条增广路径。

结合增广路径的定义和下图所示,我们可以理解以下结论:

  • 增广路径的长度必定为奇数,第一条边和最后一条边都不属于 M。

  • 将 M 和增广路径进行异或操作(去同存异)可以得到一个更大的匹配 M'。

  • M' 比 M 的匹配数多 1。

  • M 为 G 的最大匹配当且仅当不存在 M 的增广路径。

最大流算法的核心问题就是找增广路径(augment path)。匈牙利算法也不例外,它的基本模式就是:
     初始时最大匹配为空
      while 找得到增广路径
               do 把增广路径加入到最大匹配中去
      可见和最大流算法是一样的。但是这里的增广路径就有它一定的特殊性。(注:匈牙利算法虽然根本上是最大流算法,但是它不需要建网络模型,所以图中不再需要源点和汇点,仅仅是一个二分图。每条边也不需要有方向。)

      算法的思路是不停的找增广路径, 并增加匹配的个数,增广路径顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广路径的表现形式是一条"交错路径",也就是说这条由图的边组成的路径, 它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过。这样交错进行,显然他有奇数条边。那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推。也就是将所有的边进行"反色",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对。另外,单独的一条连接两个未匹配点的边显然也是交错路径。可以证明。当不能再找到增广路径时,就得到了一个最大匹配,这也就是匈牙利算法的思路。

3个重要结论:

1 最小点覆盖数: 最小覆盖要求用最少的点(X集合或Y集合的都行)让每条边都至少和其中一个点关联。可以证明:最少的点(即覆盖数)=最大匹配数
2 最小路径覆盖=最小路径覆盖=|N|-最大匹配数
     用尽量少的不相交简单路径覆盖有向无环图G的所有结点。解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个:X结点集中的i和Y结点集中的i',如果有边i->j,则在二分图中引入边i->j',设二分图最大匹配为m,则结果就是n-m。
3 二分图最大独立集=顶点数-二分图最大匹配
     在N个点的图G中选出m个点,使这m个点两两之间没有边,求m最大值。
如果图G满足二分图条件,则可以用二分图匹配来做.最大独立集点数 = N - 最大匹配数。 
例题:
http://acm.hdu.edu.cn/showproblem.php?pid=1281棋盘游戏

一种建图的方式,对于一个坐标,x , y 可以分成两个不同的集合,如果该点满足某种性质的话,就在 x , y 上连一条线,本题就是这样的……
本题要求关键点,那么只需要对于每个可行点进行删点,然后看看得出的最大匹配是否小于不删点的解,如果小于,则是关键点……统计一下即可。
代码:
[cpp] view plaincopy
/*==================================================*\
| 二分图匹配(匈牙利算法DFS 实现)
| INIT: g[][]邻接矩阵;
| 优点:实现简洁容易理解,适用于稠密图,DFS找增广路快。
| 找一条增广路的复杂度为O(E),最多找V条增广路,故时间复杂度为O(VE)
==================================================*/ 
#include<stdio.h> 
#include<memory.h> 
 
bool g[101][101]; //邻接矩阵,true代表有边相连 
bool visit[101];    //记录V2中的某个点是否被搜索过 
int match[101];   //记录与V2中的点匹配的点的编号 
int n,m,k;   //二分图中左边、右边集合中顶点的数目  
 
// 匈牙利算法 
bool dfs(int u) 

    for (int i = 1; i <= m; ++i) 
    { 
        if (g[u][i] && !visit[i])   //如果节点i与u相邻并且未被查找过 
        { 
            visit[i] = true;   //标记i为已查找过 
            if (match[i] == -1 || dfs(match[i]))   //如果i未在前一个匹配M中,或者i在匹配M中,但是从与i相邻的节点出发可以有增广路径 
            { 
                match[i] = u;  //记录查找成功记录,更新匹配M(即“取反”) 
                return true;   //返回查找成功 
            } 
        } 
    } 
    return false; 

 
inline int MaxMatch() 
{   
    int i,sum=0;   
    memset(match,-1,sizeof(match));   
    for(i = 1 ; i <= n ; ++i)   
    {   
        memset(visit,false,sizeof(visit));   //清空上次搜索时的标记   
        if( dfs(i) )    //从节点i尝试扩展   
        {   
            sum++;   
        }   
    }   
    return sum;   

 
int main(void) 

    int i,j,ans,x,y,num,t=1; 
    while (scanf("%d %d %d",&n,&m,&k)!=EOF) 
    { 
          memset(g,false,sizeof(g));   //初始化 
          for (i = 1; i <= k; ++i) 
          { 
              scanf("%d %d",&x,&y); 
              g[x][y] = true; 
          } 
          ans = MaxMatch(); 
          num = 0; 
          for (i = 1; i <= n; ++i) 
          { 
              for (j = 1; j <= m; ++j) 
              { 
                  if(g[i][j] == true) 
                  { 
                      g[i][j] = false; 
                      if(MaxMatch() < ans) 
                          num++; 
                      g[i][j] = true; 
                  } 
              } 
          } 
          printf("Board %d have %d important blanks for %d chessmen.\n",t++,num,ans); 
    } 
    return 0; 

ps:对于二分图方面的题  难的不是代码 而是你是否能看出这是一道二分图的题 是否有这种转化能力  当然 如果你知道了 套个模板基本就能对

© 著作权归作者所有

上一篇: 凸包(叉积
秋岛流云
粉丝 2
博文 26
码字总数 26030
作品 0
烟台
程序员
私信 提问
司机乘客匹配中的距离和最小问题

这个是在工作中遇到的一个实际的算法问题,问题描述如下,当前有m个司机,n个乘客,每个司机和每个乘客的距离由经纬度可以计算得到,如何匹配可以使其去接乘客的距离和最小?(只能一个司机接...

necther
2018/05/03
0
0
二分图算法模板以及相关知识

说说二分图,其实图论的题难点不在用算法,难在如何建图,只有图建好了,剩下的就简单了,在这说说求二分图的算法,即匈牙利算法,其实一点都不难,也很好理解拿笔写写就行了. //板子, 直接套就行 //...

Anxdada
2017/06/22
0
0
【算法篇】二分图匹配之匈牙利算法

二分图匹配,自然要先从定义入手,那么二分图是什么呢? 二分图: 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图...

沧海无雨
2018/07/26
0
0
二分图匹配算法(最大流匈牙利)

二分图匹配 相关概念 无向二分图(G(Ubigcup V,E)):U是一个顶点集合,V是另一个顶点集合,对于一个集合内的点无边直接相连,而对于不同集合的点可以连边,即((u,v)in E)。 匹配:两两不含公共...

小张人
08/08
0
0
12.15~12.16培训总结

图论我在九月份打了很多板,基础较熟练,但对二分图匹配和网络流、费用流以及各种模型不太熟练。 二分图主要有这些模型 (部分参考lrj) 二分图最小覆盖(选择尽量少的点,使得每条边至少有一...

myjs999
2017/12/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

查看线上日志常用命令

cat 命令(文本输出命令) 通常查找出错误日志 cat error.log | grep 'nick' , 这时候我们要输出当前这个日志的前后几行: 显示file文件里匹配nick那行以及上下5行 cat error.log | grep -C ...

xiaolyuh
13分钟前
3
0
六、Java设计模式之工厂方法

工厂方法定义: 定义一个创建对象的接口,但让实现这个接口的类来决定实例化哪个类,工厂方法让类的实例化推迟到子类中进行 类型:创建型 工厂方法-使用场景: 创建对象需要大量重复的代码 ...

东风破2019
19分钟前
2
0
win服务器管理遇到的一系列问题记录

有些小伙伴在使用iis7远程桌面管理工具的时候总是会遇到一系列的问题,下面就是为大家介绍一下服务器日常管理过程中出现的问题及我的解决办法和心得。希望能帮到大家。   拒绝服务器重新启...

1717197346
26分钟前
2
0
flutter 剪切板 复制粘贴

复制粘贴功能 import 'package:flutter/services.dart'; Clipboard.setData(ClipboardData(text:_text));Clipboard.getData;...

zdglf
29分钟前
3
0
如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题?

面试题 如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题? 面试官心理分析 这个是肯定的,用 MQ 有个基本原则,就是数据不能多一条,也不能少一条,不能多,就是前面说的重复消费...

米兜
30分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部