「笔记」独立集和覆盖

bobble · 2019-04-14 17:00:25 · 个人记录

Definitions

最大点独立集（maximum independent set）：在图中最大的一个点集，使得在此集合中任两点都不相邻，记为 I。（点数）
最大边独立集（maximum independent edge set）：在图中最大的一个边集，使得在此集合中任两边都不相邻。其实就是最大匹配，记为 M。(边数)
最小点覆盖（minimum vertex cover）：在图中最小的一个点集，使得对于任意一条边，它的两端点至少有一个在此集合中，记为 C_v。
最小边覆盖（minimum edge cover）：在图中最小的一个边集，使得对于任意一个点，都至少有一个相邻的边在此集合中，记为 C_e。
补图将存在的边消除，将不存在的边连上得到的图
团无向图G的极大完全子图称为团，最大团即使G的最大完全子图

最大团

所有的NP问题都可以归约到它

它也是一个NP问题可以在多项式时间(n^2)内判定，这是个NPC。

AT: NP-Hard不一定使个NP问题哦！

朴素搞法中比较优的一种O(2^n*n)

按照节点编号从大到小枚举确定团的最小编号点，然后最优化剪枝，

如果后面的全部节点或后面节点的最大团加上当前团中节点比当前结果小就退出？

主要优在不是枚举子集判定，而是根据性质枚举

最大独立集

最大独立集就是其补图的最大团，这个东西比较显然 ?Sample: poj1419

二分图的最大独立集

König定理

|M| = |C_v|

Proof: https://www.cnblogs.com/jianglangcaijin/p/6035945.html

 反证法证明$|C_v|\geq |M|$

 根据Hungary中增广路的性质构造大小为$|M|$独立集，然后证明之

根据这个定理，前四个问题都有多项式搞法

最大独立集相关

|I| = |V|-|M|

可以根据König定理反证

其他证法: 规定： V_M 为最大匹配的子图的点集

|I| \leq |V| - |M|

显然M中的任意一个匹配的两个端点有连边，于是每个匹配至少有一个点不在I中得证。

|I| \geq |V| - |M|

根据最大匹配的定义，对于不在M中的点相互之间不会有连线，于是I \geq |V| - |V_M| ，貌似接下来是伪证

最小路径覆盖

一个DAG，要求用尽量少的不相交的简单路径覆盖所有的节点。

显然对于每条路径上的每一个节点，度数小于等于2 于是给每个节点建立一个副本，然后跑二分图匹配，

二分图中寻找最大匹配|M|，就是找到了对应DAG中的非路径结尾顶点的最大数目，那么DAG中|V|-|M|就是DAG中结尾顶点的最小数目，即DAG的最小路径数目。

Theorom？

　　可以证明，一张图 G = (V, E) 中，|I| + |C_v| = |M| + |C_e| = |V |。

首先证明点独立集和点覆盖之间的双射关系，因为对于一个独立集，在原图上删去它后，剩下的点集显然是一个点覆盖；对于一个点覆盖，反证法，因为点覆盖所以考虑删去点独立集后的图中的任意点对之间显然没有连边，否则这就不是一个点覆盖，得证。

因此 |I| + |C_v| = |V|。

至于对于一个最大匹配，可以发现这个最大匹配盖住了 2|M| 个点，因此最多只需要再 |V|-2|M| 条边就可以覆盖完所有点，故 |C_e|\leq |V|-|M|。

然而一个最小边覆盖和所有点，会形成一个森林（没有环，否则就不会是最小），如果把每个连通块挑一个边出来，会形成边独立集。

因为每个连通块都是一棵树，满足点数减边数等于一，也就是连通块个数等于 |V|-|C_e|，因此 |M|\geq |V|-|C_e|。

综合上述两点，|M|+|C_e| = |V|。

题单？？

CTSC 2008 祭祀

todo：bitset优化传递闭包？？

偏序是一个自反，非对称，传递的关系，带偏序关系的集合叫偏序集或半序集

a,b如果满足偏序关系，那么称它们是可比的。

