algorithm - 最小与最小顶点覆盖

Question

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

顶点覆盖：图中的顶点覆盖是一组顶点，使得每条边在这个集合中至少有它的两个端点中的一个。

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

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

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

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

我真的希望他在考试中不要问这种奇怪的问题！

Answer 1

考虑以下无向图：

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

顶点集合 {2,3,5,6,7} 是最小顶点覆盖。为什么？因为它是一个顶点覆盖并且 {2,3,5,6,7} 的任何非平凡子集都不是顶点覆盖。尝试从 {2,3,5,6,7} 中删除任何顶点，并查看是否留下未覆盖的边。使顶点覆盖最小的原因是无法减少它。你不能使集合比它已经小了，但仍然得到一个顶点覆盖（不向它插入顶点）。

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

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

Answer 2

考虑图表

A --- B --- C

B 是最小顶点覆盖。

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