0x69 二分图的覆盖与独立集

$\spadesuit$ 二分图最小点覆盖

给定一张二分图，求出一个最小的点集 $S$ ，使得图中任意一条边都有至少一个端点属于 $S$ 。这个问题被称为二分图的最小点覆盖（vertex cover），简称最小覆盖。

König定理

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

证明：

首先，因为最大匹配是原二分图边集的一个子集，并且所有边都不相交，所以至少需要从每条匹配边中选出一个端点。因此，最小点覆盖包含的点数不可能小于最大匹配包含的边数。如果能对任意二分图构造出一组点覆盖，其包含的点数等于最大匹配包含的边数，那么定理就能得证。构造方法如下：

1. 求出二分图最大匹配。

2. 从左部每个非匹配点出发，再执行一次DFS寻找增广路的过程（一定会失败），标记访问过的节点。

3. 取左部未被标记的点、右部被标记的点，就得到了二分图最小点覆盖。

下面证明该构造的正确性。经过上述构造方法后：

1. 左部非匹配点一定都被标记——因为它们是出发点。

2. 右部非匹配点一定都没被标记——否则就找到了增广路。

3. 一对匹配点要么都被标记, 要么都没被标记——因为在寻找增广路的过程中, 左部匹配点只能通过右部到达。

在构造中，我们取了左部未被标记的点、右部被标记的点。根据上面的讨论可以发现，恰好是每条匹配边取了一个点，所以选出的点数等于最大匹配包含的边数。

再来讨论这种取法是否覆盖了所有的边：

1.匹配边一定被覆盖——因为恰好有一个端点被取走。
2. 不存在连接两个非匹配点的边——否则就有长度为1的增广路了。
3. 连接左部非匹配点 $i$ 、右部匹配点 $j$ 的边——因为 $i$ 是出发点，所以 $j$ 一定被访问。而我们取了右部所有被标记的点，因此这样的边也被覆盖。
4. 连接左部匹配点 $i$ 、右部非匹配点 $j$ 的边—— $i$ 一定没有被访问，否则再走到 $j$ 就找到了增广路。而我们取了左部所有未被标记的点，因此这样的边也被覆盖。

证毕。

【例题】Machine Schedule POJ1325

有两台机器 $A, B$ 及 $N$ 个任务。每台机器有 $M$ 种不同的模式。

对于每个任务 $i(1 \leq i \leq N)$ , 给定两个整数 $a[i]$ 和 $b[i]$ , 表示如果该任务在 $A$ 上执行, 需要设置模式为 $a[i]$ , 如果在 $B$ 上执行, 需要模式为 $b[i]$ 。

任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。求怎样分配任务并合理安排顺序，能使机器重启次数最少。

数据范围： $1\leq N,M\leq 100$ ， $1\leq a[i],b[i]\leq M_{\circ}$

在二分图最大匹配的例题中，我们经常寻找题目里的“0要素”和“1要素”，作为解答的突破口。二分图最小覆盖的模型特点则是：每条边有2个端点，二者至少选择一个。我们不妨称之为“2要素”。如果一个题目具有“2要素”的特点，那么可以尝试抽象成二分图最小覆盖模型求解。

在这道题目中，每个“任务”要么在机器 $A$ 上以模式 $a[i]$ 执行，要么在机器 $B$ 上以模式 $b[i]$ 执行，二者必选其一。因此，我们可以把机器 $A$ 的 $M$ 种模式作为 $M$ 个左部点，机器 $B$ 的 $M$ 种模式作为 $M$ 个右部点，每个任务作为无向边，连接左部的第 $a[i]$ 个节点与右部的第 $b[i]$ 个节点。

这张图显然是一张二分图，求出它的最小覆盖，就等价于用尽量少的模式（启动次数）来执行所有的任务。时间复杂度为 $O(NM)$ 。

【例题】Muddy Fields FOJ2226

在一块 $N * M$ 的网格状地面上，有一些格子是泥泞的，其他格子是干净的。现在需要用一些宽度为 1、长度任意的木板把泥地盖住，同时不能盖住干净的地面。每块木板必须覆盖若干个完整的格子，木板可以重叠。求最少需要多少块木板。 $N, M \leq 50$ 。

