-
没有点权和边权的时候,不讨论最大权闭合子图,最大匹配=最小点覆盖=点数-最大独立集
最小点覆盖=点数-最大独立集:这个很好理解,考虑只有一条边的二分图的情况,点覆盖要求两个端点至少选一个,独立集要求两个端点最多选一个,是互补的关系,这意味着一个合法点覆盖的点集与一个合法独立集的点集一一对应,所以最小点覆盖的方案取反就得到最大独立集的方案。这个性质在一般图上仍然成立,不依赖于二分图的结构。
最大匹配=最小点覆盖:这里利用网络流的概念简单理解。二分图内原来的边按左指向右定向且容量为无穷,从源点向左部的所有点连边,从右部的所有点向汇点连边,新连边容量为 1,此时一个流对应一个匹配,一个割对应一个点覆盖,而又有最大流=最小割,自然有最大匹配=最小点覆盖。
-
只有边权的时候,只有最大匹配有意义。此时就从最大流的模型变成了最大费用流的模型。
-
只有点权的时候,不考虑最大匹配,最大权闭合子图在这里特指左边都是正点权,右边都是负点权,边从左连向右的时候的二分图的最大闭合子图的点权和,有最小权点覆盖=总点权-最大权独立集=右部点权和+最大权闭合子图
首先最小权点覆盖和1.中描述的分析方法相同,由于一个割对应一个点覆盖,只要将容量改为点权,那么割的容量就是点覆盖的值了。与2.中描述的最大权匹配会被加强为费用流不同,最小权点覆盖仍仅需要求解最小割。
然后我们整体地解释这个等式。
现在有一个二分图,点有点权,点权全部是正的。现在约定一条边表示它所连接的两个端点不能同时选,求能选出的最大点权和,这是最大权独立集的模型。
同样的二分图,同样的要求,但我事先将所有点的点权拿走表示全选,然后把所有点权置负表示选择这个负权意味着退回之前拿的点权,此时一条边的含义转化为至少选一个点退回,这是最小权点覆盖的模型。
如果上一次事先拿点权时只拿了右边的点权表示咱且选择右边的所有点,然后把右边的点权置负表示选择这个负权意味着退回之前拿的右部点,现在一条边的含义就变为了如果选择了左边的正点权,就必须选择右边的负点权表示退回这个点,这是最大权闭合子图的模型。
第一种情况实际求解的时候是直接取反然后用最小割求解最小点覆盖,而第三种情况的一般图标准做法也是先拿走所有正权点求最小割,总的来说三种情况本质相同,都是在做最小割,最终建的图都是一样的。