最小与最小顶点覆盖

Question

我正在准备考试，其中一个示例问题如下：

顶点覆盖：图中的顶点覆盖是一组顶点，其中每条边至少有一个在该组中的两个端点。

最小顶点覆盖：图中的最小顶点覆盖是所有可能的顶点覆盖中具有最少顶点数的顶点覆盖。

最小顶点覆盖图中的最小顶点覆盖是不包含另一个顶点覆盖的顶点覆盖（从集合中删除任何顶点将创建一组不是顶点覆盖的顶点）

问题：最小顶点覆盖不是始终是最小顶点覆盖。用一个简单的例子来证明这一点。

任何人都可以解决这个问题吗？我看不出两者之间的区别。更重要的是，我很难想象它。

我真心希望他不会在考试时问出像这样的奇怪问题！

Answer 1

考虑以下无向图：

顶点集 {2,4,5} 是以下的最小顶点覆盖图表。为什么？因为它是一个顶点覆盖（所有边都被覆盖）并且没有其他顶点覆盖更少的顶点。

顶点集 {2,3,5,6,7} 是最小值 顶点覆盖。为什么？因为它是顶点覆盖，并且 {2,3,5,6,7} 的任何非平凡子集都不是顶点覆盖。尝试从 {2,3,5,6,7} 中删除任何顶点，看看是否留下了未被覆盖的边。顶点覆盖最小化的原因是无法减少它。您无法使集合比现有的更小，但仍然可以获得顶点覆盖（而不向其插入顶点）。

显然，给定的最小顶点覆盖不是最小顶点覆盖，因为最小顶点覆盖具有三个顶点，并且我们的最小顶点覆盖有 5 个顶点。因此，并非每个最小顶点覆盖也是最小顶点覆盖。

每个最小顶点覆盖也是最小顶点覆盖，因为从最小顶点覆盖中移除顶点将产生尺寸小于最小覆盖的顶点集。因此，最小顶点覆盖的任何非平凡子集都不是顶点覆盖，因此最小顶点覆盖也是最小的。

Answer 2

考虑图

A --- B --- C

B 是最小顶点覆盖。

A,C 是最小顶点覆盖。删除 A 或 C，就不会留下顶点覆盖。