要找到无向图 G 的最小支配集，您可以使用如下贪心算法：从空集 D 开始。直到 D 是支配集，添加一个具有最大未覆盖邻居数的顶点 v。
该算法一般不会找到最优解，它是一个 ln(Delta) 近似。（如果 Delta 是 G 中某个顶点的最大度数）
现在我正在寻找一个简单的例子，其中贪心算法找不到最优解。我发现的唯一一个是设置封面问题的相关实例。（http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm图片在右边）将这个转换为图形将导致至少 14 个顶点和很多边。
有谁知道一个小例子？
提前致谢
