等价关系一
一个图是二分图$<=>$染色过程中不存在矛盾$<=>$图中不存在奇数环
$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:$
从有向无环图中选出最多的点使得任意两点之间都没有边:捉迷藏