图论中的支配集

在任何图中，图 G = (V, E) 的支配集 D 可以描述为 V 的一个子集，其选择方式是 D 之外的任何顶点都至少与 D 中的一个顶点相邻。换句话说，支配集可以描述为一组顶点，这些顶点用于覆盖图中的所有顶点，使得图中的每个顶点要么在支配集 D 中，要么至少与支配集 D 中的一个顶点相邻。

支配集可以用符号 D 表示。图中可以有不止一个支配集。如果集合 D ⊆ V 包含以下关系，则称其为 G 的支配集

现在我们通过一个例子来理解支配集，描述如下

上图 G 包含 8 个顶点和 13 条边。此图的支配集 {a, b, c} 描述如下

在此图中，每个蓝色顶点都至少与一个橙色顶点相邻。这也表明橙色顶点支配蓝色顶点。因此，{a, b, c} 是 G 的支配集。

图 G 还有另一个支配集，即 {g, h}，如上所示。在此图中，每个橙色顶点都至少与一个蓝色顶点相邻。因此，{g, h} 是 G 的支配集。

此示例也表明图中可以存在多个支配集。

支配数

图的支配数可以通过计算最小支配集中顶点的数量来计算。支配数可以用符号 γ(G) 表示。如果集合 S ⊆ V 包含以下关系，则称其为 G 的支配集

现在我们通过一个例子来理解支配数，如下所示

上图 G 包含 4 个顶点和 4 条边。上图有不止一个支配集，即 {V4, V3}、{V4, V2} 和 {V4, V1}。这里，我们展示了一个最小支配集，即 {V4, V3}

最小支配集包含 2 个顶点。因此，此图的支配数是 2，即 γ(G) = 2。

如果存在任意图，那么如果 G 的支配数低于给定整数，我们必须看看是否面临 NP-完全问题。在图论领域，没有算法可以在 多项式 时间内对所有类型的图执行此操作。尽管如此，图论包含一些有效的算法，通过这些算法我们可以近似支配数。

支配集的变体

在 图论 领域中，支配集有两种变体，如下所示

1. 连通支配集

如果我们可以在 D 的任意两个顶点之间找到一条仅通过 D 的路径，那么这种类型的集合称为连通支配集。我们可以通过一些例子来理解连通支配集，如下所示

示例 1

上图 G 包含 6 个顶点和 7 条边。在此图中，每个绿色顶点都至少与一个红色顶点相邻。因此，{2, 3} 是支配集。这个集合也是连通支配集，因为支配集 D 的两个顶点都通过一条仅通过集合 D 的路径连接。

示例 2

上图 G 包含 9 个顶点和 11 条边。在此图中，每个蓝色顶点都至少与一个红色顶点相邻。因此，{2, 5, 6, 7} 是支配集。这个集合也是连通支配集，因为支配集 D 的每个顶点都通过一条仅通过 D 的路径连接。

示例 3

上图 G 包含 6 个顶点和 7 条边。在此图中，每个蓝色顶点都至少与一个白色顶点相邻。因此，{1, 4, 6} 是支配集，但这个集合不是连通支配集，因为支配集 D 的顶点没有通过一条仅通过集合 D 的路径连接。需要覆盖更多 G 的顶点才能创建路径。

2. 全支配集

全支配集也称为强支配集，可以描述为一个集合，其中所有顶点必须至少在 D 中有一个邻居。换句话说，它也可以描述为一个集合，其中 G 的所有顶点以及 D 本身的顶点都必须在 D 中包含一个邻居。

全支配集不能存在于那些具有一个或多个顶点但没有边的图中。全支配集或强支配集可以用符号 γ^strong(G) 表示。我们可以通过一些例子来理解全支配集，如下所示

示例 1

上图 G 包含 9 个顶点和 11 条边。在此图中，每个蓝色顶点都至少与一个红色顶点相邻。因此，{1, 2, 6, 7} 是支配集 D。这个集合也是一个全支配集，因为 G 和 D 的所有顶点都在 D 中包含一个邻居。

示例 2

上图 G 包含 6 个顶点和 7 条边。在此图中，每个绿色顶点都至少与一个红色顶点相邻。因此，{3, 5} 是支配集。这个集合也是一个全支配集，因为 G 和 D 的所有顶点都在 D 中包含一个邻居。

支配集的应用

支配集有很多应用。例如，支配集可以用于自组织无线网络中的 路由协议。此应用程序主要用于计算设备网络中的支配集，该支配集可以进一步用于借助支配顶点路由用户消息。

因此，如果用户 X 需要向用户 Y 发送消息，在这种情况下，路由将计算 X 和 Y 的支配邻居之间的最短路径。通过这种方法，可以保证消息将发送给用户，因为所有设备都至少包含一个支配邻居。

支配集的示例

支配算法包含各种示例。一些示例如下所示

示例 1

此示例包含一个图。在这里，我们需要找到此图的支配集和支配数。

解：上图 G 包含 8 个顶点和 14 条边。此图的支配集如下所示

在此图中，每个红色顶点都至少与一个黑色顶点相邻。这也表明黑色顶点支配红色顶点。因此，{a, g, e} 是 G 的支配集。

支配集包含 3 个顶点。因此，此图的支配数是 3，即 γ(G) = 3。

示例 2

此示例包含一个图。在这里，我们需要找到此图的支配集和支配数。

解：上图 G 包含 10 个顶点和 15 条边。此图的支配集如下所示

在此图中，每个黄色顶点都至少与一个红色顶点相邻。这也表明红色顶点支配橙色顶点。因此，{z, vu, w} 是 G 的支配集。

支配集包含 3 个顶点。因此，此图的支配数是 3，即 γ(G) = 3。

示例 3

此示例包含一个图。在这里，我们需要找到此图的支配集和支配数。

解：上图 G 包含 9 个顶点和 11 条边。此图的支配集如下所示

在此图中，每个绿色顶点都至少与一个红色顶点相邻。这也表明红色顶点支配绿色顶点。因此，{2, 4, 7} 是 G 的支配集，如下所示

支配集包含 3 个顶点。因此，此图的支配数是 3，即 γ(G) = 3。

示例 4

此示例包含一个图。在这里，我们需要找到此图的支配集和支配数。

解：上图 G 包含 7 个顶点和 6 条边。此图的支配集如下所示

在此图中，每个绿色顶点都至少与一个红色顶点相邻。这也表明红色顶点支配绿色顶点。因此，{v1} 是 G 的支配集，如下所示

支配集包含 1 个顶点。因此，此图的支配数是 1，即 γ(G) = 1。

示例 5

此示例包含一个图。在这里，我们需要找到此图的支配集和支配数。

解：上图 G 包含 7 个顶点和 6 条边。此图的支配集如下所示

在此图中，每个蓝色顶点都至少与一个红色顶点相邻。这也表明红色顶点支配蓝色顶点。因此，{v1, v5} 是 G 的支配集，如下所示

支配集包含 2 个顶点。因此，此图的支配数是 2，即 γ(G) = 2。

示例 6

此示例包含一个图。在这里，我们需要找到此图的支配集和支配数。

解：上图 G 包含 8 个顶点和 8 条边。此图的支配集如下所示

在此图中，每个蓝色顶点都至少与一个红色顶点相邻。这也表明红色顶点支配蓝色顶点。因此，{v3, v4, v7, v8} 是 G 的支配集，如下所示

支配集包含 4 个顶点。因此，此图的支配数是 4，即 γ(G) = 4。