對酒當歌,人生幾何? 譬如朝露,去日苦多

kuangbin专题分类

一. 二分匹配

先看一下理论理解一下:http://www.renfei.org/blog/bipartite-matching.html

然后趣学匈牙利算法:一遍就看懂

A,B,C,D,E,G

1.交叉染色判断二分图。

2.二分图最小点覆盖(König定理证明)(好像只能无向,对吧?)

I,

感谢Matrix   

感谢:http://blog.csdn.net/kootain/article/details/6692582?utm_source=jiancool

其实就是二分图最大匹配,要换个角度思考。

二分图最大匹配匹配到的点为集合M。x点属于左集合,y点属于右集合,且x点和y点不属于M,那么x,y点一定没有路相连,因为它们不属于集合M。所以除集合M的点外,其他点与之相连的边一定属于M,M中的点是二分图最大匹配,所以就相等,但是有向要改为无向进行二分图最大匹配。

3.

无向图二分图最小路径覆盖,

H,

无向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数/2

一开始我想时是这样的样例,有7个点,经过匹配1和5,2和4,3和6,7单出来。所以我以为是(二分图最大匹配+1)/2,但是发现我只考虑了一个图,如果他有好几个图,我就完了,所以上面的公式补全了我的思想。

有向图二分图最小路径覆盖和求最大独立子集

有向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数

感谢:http://blog.sina.com.cn/s/blog_89a06c7d0100trcg.html

也就是 最大独立子集=顶点个数-最小顶点覆盖(最大二分匹配数)

先假设一个二分图模型,A集合和B集合,然后A中一些人认识B中的一些人,但是它们集合内部互不认识,现在要找,A集合和B集合中互不认识的人有多少个?

那么求出来最大匹配数后,按照我第二个思想(二分图最小点覆盖),用总定点数减去最大匹配数后就是互不认识的人,那就是最大独立子集=顶点个数-最小顶点覆盖(最大二分匹配数),那么把路径看成一个集合就能理解了。

另外如果最小路径上可以有点重复,需要floyd缩点,不怎么懂,稍微看懂点的博客

 

标签: none

仅有一条评论

  1. 刀剑 刀剑

    可以

添加新评论