图的边覆盖与边覆盖数

字数 2061 2025-12-12 01:24:08

图的边覆盖与边覆盖数

我们先从基本定义开始。
一个图 \(G=(V,E)\) 的 边覆盖 是指一个边子集 \(C \subseteq E\)，使得图中每个顶点都至少与 \(C\) 中的某条边关联（即覆盖所有顶点）。
边覆盖数 \(\beta'(G)\) 表示边覆盖的最小大小（最小边覆盖的边数）。

第一步：与匹配、顶点覆盖的对比
需要区分几个相关概念：

匹配：边子集，其中任意两边不共用顶点，目的是覆盖尽量多的顶点但不要求覆盖所有顶点。最大匹配记作 \(\alpha'(G)\)。
顶点覆盖：顶点子集，使得每条边至少有一个端点在该子集中。最小顶点覆盖大小记作 \(\beta(G)\)。
边覆盖：覆盖所有顶点的边集，最小大小是 \(\beta'(G)\)。

重要观察：如果图没有孤立顶点（度为 0 的顶点），那么边覆盖一定存在（比如用所有边 \(E\) 就是一种覆盖）。孤立顶点无法被任何边覆盖，所以有孤立顶点时边覆盖不存在，通常讨论时假设图无孤立点。

第二步：最小边覆盖的构造
已知定理（Gallai 定理的一部分）：对任意 \(n\) 个顶点且无孤立点的图，有

\[\alpha'(G) + \beta(G) = n \]

但和边覆盖数有关的另一个 Gallai 恒等式是：

\[\alpha'(G) + \beta'(G) = n \]

其中 \(\alpha'(G)\) 是最大匹配的边数，\(\beta'(G)\) 是最小边覆盖的边数。
这个公式揭示了匹配与边覆盖之间的对偶关系。

推导理解：

如果有一个最大匹配 \(M\)（大小为 \(\alpha'(G)\)），它覆盖了 \(2\alpha'(G)\) 个顶点。
未覆盖的顶点有 \(n - 2\alpha'(G)\) 个，每个这样的顶点必须用一条边去覆盖，并且这些边不能连接两个已匹配顶点（否则匹配可扩充，矛盾），所以可从每个未覆盖顶点任选一条邻边加入，这些新边之间、新边与匹配边之间可能有公共顶点，但没关系，我们仍能得到一个边覆盖。
这样总边数 = \(\alpha'(G) + (n - 2\alpha'(G)) = n - \alpha'(G)\)，所以 \(\beta'(G) \le n - \alpha'(G)\)。
反过来，从一个最小边覆盖 \(C\) 中可构造一个匹配：在 \(C\) 中删除一些边可得到匹配，可证明最优时等式成立，因此 \(\beta'(G) = n - \alpha'(G)\)。

这样，求最小边覆盖转化为求最大匹配（有高效算法），之后按上述方法扩展即可。

第三步：例子
考虑一个路径图 \(P_4\)：顶点 \(v_1-v_2-v_3-v_4\)。

最大匹配 \(M = \{v_1v_2, v_3v_4\}\) 大小 \(\alpha'=2\)，覆盖所有顶点，所以它本身已经是一个边覆盖，\(\beta' = 2\)。
公式：\(2 + 2 = 4\) 符合 \(n=4\)。

考虑一个三角形 \(C_3\)：

最大匹配 \(\alpha'=1\)（一个匹配只能取一条边，但也可取大小为 1 的匹配），未覆盖 1 个顶点，加一条边覆盖它，但加的那条边会覆盖两个顶点，其中一个是已覆盖的，于是总边数 = 2，即最小边覆盖可以是任意两条边，所以 \(\beta' = 2\)，公式 \(1+2=3\)。

第四步：算法与复杂度
因为 \(\beta'(G) = n - \alpha'(G)\)，所以只需用二分图或一般图的最大匹配算法（如开花算法、Hopcroft–Karp 算法等），得到最大匹配大小 \(k\)，则最小边覆盖大小 \(n-k\)，并且可在 \(O(|E| \sqrt{|V|})\) 或相应匹配算法复杂度内构造出来。

第五步：相关扩展概念

极小边覆盖（minimal edge covering）：去掉任一边后不再是边覆盖，但不一定最小。
如果图是二分图，König 定理给出 \(\alpha'(G) = \beta(G)\)，结合上面公式可得 \(\beta'(G) = n - \beta(G)\)，即最小边覆盖与最小顶点覆盖的大小之和为顶点数。
如果图有完美匹配（\(\alpha' = n/2\)），则 \(\beta' = n/2\)，并且完美匹配本身就是一个最小边覆盖。
加权版本：最小权边覆盖问题，也可通过转化为匹配问题或直接动态规划/整数规划求解，但比无权情况复杂。

第六步：总结核心
图的边覆盖与匹配之间由 Gallai 恒等式紧密联系，这让我们能用匹配算法高效解决最小边覆盖问题。这是图论中“覆盖-打包”对偶的经典例子之一，与顶点覆盖、匹配一起构成了图组合优化的基本要素。

图的边覆盖与边覆盖数我们先从基本定义开始。一个图 \( G=(V,E) \) 的边覆盖是指一个边子集 \( C \subseteq E \)，使得图中每个顶点都至少与 \( C \) 中的某条边关联（即覆盖所有顶点）。边覆盖数 \( \beta'(G) \) 表示边覆盖的最小大小（最小边覆盖的边数）。第一步：与匹配、顶点覆盖的对比需要区分几个相关概念：匹配：边子集，其中任意两边不共用顶点，目的是覆盖尽量多的顶点但不要求覆盖所有顶点。最大匹配记作 \( \alpha'(G) \)。顶点覆盖：顶点子集，使得每条边至少有一个端点在该子集中。最小顶点覆盖大小记作 \( \beta(G) \)。边覆盖：覆盖所有顶点的边集，最小大小是 \( \beta'(G) \)。重要观察：如果图没有孤立顶点（度为 0 的顶点），那么边覆盖一定存在（比如用所有边 \( E \) 就是一种覆盖）。孤立顶点无法被任何边覆盖，所以有孤立顶点时边覆盖不存在，通常讨论时假设图无孤立点。第二步：最小边覆盖的构造已知定理（Gallai 定理的一部分）：对任意 \( n \) 个顶点且无孤立点的图，有 \[ \alpha'(G) + \beta(G) = n \] 但和边覆盖数有关的另一个 Gallai 恒等式是： \[ \alpha'(G) + \beta'(G) = n \] 其中 \( \alpha'(G) \) 是最大匹配的边数，\( \beta'(G) \) 是最小边覆盖的边数。这个公式揭示了匹配与边覆盖之间的对偶关系。推导理解：如果有一个最大匹配 \( M \)（大小为 \( \alpha'(G) \)），它覆盖了 \( 2\alpha'(G) \) 个顶点。未覆盖的顶点有 \( n - 2\alpha'(G) \) 个，每个这样的顶点必须用一条边去覆盖，并且这些边不能连接两个已匹配顶点（否则匹配可扩充，矛盾），所以可从每个未覆盖顶点任选一条邻边加入，这些新边之间、新边与匹配边之间可能有公共顶点，但没关系，我们仍能得到一个边覆盖。这样总边数 = \( \alpha'(G) + (n - 2\alpha'(G)) = n - \alpha'(G) \)，所以 \( \beta'(G) \le n - \alpha'(G) \)。反过来，从一个最小边覆盖 \( C \) 中可构造一个匹配：在 \( C \) 中删除一些边可得到匹配，可证明最优时等式成立，因此 \( \beta'(G) = n - \alpha'(G) \)。这样，求最小边覆盖转化为求最大匹配（有高效算法），之后按上述方法扩展即可。第三步：例子考虑一个路径图 \( P_ 4 \)：顶点 \( v_ 1-v_ 2-v_ 3-v_ 4 \)。最大匹配 \( M = \{v_ 1v_ 2, v_ 3v_ 4\} \) 大小 \( \alpha'=2 \)，覆盖所有顶点，所以它本身已经是一个边覆盖，\( \beta' = 2 \)。公式：\( 2 + 2 = 4 \) 符合 \( n=4 \)。考虑一个三角形 \( C_ 3 \)：最大匹配 \( \alpha'=1 \)（一个匹配只能取一条边，但也可取大小为 1 的匹配），未覆盖 1 个顶点，加一条边覆盖它，但加的那条边会覆盖两个顶点，其中一个是已覆盖的，于是总边数 = 2，即最小边覆盖可以是任意两条边，所以 \( \beta' = 2 \)，公式 \( 1+2=3 \)。第四步：算法与复杂度因为 \( \beta'(G) = n - \alpha'(G) \)，所以只需用二分图或一般图的最大匹配算法（如开花算法、Hopcroft–Karp 算法等），得到最大匹配大小 \( k \)，则最小边覆盖大小 \( n-k \)，并且可在 \( O(|E| \sqrt{|V|}) \) 或相应匹配算法复杂度内构造出来。第五步：相关扩展概念极小边覆盖（minimal edge covering）：去掉任一边后不再是边覆盖，但不一定最小。如果图是二分图，König 定理给出 \( \alpha'(G) = \beta(G) \)，结合上面公式可得 \( \beta'(G) = n - \beta(G) \)，即最小边覆盖与最小顶点覆盖的大小之和为顶点数。如果图有完美匹配（\( \alpha' = n/2 \)），则 \( \beta' = n/2 \)，并且完美匹配本身就是一个最小边覆盖。加权版本：最小权边覆盖问题，也可通过转化为匹配问题或直接动态规划/整数规划求解，但比无权情况复杂。第六步：总结核心图的边覆盖与匹配之间由 Gallai 恒等式紧密联系，这让我们能用匹配算法高效解决最小边覆盖问题。这是图论中“覆盖-打包”对偶的经典例子之一，与顶点覆盖、匹配一起构成了图组合优化的基本要素。