我试图了解顶点覆盖和支配集之间的区别。
据了解，在支配集合中，集合 D 包含与不在 D 中的其他顶点相邻的顶点（对于 V 中的每个 v，v 要么在 D 中，要么与 D 中的一个相邻）。
在顶点覆盖中，D 中的所有顶点都覆盖了所有边，但是这样做它们与其他顶点相邻，它们不在 D 中 - 那么为什么它不是一个支配集呢？
问问题
20621 次
9 回答
38
我在 Wikipedia 的 Domination Set 文章中找到了一些图表来说明这种差异。
这些示例显示了不是顶点覆盖的主导集（红色），与您稍后在问题中提出的相反。(VD) 中的边防止它们成为顶点覆盖。
于 2013-01-30T00:52:21.947 回答
36
以前的答案很好，但是最简单的例子还没有写在这里，所以：
于 2016-01-28T14:56:16.237 回答
6
我不能很快地从给定的答案中理解顶点覆盖和支配集之间的区别，所以我查了一下。
定义顶点覆盖：
“图的顶点覆盖是一组顶点，包括图的每条边的至少一个端点。”
因此，简单来说，对于每一行，2 个点/节点中的 1 个（连接到线的末端）必须在点/节点的集合中。
定义支配集：
图 G = (V, E) 的支配集是 V 的子集 D，使得不在 D 中的每个顶点都与 D 的至少一个成员相邻。
简而言之：所有点/节点必须在（点/节点的）集合中，或者通过单条线/边连接到集合。
给定示例的解释
这就是为什么在@Daniel 给出的示例中：
每2个节点是一个顶点覆盖，单个节点不能是一个顶点覆盖，因为与所选节点相对的线没有“顶点覆盖集中至少1个节点”。
差异的可视化
区别如下图所示：
然而，1 个节点是一个支配集，因为在这种情况下，所有节点要么：在集合中，要么通过 1 条线连接到集合。（这里的 1 条线是距离明智的，如果有 2 条线并联连接到主导集，也可以很好，只要它不仅仅是 2 条串联/彼此后面的线，连接到主导集） .
下面添加了一个示例来可视化为什么单个节点是 3 个节点中的支配集：
于 2020-03-28T20:05:48.310 回答
5
如果您在顶点覆盖之外有零度顶点，则顶点覆盖可能不是支配集。顶点覆盖“覆盖”所有边，但零度顶点不与顶点覆盖相邻。
如果存在边，例如 e = (u,v)，则支配集可能不是顶点覆盖，其中 u 和 v 都在支配集之外。这是可能的，如果 u 和 v 都与其他边的支配集中的顶点相邻。
于 2013-12-28T21:26:34.527 回答
3
您只需要考虑四个顶点上的路径即可区分这两个概念。设 a,b,c,d 是这样一条路径的连续顶点。那么 {a,d} 是一个支配集，但不是一个顶点覆盖（因为它不能覆盖边 bc）。
于 2013-11-08T21:59:40.930 回答
1
每个顶点覆盖都是一个支配集，但反之则不然。例如，如果你有一个图 G=(V,E) G={a,b,c,d,e} 和 E={(a,b),(b,c),(c,d),( e,a),(e,b)}，则支配集 DS={b,e} 不是 G 的顶点覆盖。边 (c,d) 没有被覆盖。
于 2013-12-04T17:39:10.983 回答
0
对于连通图，顶点覆盖必须是支配集。对于孤立节点，您需要将其包含在支配集中，但不需要将其包含在顶点覆盖中。但是，支配集是更大的类，它们不必是顶点覆盖，如本回复中的示例所示。
于 2016-05-16T19:02:23.190 回答
0
我认为主要区别在于顶点覆盖，边缘必须在顶点覆盖集中至少有一个端点。然而，对于支配集，它满足当一个节点要么在集中，要么它的直接邻居在集中，因此有可能边的两个端点都不在集中（只有当它们都在集中时才会发生）连接到集合中的节点）。希望这能澄清一点。
于 2018-11-05T16:14:37.653 回答
0
顶点覆盖：您可以将它们视为关注任何通道（边缘）的策略。这样，他们可以关注除孤立节点之外的任何节点，因为节点不是他们关心的问题。它们必须涵盖所有段落。
支配集：这些是关注任何节点的策略。通道并不重要，因此如果其中一个通过边监视节点，则连接到该节点的其他边可能不会被覆盖，因为通道不是这些策略的关注点。
于 2018-12-02T19:33:19.967 回答