「Algorithm」图匹配相关学习笔记

二分图的最大匹配，最小点覆盖，最小边覆盖，最大独立集

DAG的最小路径覆盖，最小链覆盖（可相交路径覆盖），最大独立集，最长反链

二分图

注：此部分中 $n$ 表示图中总点数（两部分点数的总和）， $P$ 表示最大匹配数

选出尽量多的边，使得每个点至多是其中一条边的端点

建源点汇点，从 $S$ 向左边每个点连流量为 $1$ 的边，右边每个点向 $T$ 连流量为 $1$ 的边，原图中的边流量为 $1$ ，跑最大流

显然中间部分每条边最多流量为 $1$ ，每个点最多被一条边包含，且选出来的边最多

选出尽量少的点，使得每条边至少有一个端点被选出

最小点覆盖，就是最大流

不难发现上面建图的最小割就是最小点覆盖

显然割掉中间的边不会比割两侧的边优，割两侧的边就代表选择相应的点

同一张网络流的图中，最大匹配是利用了中间流的情况，最小点覆盖是利用了两侧割的情况，但是本质是一样的

选出尽量少的边，使得每个点至少是一条选出的边的端点

最小边覆盖 $= n-P$ ，就是最小割

要尽量使得选出的边贡献最大，也就是先做最大匹配

匹配边每条边都会产生 $2$ 的贡献（连接的两个点都不重复），那么这里就已经选出 $P$ 条边，个点了

还剩下 $n-2P$ 个点不能和其他点匹配，那么会有条边

总边数为 $P + (n-2P) = n - P$

选出尽量多的点，使得点两两之间没有边连接

最大独立集 $=n-P$

推论：最大点权独立集 $=$ 总权值 $-$ 最小点权覆盖集（NOIp2018 保卫王国）

最大匹配没有选出来的所有点，它们两两之间没有连边，这里有 $n-2P$ 个点

显然，最大匹配的两个点不可能同时还向另外一侧有连边（否则最大匹配数能+1），因此最大匹配的两个点能任意再选一个，这里有个点

总点数为 $(n-2P) + P = n-P$

UPD另外一种理解方法

最大独立集 + 最小点覆盖 = 所有点

这是因为最小点覆盖把所有边都包含了，所以对于每个在最大独立集中的点，它连向的点都在最小点覆盖中

这样理解的话便于输出方案，只要用最小点覆盖的做法，跑网络流的时候把两侧没有被割的点输出即可

用最少的不相交路径，覆盖所有点恰好一次

一开始每个点都独立为一条路径，在二分图中匹配就是将路径合并（即匹配的这两个点在同一条路径上）

因为二分图的匹配中不能有公共点，显然这样做出来路径没有交

用最少的可以相交的路径，覆盖所有点至少一次

先跑一遍传递闭包，然后就转化成了最小路径覆盖

这个很显然，因为在原图中两条相交的路径都能在新图中转化成不相交的

反链：DAG中的一个点集，链上任意两个点 $x$ , $y$ ，满足 $x$ 不能到达 $y$ ，且 $y$ 也不能到达 $x$

最长反链长度 $=$ 最小链覆盖

最长链长度 $=$ 最小反链覆盖

证明真心没看懂