反链是任意两个元素都不可比的集合，而链是任意都可比的 --- 下面是两个重要定理：对于有限偏序集X，并令r是其最长链的大小。则X可以被划分成r个并且不能再少的反链。对于有限偏序集X，并令m是最长反链的大小。则X可以被划分成m个并且不能再少的链。 --- 证明：设p为最少反链个数 //证明还没看 (1)先证明X不能划分成小于r个反链。由于r是最大链C的大小，C中任两个元素都可比，因此C中任两个元素都不能属于同一反链。所以p>=r。 (2)设X1＝X，A1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。令A2是X2中极小元的集合，从X2中删除A2得到X3……最终，会有一个Xk非空而X(k+1)为空。于是A1,A2,...,Ak就是X的反链的划分，同时存在链a1<=a2<=...<=ak，其中ai在Ai内。由于r是最长链大小，因此r>=k。由于X被划分成了k个反链，因此r>=k>=p。因此r=p，定理1得证。搞清楚了反链和链的定义，就能够很好的从Hasse Diagram中得到理解。链就是从纵向的角度看 Hasse Diagram ,反链是从横- 向的角度看Hasse Diagram。定理一，就是至少有r行构成反链关系。定理二，就是至少有m列构成链关系。 --- 要求最长反链也就是dag的最小路径覆盖，但由于是偏序，传递闭包使得关系图完整，【todo：相关反例】由于每个点只能有一个入边和一个出边，建立两层的图，即二部图，直接匹配可以求得原图的最大匹配， Update 4.25 : 哎，把反例想到后上一段显然就是错误的。 ![https://cdn.luogu.com.cn/upload/pic/57406.png](https://cdn.luogu.com.cn/upload/pic/57406.png) 建二分图是因为每条路径只有一个起点和终点，中间的点可能会有多个入度和出度，传递闭包后匹配，可以发现若干条路径可以连起来，但是计数可以按照如下，是没毛病的。 **求最大匹配求得原图的非路径结尾顶点数目，对每条路径取终点为最小代表元，计数一下发现点数减去最大匹配可以得到最小路径覆盖数 ** --- ### TJOI 攻击装置 #### 棋盘染色棋盘染色之后，发现连边的点对是不同色的，也就是一个二部图，然后我们对二部图求最大独立集，根据染的色选择一部开始`Hungarian`。在二分图中根据Konig定理可以知道$|M| = |C_v|$于是得到$|I| = |V| - |C_v| = |V| - |M|

不想染色？

建立两层的图包括副本，然后的话我们只让它跨层连接，跨层连接的一定可以对应到一层，而我们如果建的是双向边，也就是跨层交叉的话，匹配方案数除以二就可以啦

其实本质也是属于染色

虽然说边少转化成二分图貌似可以不让他npc,但是感觉时间复杂度还是有点玄学，所以犹豫了好久——疑问脸

总结一下大概就是 最大独立集＝二分图点数－最小点覆盖＝最长反链长度＝最小链覆盖(路径不能相交)

[HEOI2012]朋友圈

求最大团

最初想法是直接建补图求最大独立集，和前面一样.但是看了下题解，好像不是这样的，显然是姿势太naive

如果只考虑B国那么只需要求B国的补图然后求最大匹配算最大独立集，

因为B国补图连边的条件时奇偶性不同并且or有奇数个1

对于A国，根据鸽巢原理，选三个的话就会有出现奇偶性一致的，也就是说补图中这是三个至少有一条连边，显然三者不能同时处在一个补图的最大独立集中。

然后对于枚举的几个A国，选出和它们都有关系的B国同学，对B国同学乱搞一下就可以了。

做题时草稿太乱，逻辑有点被题解区带歪。。

参考： https://blog.csdn.net/dogeding/article/details/83031414

poj3680 区间图的最大权独立集问题

某一场cf的题目

还没看的blog

https://yzmduncan.iteye.com/blog/1149057

退火和最大团

matrix的与或门?

https://www.baidu.com/link?url=Ab-GZVGn73nI1lvJelIRF4Tw9JeC0Xzm1zm9VOrxJvG94PQnY0f4tUJnsvVLE1M3DWCN_NIqPc11-O5C4YGBCYk0szCCGp4zr_E-2kL7kVu&wd=&eqid=d341fc0000041e16000000065cb2fdf6

https://blog.csdn.net/roufoo/article/details/79314431

https://blog.csdn.net/qq_39599067/article/details/80685961

https://www.cnblogs.com/patrickzhou/p/5853109.html

https://baike.baidu.com/item/%E6%94%AF%E9%85%8D%E9%9B%86 支配树和支配图是什么关系？

https://wenku.baidu.com/view/1c3d58615627a5e9856a561252d380eb6294239e.html