algorithm - 图 G 具有大小为 |V| 的最小顶点覆盖。- 1 当且仅当 G 是完整的。这是真的吗？

Question

网格可以是完整 G 的示例。其中每个节点都连接到每个其他节点。因此，这种图的最小顶点覆盖大小不应该是“1”。

Answer 1

最小顶点覆盖是一组顶点，使得每条边都接触到集合中的一个顶点。给定一个 和 的网格（完整图）A B，C如果您只有一个节点（例如A）作为您尝试的 MVC，则您缺少一条边（在本例中为边B-C）。