等价关系一

一个图是二分图$<=>$染色过程中不存在矛盾$<=>$图中不存在奇数环

$Example:$

① 二分+染色法判断最大匹配：关押罪犯

② 将放置$1×2$的方格问题转化成奇偶坐标点之间的匹配，最后求最大匹配数：棋盘覆盖

等价关系二

最小点覆盖$<=>$最大匹配数$<=>$总点数-最大独立集$<=>$总点数-最小路径覆盖

最小点覆盖：选出最少的点将图中所有边全部覆盖
最大独立集：选出最多的点且选出的点之间没有边
最大团：选出最多的点，使得任意两点之间都有边(原图的最大独立集就是补图的最大团)
增广路径：连同两个未匹配顶点的路径，即从一个未匹配的顶点到另一个未匹配的顶点之间的路径

证明$1$：最小点覆盖数$n$$<=>$最大匹配数$m$

① 证明$n≥m$。因为对于最大匹配中的所有匹配边来说，它们之间没有公共点，所以要覆盖这$m$条匹配边就需要选上这些边中的$m$个端点，所以$n≥m$

② 证明等号可以成立。这里使用构造性证明

1° 求出二分图中最大匹配，如下图中红色边

2° 从左边每个非匹配点出发，做一遍增广路径(一定不会成功，因为如果存在增广路径，那么一定可以使最大匹配多一个(画图举例易得)，标记路径中左右所有的点

做完上面两步之后，就可以构造出一个最小点覆盖的方案，方案中包含的点为：左边所有未被标记的点 $+$ 右边所有未被标记的点

3° 我们来讨论这么构造的方案是否可以将所有的边都覆盖

我们可以将所有边分为四类：记匹配点为$P$、非匹配点为$Q$
则所有种类的边按左$<$–$>$右分为：$P<$–$>P$、$Q<$–$>Q$、$P<$–$>Q$、$Q<$–$>P$
3.1° 如果是$P<$–$>P$，由图中性质$3$可以知道匹配边要么同时被标记，要么同时不被标记，前者一定会被右边所选的标记点覆盖，后者一定会被左边选的非标记点覆盖,所以这一类边被全覆盖
3.2° 如果是$Q<$–$>Q$，如果存在这类边，则不是最大匹配，所以这类边不存在
3.3° 如果是$P<$–$>Q$，如果这个匹配点被标记了，那么这个非匹配点也一定会被标记，所以选的右边的标记点会将这条边覆盖，如果这个点没被标记，即如下图形式，那么选的坐标的未被标记点也可以将这个边覆盖，所以这一类边被全覆盖
3.4° 如果是$Q<$–$>P$，易知这类边一定被全覆盖
综上，采取这类方式构造的解一定可以将所有边全覆盖，而这种选法的每个点都是每条匹配点的一个且仅一个端点，所以选的点数$n$=最大匹配边数$m$
又$n≥m$，所以$n$最小可以取到$m$，因为$n$是最小点覆盖
故：$n=m$
模板题：机器任务

证明$2$：最大独立集$<=>$总点数$n-$最大匹配数$m$

最大独立集为$n-m$，即要去掉$m$个点将图中所有边都破坏掉，使剩下的点最多，要剩下最多即要去掉最少，而最小点覆盖即用最少的点将所有边全覆盖，所以只需去掉最小点覆盖即可，而最小点覆盖$=$最大匹配
故：最大独立集$<=>$总点数$n-$最大匹配数$m$
模板题：骑士放置

等价关系三

最小路径点覆盖(非重复)$<=>$总点数-最大匹配数

最小路径重复点覆盖$<=>$整个图传递闭包后的最小点覆盖(非重复)

$Ps$：最小路径点覆盖(非重复)：选出最少的没有交点的路径，覆盖所有的点
$Ps$：最小重复点覆盖即选出的路径中点和边均可重复

证明1：最小路径点覆盖(非重复)$<=>$总点数-最大匹配数

① 拆点建图

将每个点拆到两侧，一个起点一个终点，将每条边$i->j$都转化成左边$i$到右边$j’$的一条边，这样就转化成一个二分图

② 最少路径转化成最大匹配

因此将原图中的每条路径都可以转化成二分图中的一组匹配(没有公共点)。因为是$DAG$(有向无环图)，因此除了出度为0的点(终点)都会和其他点之间有边，即和右侧的点存在匹配边。要选最少的路径来覆盖所有点，路径最少即终点最少，在所有非终点都会与右侧形成匹配的前提下，即求左侧非匹配点(终点)的最少个数

③ 求左侧非匹配点的最少个数

要求非匹配点的最少个数，只需求出匹配点的最大个数，即最大匹配，再用总点数减去匹配数量即可

综上：最小路径点覆盖$<=>$总点数-最大匹配数

证明2：最小路径重复点覆盖$<=>$整个图传递闭包后的最小点覆盖(非重复)

① 所有含有重复点的路径$=>$不含重复点的路径

将所有的含有重复点的路径换成传递闭包后的路径(传递闭包：间接能到的点都转化为直接能到)，就可以得到不含有重复点的覆盖路径

② 不含重复点的路径$=>$含有重复点的路径

将所有直接到达的点按照①中的方法展开即可得到含有重复点的路径

综上，最小路径重复点覆盖、整个图传递闭包后的最小点覆盖(非重复)中的路径元素是相同的(数量也相同)，因此具有相同的最小路径数量，即等价

$Examle:$

从有向无环图中选出最多的点使得任意两点之间都没有边：捉迷藏