提出反例说明贪心算法不是2-近似算法

假设以下列贪心思想解决最小顶点覆盖问题：重复选择度数最高的顶点，并去掉所有邻接边。给出一个例子，说明该贪心算法不是2-近似算法。

北京某高校算法课作业？（不会写菜鸡的路过）

近似算法的思想是，每次取一条边，两个点加入集合，并删除 两个点和关联的边，直到所有的边去掉。
比如你给的图可以先去掉z,u,删除 两个点和关联的边后再去掉y,x {z,u,y,x}是一个顶点覆盖

贪心算法之近似算法（格雷厄姆算法）初识
https://blog.csdn.net/xiaofengcanyuexj/article/details/17527533

Approx-TSP具有性能比2. 先序遍历解H删掉一条边, 就是一个过所有点的生成树, 而所有的生成树的边的总代价肯定都大于等于最小生成树MST, 所以有C(T)<=C(T')<=C(H).
再者, 先序遍历中如果不允许跨越的话, 直接严格在MST上走的路线W, 恰好是把最小生成树MST上的每条边走了两次, 因此C(W)=2C(T).
最后, C(W)>=C(H), 这是因为三角不等式被作为一个前提条件, 换句话说, 借助中间点没有两点直接连接的代价小.
综合看, 2C(T)>=C(H), 2C(H*)>=2C(T), --> 2C(H*)>=C(H), C(H)/C(H*) <= 2, 因此我们解的性能比值为2.

参见：问题求解 | 调度问题：2-近似的贪心算法与4/3-近似的LPT算法(https://zhuanlan.zhihu.com/p/493095021)