$$二分图的拓展$$

$二分图的最小点覆盖$

$给定一张二分图,求一个最小点集S,使得图中任何一条边都有一个端点v\in S$

$这类问题被称为二分图的最小点覆盖$

$König定理$

$二分图的最小点覆盖点数 = 二分图最大匹配$

$证明$

$对于一个二分图,先求出他的最大匹配,取每条匹配边的右部端点覆盖二分图$

$从左部每一个非匹配边出发,做一次dfs寻找增广路,标记访问过的节点$

$对于每一条边,都对应一个左部端点和右部端点$

$若左部端点是匹配点,那么这条边已经被覆盖了$

$若左部端点是非匹配点,对于右部端点$

$若右部端点是非匹配点,则这条边可以算入最大匹配,于最大匹配不符$

$所以右部端点一定是匹配点,那么这条边已经被覆盖了$

$综上所述,二分图的最小点覆盖等于二分图最大匹配$

$证毕$

$二分图最大独立集$

$给定一张无向图G = (V, E)$

$图中的一个点集S满足任何两点之间都没有直接连边的被称为图的一个独立集$

$独立集集合中点数最多的被称为最大独立集$

$对应的,图中的一个点集S满足任何两点之间存在直接连边的被称为图的一个团$

$团集合中点数最多的被称为最大团$

$定理$

$二分图最大独立集点数 = 总点数 - 二分图最大匹配$

$证明$

在一张图中取最多的点构成独立集

相当于在图中去掉最少的点,使得两点之间没有连边

又相当于用最少的点覆盖图中的所有边

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

$证毕$

$有向无环图的最小路径覆盖$

有向无环图的最小路径覆盖,指用最少的路径,每条路径把经过的所有点的值加1

使得最后所有点的值都为1

$拆点二分图$

$对于任意有向无环图,把图上所有点v拆成两部分,v和v’$

$原点v的所有出边从v连出, 原点v的所有入边都从某一点连向v’$

$则拆点后的有向无环图一定是二分图,被称为拆点二分图$

$定理$

$最小路径覆盖条数 = 总点数 - 拆点二分图最大匹配$

$证明$

$求最小路径覆盖$

$就相当于在拆点二分图上路径终点(左部点未匹配)最少,使得覆盖所有点$

$就相当于拆点二分图左部未匹配点最少$

$也就是 左部总点数 - 二分图最大匹配数$

$即最小路径覆盖条数 = 总点数 - 拆点二分图最大匹配$

$证毕$

$总结$

$综上,二分图最大匹配$
$= 二分图最小点覆盖$
$= 总点数 - 二分图最大独立集点数$
$= 总点数 - 最小路径覆盖条数$