覆盖

图 G 的图覆盖是指 G 的一个子图，它包含与某个其他图对应的所有顶点或所有边。

包含所有顶点的子图称为线/边覆盖。 包含所有边的子图称为顶点覆盖。

1. 边覆盖

覆盖图 G 的所有顶点的边集称为 G 的线覆盖或边覆盖。

当且仅当 G 具有孤立顶点时，边覆盖不存在。

具有 n 个顶点的图 G 的边覆盖至少有 n/2 条边。

示例

在上图中，红色边表示图中边覆盖的边。

最小线覆盖

如果不能从 M 中删除任何边，则称图 G 的线覆盖 M 为最小线覆盖。

或者，最小边覆盖是图 G 的一个边覆盖，它不是任何其他边覆盖的真子集。

没有最小线覆盖包含循环。

示例

从上图中，具有边覆盖的子图是

M1 = {{a, b}, {c, d}}
M2 = {{a, d}, {b, c}}
M3 = {{a, b}, {b, c}, {b, d}}
M4 = {{a, b}, {b, c}, {c, d}}

这里，M₁、M₂、M₃ 是最小线覆盖，但 M₄ 不是，因为我们可以删除 {b, c}。

最小线覆盖

具有最少边的最小线覆盖称为图 G 的最小线覆盖。它也称为最小最小线覆盖。

每个最小边覆盖都是一个最小边覆盖，但反之则不一定成立。

G 中最小线覆盖中的边数称为 G 的线覆盖数，用 α₁ 表示。

示例

从上图中，具有边覆盖的子图是

M1 = {{a, b}, {c, d}}
M2 = {{a, d}, {b, c}}
M3 = {{a, b}, {b, c}, {b, d}}
M4 = {{a, b}, {b, c}, {c, d}}

在上面的例子中，M₁ 和 M₂ 是 G 的最小边覆盖，且 α₁ = 2。

2. 顶点覆盖

覆盖图 G 的所有节点/顶点的顶点集称为 G 的顶点覆盖。

示例

在上面的例子中，每个红色的顶点都是图的顶点覆盖。 这里，每个图中所有红色顶点的集合都触及图中的每条边。

最小顶点覆盖

如果不能从 M 中删除任何顶点，则称图 G 的顶点 M 为最小顶点覆盖。

示例

可以从上图中派生的子图是

M1 = {b, c}
M2 = {a, b, c}
M3 = {b, c, d}

这里，M₁ 和 M₂ 是最小顶点覆盖，但在 M₃ 中，顶点 'd' 可以被删除。

最小顶点覆盖

当图 G 中覆盖的顶点数最少时，称为最小顶点覆盖。 它也称为最小最小顶点覆盖。

图 G 中最小顶点覆盖中顶点数称为 G 的顶点覆盖数，用 α₂ 表示。

示例 1

在上图中，最小顶点覆盖中的顶点为红色。

α₂ = 3，对于第一个图。

并且 α₂ = 4，对于第二个图。

示例 2

可以从上图中派生的子图是

M1 = {b, c}
M2 = {a, b, c}
M3 = {b, c, d}

这里，M1 是 G 的最小顶点覆盖，因为它只有两个顶点。 因此，α₂ = 2。