注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

二分图总结(未完待续)  

2014-07-09 21:09:50|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一.
这个博客让我明白了为什么无环有向图中的最小路径覆盖=原图中点数-二分图最大匹配;
转载:
DAG的最小路径覆盖是指找最小数目的互相不相交的有向路径,满足DAG的所有顶点都被覆盖.

首先给出公式:DAG的最小路径覆盖数=DAG图中的节点数-相应二分图中的最大匹配数.

那么对应一个DAG,如何构造相应的二分图?对于DAG中的一个顶点p,二分图中有两个顶点p和p',对应DAG中的一条有向边p->q,二分图中有p-q'的一条无向边.二分图中p属于S集合,p'属于T集合.
下面我们来解释上面公式为什么成立,思路参考baihacker神牛:


上图中,对应左边的DAG建立构造右边的二分图,可以找到二分图的一个最大匹配M:1-3',3-4',那么M中的这两条匹配边怎样对应DAG中的路径的边?
使二分图中一条边对应DAG中的一条有向边,1-3'对应DAG图中的有向边1->3,这样DAG中1就会有一个后继顶点(3会是1的唯一后继,因为二分图中一个顶点至多关联一条边!),所以1不会成为DAG中一条路径中的结尾顶点,同样,3-4'对应DAG中3->4,3也不会成为结尾顶点,那么原图中总共4个顶点,减去2个有后继的顶点,就剩下没有后继的顶点,即DAG路径的结尾顶点,而每个结尾顶点正好对应DAG中的一条路径,二分图中寻找最大匹配M,就是找到了对应DAG中的非路径结尾顶点的最大数目,那么DAG中顶点数-|M|就是DAG中结尾顶点的最小数目,即DAG的最小路径覆盖数.
二.最小点覆盖

二分图中,选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖),叫做最小点覆盖。
最小点覆盖数 = 最大匹配数

这个比较显然。。

三.最大独立点集

在一个二分图中,选择一些顶点,使得所选择的点集中任意两个顶点之间没有边相连
可以证明,最大独立顶点集 = 总顶点数 - 最大匹配数

例如:poj3692

给出女生人数 G 男生人数 B 和 男女认识的关系数 M

接下来 M 行..

a b 表示女生 a 和男生 b 认识..

当G B M都等于0的时候表示输入结束..

输出可以找出多少个人是互相认识的..

P.S. 男生们都互相认识了~女生们也都互相认识了..

题解:

将男生看成一个集合 女生看成一个集合

先求补图

然后最大独立及顶点个数 = 节点数(x + y) - 最大匹配数

所以我就是先把他们当成都是认识的了..

如果是认识的就变成 G[a][b] = false;

然后用匈牙利求最大匹配..


PS:由上面结论可得,最小覆盖点集和最大独立点集互补,即
最小点覆盖 + 最大独立点集 = 总顶点数
类似的,在带点权的二分图中,最小点权覆盖集 + 最大点权独立集 = 总权和
  评论这张
 
阅读(7915)| 评论(39)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018