首页 > 其他 > 详细

二分图公式汇总

时间:2020-03-11 02:04:01      阅读:69      评论:0      收藏:0      [点我收藏+]

二分图



注意,要分清题目给的是二分图,还是有向图,还是无向图。对于二分图可以直接求,而有向图或无向图,需要进行拆点,构成对应的二分图(虽然节点个数翻倍),再利用公式(一般公式最后都会除以 \(2\),而原图(有向图或无向图)节点数即为二分图节点数 \(/\) \(2\))。


最小点覆盖:用最少的点,覆盖所有边。即所有边的端点至少有一个点被使用过。

1、二分图最小点覆盖 \(=\) 二分图最大匹配数。

2、无向图最小点覆盖 \(=\)(该无向图的二分图节点数 \(-\) 该无向图的二分图最大匹配数)\(/\) \(2\)

最短路径覆盖:用最少的路径数,来覆盖所有点。

1、有向图最小不相交路径覆盖:用最少的路径覆盖所有点,而且所有点在所有路径上只出现一次。

它的值为:有向图节点数 \(-\) 该有向图的二分图最大匹配数。

2、有向图最小可相交路径覆盖:用最少的路径覆盖所有点,不限制每个点在所有路径上出现的次数。

这种题在 有向图 建图完后,进行传递闭包,然后将所有能到达的两个点对 A->B 都作为了一条有向边。再对这个新的有向图进行拆点,变成二分图,然后就按照 不相交路径覆盖 来写了。
它的值为:有向图节点数 \(-\) 该有向图的二分图最大匹配数。

3、无向图最小路径覆盖: 对于此块内容,在网络上的公式只有:无向图节点数 \(-\) 其二分图最大匹配数 \(/\) \(2\) 。然而这个公式很容易验证是错的。
例如 3 个点, \(1-2-3\) ,对这个无向图拆分后的二分图最大匹配数为 \(2\) ,而这个无向图最小路径数显然为 \(1\) ,它并不等于公式上的 \(3\) \(-\) \(2\)\(/\)\(2\)

最小边覆盖:用最少边,来覆盖所有点。(注意与路径的区别)

1、二分图最小边覆盖:它的值为:原图二分图节点数(两边的节点之和) \(-\) 原图二分图最大匹配数。

2、无向图最小边覆盖:它的值为:(其对应的二分图节点数 \(-\) 其对应的二分图最大匹配数)\(/\) \(2\) \(=\) 原图无向图节点数 \(-\) 其二分图最大匹配数 \(/\) \(2\)

最大独立集:选最多的点,这些点之间两两没有边相连

无向图最大独立集: 它的值为:原图无向图节点数 \(-\) 其对应的二分图的最大匹配数 \(/\) \(2\)

最大独立团:在原图上选若干个节点,这些点两两间都有边连接。即原图的最大完全子图(顶点最多)

最大独立团的节点数 \(=\) 补图的最大独立集。

二分图公式汇总

原文:https://www.cnblogs.com/Absofuckinglutely/p/12459806.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!