二分图相关学习笔记

前置知识

一、二分图最小点覆盖

点覆盖：一个点集，使得每条边都至少与该点集中一个点相连。
最小点覆盖：点数最小的点覆盖，即：任意真子集不是点覆盖的点覆盖。

二分图最小点覆盖=二分图最大匹配
证明：(König) 定理
不难发现，要覆盖所有的匹配边至少需要最大匹配数的点。(可以看做一个下界)

求最小点覆盖的过程(严格证明)：
可以思考二分图匹配时求增广路的过程，事实上是以一个未匹配点为起点寻找交错路(匹配边和非匹配边交错出现的路径)，当找到一个在交错路上未匹配点时，就成功找到一条增广路。
显然地，当二分图已是最大匹配时，每一次试图增广都会因为找不到未匹配点而失败。
从左边所有未匹配点开始跑交错路，给经过的节点打标记，最后，左边没有标记的点和右边有标记的点就是最小覆盖点集。

设二分图的最大匹配数为 (N)

为什么得到的点集大小刚好为 (N)？点集中每个点与匹配一一对应，理由如下：

		1.左边的非匹配点会当做起点被标记；
		2.从左边的未匹配点开始，走不到右边的未匹配点，否则就会找到一条完整的增广路；
		3.对于匹配边，左端点只能从右端点跑过来，所以左右端点只能同时有或没有标记。

为什么点集可以覆盖所有边？没有边是左端点有标记，右端点没有标记的，理由如下：

		1.非匹配边：右端点可以从左端点通过这条边到达。
		2.匹配边：上文已经提到。

(可配合画图理解)

二、二分图最大独立集

独立集：一个点集，集合中任意两点没有变相连。
最大独立集：点数最多的独立集。

二分图最大独立集=点数-二分图最小点覆盖=点数-二分图最大匹配

求独立集的过程可以看成：在图中选一些点，删除这些点和与该这些点相连的所有边，直到所有边都被删掉，剩下的就是独立集。所以最大独立集和最小点覆盖互为补集。

三、(DAG) 相关

(1) 路径不可相交最小链覆盖

可以把点 (x) 拆成两个点 (A_x,B_x)；
若在原图中 (x->y) 有边，则在新图中连接 (B_x->A_y)，跑二分图最大匹配即可。
(DAG) 最小路径覆盖=原图的点数-新图的最大匹配。
证明：先把原图中的点分别看做一个点的路径，考虑新图中一条边作为匹配边的意义——在原图中将两个点相连，使得路径数减一。