二分匹配最大匹配的理解(附图解)-阿里云开发者社区

开发者社区> 人工智能> 正文

二分匹配最大匹配的理解(附图解)

简介:

  定义
一个PXP的有向图中,路径覆盖就是在图中找一些路径,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联;(如果把这些路径中的每条路径从它的起始点走到它的终点,那么恰好可以经过图中的每个顶点一次且仅一次);如果不考虑图中存在回路,那么每条路径就是一个弱连通子集.
由上面可以得出:
1.一个单独的顶点是一条路径;
2.如果存在一路径p1,p2,......pk,其中p1 为起点,pk为终点,那么在覆盖图中,顶点p1,p2,......pk不再与其它的顶点之间存在有向边.
路径覆盖与二分图匹配的关系(必须是有向无环图):
最小路径覆盖=|P|-最大匹配数

也就是说匈牙利算法将一个二分匹配模型转换成了一个有向图的关系(u->v)存在了二维数组中!最后通过linker[u]数组的值,我们知道是选择了linker[u] -> u这一条有向边的匹配关系!也就是有多少个非负的linker[u]的个数,就有多少个匹配的关系!如果不存在回路,那么这些linker[u] -> u有向边关系所构成的弱联通的子集的个数就是最小路径覆盖的个数!










本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3917855.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章