写给自己复习用的,可能不太适合阅读
二分图的最小点覆盖
用最少的点覆盖二分图的所有边,即找到一个点集,使得二分图中的每一条边都至少有一个端点属于
,且
尽量小。
König 定理
二分图的最小点覆盖的点数等于最大匹配包含的边数。
从每个左部非匹配点开始再跑一次匈牙利算法,标记沿途经过的每个点,然后选择左部未被标记的点和右部被标记的点即可。
正确性证明见书P428。
但需要提到的是,左部未被标记的点是匹配点,但并非所有左部匹配点都未被标记。右部被标记的点是匹配点,但并非所有右部匹配点都被标记。
求解最小点覆盖类问题通常有一个特征,即题中内容可以抽象成二分图,每条边都必须被覆盖,求解最少的点。
二分图的最大独立集
二分图的最大独立集是指:满足点集内任意两点之间都没有边,且
是
中
的子集的最大
。
的最大独立集的大小等于
减去最大匹配数。
对比:
这两个题看似相似,其实求解方式完全不同。
棋盘覆盖求最大骨牌数。将相邻两个没被禁止的格子连上一条边,一条边即可对应一个骨牌。(每条边代表一个骨牌)所以要求解的是最多不产生矛盾的边数,即最大匹配。
骑士放置求解的是放置的骑士数。将没被禁止的能互相攻击到的骑士连边,我们要求解的是内部没有边相连的最大点集(每个点代表一个骑士),即最大独立集。
DAG 的最小路径点覆盖
用尽量少的不相交的简单路径覆盖有向无环图的所有顶点,这个问题被叫做最小路径点覆盖。
将的所有点拆成入点和出点,构成拆点二分图
将入点作为左部点
,出点作为右部点
。对每一条边
,在
中连接
与
。
减去
的最大匹配数即为答案。
如果简单路径可相交,进行一次传递封包即可。
证明略。