最小与最小顶点覆盖

Question

我正在攻读考试,其中一个示例问题如下:

顶点覆盖:图形中的顶点覆盖是一组顶点,使得每个边缘在该集合中具有其两个端点中的至少一个.

最小顶点覆盖:图形中的MINIMUM顶点覆盖是顶点覆盖,其在所有可能的顶点覆盖中具有最小数量的顶点.

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

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

有人能解决这个问题吗？我没有看到两者之间的区别.更重要的是,我很难想象它.

我真的希望他不会在考试中问这样的奇怪问题!

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,你没有留下顶点覆盖.