每块泥地 $(i,j)$ 要么被第 $i$ 行的一块横着的木板盖住，要么被第 $j$ 列的一块竖着的木板盖住，二者至少选择一个，这是本题的“2要素”。

因为木板不能盖住干净的地面，所以横着的木板只能放在同一行若干个连续的泥地上，竖着的木板只能放在同一列若干个连续的泥地上。我们把这些连续的泥地分别称为“行泥泞块”和“列泥泞块”。如下图所示：

把“行泥泞块”作为二分图左部节点，“列泥泞块”作为二分图右部节点。对于每块泥地，在它所属的“行泥泞块”与“列泥泞块”之间连边。

求出二分图的最小覆盖，就是用最少的木板（放在泥泞块里）覆盖所有的泥地。

$\spadesuit$ 二分图最大独立集

给定一张无向图 $G = (V,E)$ ，满足下列条件的点集 $S$ 被称为图的独立集：

1. $S\subseteq V$

2. $\forall x,y\in S,(x,y)\notin E$

通俗地讲，图的独立集就是“任意两点之间都没有边相连”的点集。包含点数最多的一个就是图的最大独立集。

对应地，“任意两点之间都有一条边相连”的子图被称为无向图的“团”。点数最多的团被称为图的最大团。

定理

无向图 $G$ 的最大团等于其补图 $G^{\prime}$ 的最大独立集。

注： $G^{\prime} = (V,E^{\prime})$ 被称为 $G = (V,E)$ 的补图，其中 $E^{\prime} = \{(x,y)\notin E\}$

正确性显然。值得提醒的是，在一些题目中，补图转化思想能成为解答的突破口。

对于一般无向图，最大团、最大独立集是 NPC 问题①。

定理

设 $G$ 是有 $n$ 个节点的二分图， $G$ 的最大独立集的大小等于 $n$ 减去最大匹配数。证明：

选出最多的点构成独立集

$\Leftrightarrow$ 在图中去掉最少的点，使剩下的点之间没有边

$\Leftrightarrow$ 用最少的点覆盖所有的边

因此，去掉二分图的最小点覆盖，剩余的点就构成二分图的最大独立集。而最小点覆盖数等于最大匹配数。故最大独立集大小等于 $n$ 减去最大匹配数。

证毕。

【例题】骑士放置

给定一个 $N * M$ 的棋盘，有一些格子禁止放棋子。问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。

与例题“棋盘覆盖”类似，对棋盘进行黑白染色，黑、白色的格子分别作为二分图左、右部节点。

若两个格子是“日”字的对角（能互相攻击到），则在它们对应的节点之间连边。容易发现，“日”字的两个对角格子的颜色一定不同。因此，我们建出的图确实是一张二分图。

求上述二分图的最大独立集即可。

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

给定一张有向无环图，要求用尽量少的不相交的简单路径，覆盖有向无环图的所有顶点（也就是每个顶点恰好被覆盖一次）。这个问题被称为有向无环图的最小路径点覆盖，简称“最小路径覆盖”。

设原来的有向无环图为 $G = (V,E)$ ， $n = |V|$ 。把 $G$ 中的每个点 $\mathcal{X}$ 拆成编号为 $\mathcal{X}$ 和 $x + n$ 的两个点。建立一张新的二分图， $1\sim n$ 作为二分图左部点， $n + 1\sim 2n$ 作为二分图右部点，对于原图的每条有向边 $(x,y)$ ，在二分图的左部点 $\mathcal{X}$ 与右部点 $y + n$ 之间连边。最终得到的二分图称为 $G$ 的拆点二分图，记为 $G_{2}$ 。

定理

有向无环图 $G$ 的最小路径点覆盖包含的路径条数，等于 $n$ 减去拆点二分图 $G_{2}$ 的最大匹配数。

证明：

在有向无环图 $G = (V, E)$ 的最小路径覆盖中，对于任意的 $x \in V$ ，因为路径不相交，所以 $x$ 的入度和出度都不超过 1。因为每个节点都被覆盖，所以 $x$ 的入度和出度至少有一个是 1。

