顶点覆盖与主导集合

Question

我试图理解顶点覆盖和支配集之间的区别.

根据理解,在支配集中,集合D包含与不在D中的其他顶点相邻的顶点(对于V中的每个v,v在D中或者在D中与1相邻).

在顶点覆盖中,D中的所有顶点都覆盖了所有边缘,但是通过这样做,它们与其他顶点相邻,它们不在D中 - 那么为什么它不是一个支配集？

Answer 1

我在维基百科的Dominating Set文章中找到了一些图表来说明这种差异.

这些示例显示了不是顶点覆盖的主导集(红色),与您稍后在问题中提到的相反.(VD)中的边缘可防止它们成为顶点覆盖.

Answer 2

以前的答案很好但是最简单的例子还没有写在这里:

Answer 3

我无法很快从给定的答案中理解顶点覆盖和支配集之间的区别，所以我查了一下。

定义顶点覆盖：

根据维基百科：

“图的顶点覆盖是一组顶点，其中包括图的每条边的至少一个端点。”

因此，简单来说，对于每条线，2 个点/节点中的 1 个（连接到线的末端）必须位于点/节点集中。

定义支配集：

根据维基百科：

图 G = (V, E) 的支配集是 V 的子集 D，使得不在 D 中的每个顶点都与 D 的至少一个成员相邻。

简而言之：所有点/节点必须位于（点/节点）集合中，或者通过单条线/边连接到该集合。

给定示例的解释

这就是为什么在@Daniel 给出的示例中：

每2个节点就是一个顶点覆盖，单个节点不能是顶点覆盖，因为这样与所选节点相对的线不具有“顶点覆盖集中至少有1个节点”。

差异可视化

区别如下图所示：

然而，1 个节点是一个支配集，因为在这种情况下，所有节点要么：在该集中，要么通过 1 条线连接到该集。（这里的 1 条线是距离方面的，如果有 2 条线并联连接到主导集，也可能完全没问题，只要它不仅仅是串联/在彼此后面的 2 条线连接到主导集） 。

下面添加了一个示例来直观地说明为什么单个节点是 3 个节点中的支配集：

Answer 4

1. 如果顶点覆盖之外有一个零度顶点，则顶点覆盖可能不是支配集。顶点覆盖“覆盖”了所有边，但度数为零的顶点不与顶点覆盖相邻。

2. 如果存在边，例如 e = (u,v)，其中 u 和 v 都在支配集之外，则支配集可能不是顶点覆盖。这是可能的，如果 u 和 v 都与其他边的支配集中的顶点相邻。