关于二分图一些概念的记录

最大匹配其实就是最大边独立集
最小点覆盖集=最大边独立集
最小边覆盖集=最大点独立集
求最小点覆盖集的一个可行解:
法一:见matrix67对二分图最大匹配的König定理的证明
法二:
算法实现步骤:
1. 做最大匹配,没有匹配的空闲点∈S
2. 如果u∈S那么u的邻点必然属于T
3. 如果一对匹配的点中有一个属于T那么另外一个属于S
4. 还不能确定的,把左子图的放入S,右子图放入T
算法结束
求最大点独立集的一个可行解:所有点去掉最小点覆盖集的点

关于DAG的最小路径覆盖的一些理解:
最近记忆力很差,很多结论做题的时候记得,果断时间又忘了,还是记录下来..
1.可以这样理解最小路径覆盖:开始的时候n个点,每个点需要一条路径去覆盖,然后一条匹配边会把两个路径连在一起,所以每增加一条匹配边,路径数就减少1,当达到最大匹配时,路径数最少。所以最小路径覆盖=原图总点数-最大匹配
2.也可以这样理解最小路径覆盖:二分图的最大匹配的那些弧和最小路径覆盖的弧是对应的。假如有弧,则连弧,所以对于二分匹配完的图中,u点的匹配点是n+v,意思就是v点有入边。在一条路径中,只有起始点是没有入边的,所以最少有几条路径本质就是最少有几个这样没有入边的点。那么二分匹配边的右侧点都是有入边的,剩下(原图总点数-二分匹配数)个点是没有入边的,这些点就是每条路径的起始点。
由上面的2可以得到求最小路径覆盖的可行解(最小路径覆盖可能有多个解,因为最大匹配可能有多个解)。

有向无环图最小可相交路径覆盖
定义:用最小的可相交路径覆盖所有顶点。
算法:先用floyd求出原图的传递闭包,即如果a到b有路,那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>