因此，最小路径覆盖中的所有边，在拆点二分图 $G_{2}$ 中构成一组匹配。最小路径覆盖中每条边 $(x,y)$ 的起点 $x$ 与二分图每条匹配边 $(x,y + n)$ 的左部点 $x$ 是一一对应的。

特别地，对于每条路径的终点 $t$ ，因为 $t$ 没有出边，所以在二分图中， $t$ 匹配失败。即路径的终点和二分图左部的非匹配点是一一对应的。

路径覆盖包含的路径条数最少

$\Leftrightarrow$ 路径的终点数（出度为0的点数）最少
$\Leftrightarrow$ 二分图左部非匹配点最少

故 $G$ 的最小路径覆盖的路径数等于 $n$ 减去拆点二分图 $G_{2}$ 的最大匹配数。证毕。

给定一张有向无环图，要求用尽量少的可相交的简单路径，覆盖有向无环图的所有顶点（也就是一个节点可以被覆盖多次）。这个问题被称为有向无环图的最小路径可重复点覆盖。

在最小路径可重复点覆盖中，若两条路径 $\dots \rightarrow u \rightarrow p \rightarrow v \rightarrow \dots$ 和 $\dots \rightarrow x \rightarrow p \rightarrow y \rightarrow \dots$ 在点 $p$ 相交，则我们在原图中添加一条边 $(x, y)$ ，让第二条路径直接走 $x \rightarrow y$ ，就可以避免重复覆盖点 $p$ 。

进一步地，如果我们把原图中所有间接连通的点对 $x, y$ 直接连上有向边 $(x, y)$ ，那么任何“有路径相交的点覆盖”一定都能转化成“没有路径相交的点覆盖”。

综上所述，有向无环图 $G$ 的最小路径可重复点覆盖，等价于先对有向图传递闭包，得到有向无环图 $G^{\prime}$ ，再在 $G^{\prime}$ 上求一般的（路径不可相交的）最小路径点覆盖。

【例题】Vani和Cl2捉迷藏 TYVJ1957/BZOJ2718/BZOJ1143

Vani 和 cl2 在一片树林里捉迷藏。这片树林里有 $N$ 座房子， $M$ 条有向道路，组成了一张有向无环图。 $N \leq 200, M \leq 30000$ 。

树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。如果从房子 $A$ 沿着路走下去能够到达 $B$ ，那么在 $A$ 和 $B$ 里的人是能够相互望见的。

现在cl2要在这 $N$ 座房子里选择 $K$ 座作为藏身点，同时Vani也专挑cl2作为藏身点的房子进去寻找，为了避免被Vani看见，cl2要求这 $K$ 个藏身点的任意两个之间都没有路径相连。

为了让Vani更难找到自己，cl2想知道最多能选出多少个藏身点。

输入数据的第一行是两个整数 $N$ 和 $M$ 。接下来 $M$ 行，每行两个整数 $x, y$ ，表示一条从 $x$ 到 $y$ 的有向道路。输出一个整数 $K$ ，表示最多能选取的藏身点个数。

题目所求的最多能选取的藏身点个数，就等于最小路径可重复点覆盖包含的路径条数。我们对题目中给出的有向无环图 $G$ 进行传递闭包，得到一张新的有向无环图 $G'$ ，然后求出拆点二分图 $G_2'$ 的最大匹配，输出 $N$ 减 $G_2'$ 的最大匹配数即可。

接下来我们证明上述结论。只需证明：在 $G'$ 中最多能选取的藏身点数等于 $G'$ 的最小路径点覆盖（路径不可相交）包含的路径条数。

设藏身点集合为 $hide$ ，最小路径点覆盖的路径集合为 $path$ 。显然， $path$ 的每条路径上至多选出 1 个点。而 $path$ 覆盖了所有节点，故 $|hide| \leq |path|$ 。若我们能构造出一种使得 $|hide| = |path|$ 的方案，即可完成证明。

