二分图的点覆盖与独立集

写给自己复习用的,可能不太适合阅读

二分图的最小点覆盖

用最少的点覆盖二分图的所有边,即找到一个点集S,使得二分图中的每一条边都至少有一个端点属于S,且|S|尽量小。

König 定理

二分图的最小点覆盖的点数等于最大匹配包含的边数。

从每个左部非匹配点开始再跑一次匈牙利算法,标记沿途经过的每个点,然后选择左部未被标记的点和右部被标记的点即可。

正确性证明见书P428。

但需要提到的是,左部未被标记的点是匹配点,但并非所有左部匹配点都未被标记。右部被标记的点是匹配点,但并非所有右部匹配点都被标记。

求解最小点覆盖类问题通常有一个特征,即题中内容可以抽象成二分图,每条边都必须被覆盖,求解最少的点。

二分图的最大独立集

二分图的最大独立集是指:满足点集S内任意两点之间都没有边,且SG(V,E)V的子集的最大S

G(V,E)的最大独立集的大小等于|V|减去最大匹配数。

对比:

棋盘覆盖

骑士

这两个题看似相似,其实求解方式完全不同。

棋盘覆盖求最大骨牌数。将相邻两个没被禁止的格子连上一条边,一条边即可对应一个骨牌。(每条边代表一个骨牌)所以要求解的是最多不产生矛盾的边数,即最大匹配。

骑士放置求解的是放置的骑士数。将没被禁止的能互相攻击到的骑士连边,我们要求解的是内部没有边相连的最大点集(每个点代表一个骑士),即最大独立集。

DAG 的最小路径点覆盖

用尽量少的不相交的简单路径覆盖有向无环图的所有顶点,这个问题被叫做最小路径点覆盖。

G(V,E)的所有点拆成入点和出点,构成拆点二分图G_2(V',E')将入点作为左部点x,出点作为右部点x'。对每一条边E(x,y),在G_2中连接xy'|V|减去G_2的最大匹配数即为答案。

如果简单路径可相交,进行一次传递封包即可。

证明略。

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注