最小点覆盖问题
KÖNIG 定理
最⼤匹配边数 = 最⼩点覆盖点数
证明
从边的匹配情况思考：
-
匹配边：2个红点，任选一个
-
非匹配边：
(i).一红一蓝，选红点更优（红点一定有其它的点与其相连，蓝点不一定）
(ii).两红，任选一个，因为一定不会出现一下情况，所以一定能做到在非匹配边的两个红点与其所对应的另外两个红点共四个红点中，只选出两个就能满足当前的情况
实现
先求最大匹配，然后从右侧所有非匹配点开始 dfs， 从右侧向左侧走，只能走非匹配边，从左侧到右侧走，只能走匹配边，最后，取出所有左边的被 dfs 到的点和右边的未被 dfs 到的点，就是最小点覆盖
证明：一条边不被覆盖当且仅当左边未被 dfs 到，右边被 dfs 到。
右边被 dfs 到了，他如果是非匹配点，他必将便利左侧所有相连点。
如果他是匹配点，那么他肯定是由左侧的匹配点过来的，过来的左侧点肯定被访问了，其他的左侧点会被他访问。
所以，一个与右侧被 dfs 到的点相连的所有左侧点都会被 dfs 到，不存在上述情况
最大独立集
定理
最大独立集=总点数-最大匹配边数
证明
选出最多的点构成独立集
\(\Leftrightarrow\) 在图中去掉最少的点，使剩下的点之间没有边
\(\Leftrightarrow\) 用最少的点覆盖所有的边
\(\Leftrightarrow\) 总点数-最小点覆盖点数
独立集与最大团
定理
无向图的最大团等于其补图的最大独立集
补图
⽆边图的补图是完全图，反之亦然。
独⽴集的补图是团，反之亦然。
triangle-free graph的补图是claw-free graph。
self-complementary graph是⼀个与⾃⼰的补图同构的图。
Cograph是由不交并（可参考集合论的的不交并）以及补集建⽴起来图的集
合。⽽且，这个集合是self-complementary；也就是说，任何cograph的补图
也必然是cograph（虽然可能不是同构的图）。
最小路径覆盖
有向无环图
不相交路径覆盖
做法
将原图的每个点\(x\)拆成\(x\)和\(x+n\)两个点，形成二分图：
1~n为左部，n+1~2n为右部，若原图存在有向边\((x,y)\)，在二分图左部点\(x\)与右部点\((y+n)\)连边
定理
有向无环图的最小路径覆盖的路径条数=总点数-拆点二分图的最大匹配
证明
最小路径覆盖中的所有边将是拆点二分图中的一组匹配
一条路径，只有终点没有出边，所以终点没有匹配
路径条数最少
\(\Leftrightarrow\) 路径终点数最少
\(\Leftrightarrow\) 二分图左部的非匹配点最少
可相交路径覆盖
将所有通过其他的点间接连接起来的两个点直接相连，然后就能转换为不相交路径覆盖问题
特殊
如题目「POJ3020」Antenna Placement与「POJ2724」 Purifying Machine，这两道题都是相邻两点间可以有一条路径，但一条路径包含的点数小于等于2，也就是说不能将有交集的路径合二为一
实现
这时候，就可以舍去拆点二分图，因为原图本身就是一张二分图（考虑黑白染色，相邻两点的颜色不同，就像国际象棋的那个格子一样，发现只有不同颜色之间才有连边）
在原图上跑匈牙利算法，答案就是总点数-最大匹配边数
证明
最大匹配就是让两个点连在一起且连边不相交，对于题目而言，可以转化为最大匹配的模式（这样一定是最优解）
总点数-最大匹配边数*2得到的就是落单的点，它们自称一条路径，而两两匹配的点总用一条路径，也就是说两两匹配的点共用掉了最大匹配边数个路径，所以答案是总点数-最大匹配边数
链与反链
Dilworth定理
最小链覆盖=最长反链长度=总点数-最大匹配边数
前提
在有向无环图中
实现
最小链覆盖和最小路径覆盖的区别是，最小链覆盖允许路径相交，所以使用可相交路径覆盖的做法即可（反链也需要传递连通性/传递闭包）
证明
最小链覆盖
如果没有边，每个点自成一条链
每当一条边联通两条链，两条链合为一条链，答案-1
所以答案减少的越多越好，而链又不能相交，所以减少的答案最大就是最大匹配边数
最长反链
虽然不知道对不对。。。可以理解为传递闭包后的求独立集