先求出 path 的具体方案。设节点 $x \in G'$ 在拆点二分图 $G_2'$ 中对应左部点 $x$ 和右部点 $x'$ 。

1. 依次考虑左部每一个非匹配点 $x_0$ 。

2. 从 $x_0$ 出发，不断访问 $x_0, \text{match}[x_0']$ , $\text{match}[\text{match}[x_0']']$ ，直至到达一个左部点 $y_0$ ，满足它对应的右部点 $y_0'$ 是非匹配点。

3. 在 $G'$ 中，节点 $x_0, y_0$ 以及刚才经过的点构成一条路径， $y_0$ 是起点， $x_0$ 是终点。

上述找到的所有路径就是覆盖 $G^{\prime}$ 中所有点的一个方案，且路径互不相交。

下面给出从 path 的每条路径上选出一个藏身点的方法：

1. 选出 path 中每条路径的终点 $x_0$ ，构成一个集合 $E$ 。

2. 求出从 $E$ 中节点出发，走一条边，到达的节点集合 next(E)。

3. 根据传递闭包的性质， $G$ 中任意两个藏身点没有路径相连，等价于 $G'$ 中任意两个藏身点都没有边相连。因此，若 $E \cap next(E) = \emptyset$ ，则 $hide = E$ 即为所求。

4. 否则，考虑 $E \cap \text{next}(E)$ 中的每个节点 $e$ ，沿着 $e$ 所在的路径向上走，直到一个节点 $e' \notin \text{next}(E)$ 。从 $E$ 中删除 $e$ ，加入 $e'$ 。

5. 对于修改后的集合 $E$ ，重复执行步骤 $3\sim 4$ ，直至步骤3中的条件满足。

可以证明，任何时刻在步骤4中，我们一定能找到合法的 $e^{\prime}$ 。这是因为如果找不到这样的 $e^{\prime}$ ，就说明 $e$ 所在路径（记为 $pe$ ）上的所有点都能够被其他路径的终点到达。设 $pe$ 的起点是 $y_0$ ，我们可以延长那条到达 $y_0$ 的路径，代替 $pe$ 去覆盖 $pe$ 上的所有节点，使集合 path 中的路径减少一条，与 path 的最小性矛盾。

以下程序求出本题的解，同时实现了藏身点方案的构造过程：

bool c1[222][222]; //邻接矩阵  
int match[222], n, m;  
bool vis[222], succ[222];  
int hide[222]; //藏身点集合

bool dfs(int x) {  
    for (int i = 1; i <= n; i++)  
        if (cl[x][i] && !vis[i]) {  
            vis[i] = true;  
            if (!match[i] || dfs(match[i])) {  
                match[i] = x;  
            return true;  
        }  
    }  
    return false;

int main(){ //读入 cin>>n>>m; for (int i = 1; i <= m; i++) { int x, y; scanf("%d%d", &x, &y); cl[x][y] = 1; } //Floyd传递闭包 for (int i = 1; i <= n; i++) cl[i][i] = 1; for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { cl[i][j] |= cl[i][k] && cl[k][j]; for (int i = 1; i <= n; i++) cl[i][i] = 0; //在拆点二分图上求最大匹配 int ans = n; for (int i = 1; i <= n; i++) { memset(vis, 0, sizeof(vis)); ans  $= =$  dfs(i); } cout << ans << endl; //构造方案，先把所有路径终点（左部非匹配点）作为藏身点 for (int i = 1; i <= n; i++) succ-match[i] = true; for (int i = 1, k = 0; i <= n; i++) if (!succ[i]) hide[++k] = i; memset(vis, 0, sizeof(vis)); bool modify  $=$  true; while (modify){ modify  $=$  false; //求出next Hide) for (int i = 1; i <= ans; i++) for (int j = 1; j <= n; j++) if (cl[hide[i]][j]) vis[j] = true; for (int i = 1; i <= ans; i++) if (vis[hide[i]]) { modify  $=$  true; //不断向上移动 while (vis[hide[i]]) hide[i]  $=$  match[hide[i]];

}   
}   
for (int i = 1; i <= ans; i++) printf("%d ", hide[i]); cout << endl;