algorithm - 表明顶点覆盖的启发式解最多是最优解的两倍

Question

我得到的启发式解决方案是:

• 对图执行深度优先搜索
• 删除所有叶子
• 剩下的图形成一个顶点覆盖

有人问我这个问题:“证明这个启发式最多是顶点覆盖的最优解的两倍”。我怎样才能显示这个？

Answer 1

我假设图是连通的(如果不是这样，我们可以针对每个组件分别解决这个问题)。

我还假设 dfs-tree 是 Root过的，叶子是在有根 dfs-tree 中没有子节点的顶点(这很重要。如果我们以不同的方式定义它，算法可能无法工作)。

我们需要向事物展示:

1. 算法返回的顶点集是顶点覆盖。事实上，在任何无向图的 dfs 树中只能有边的类型:树边(这样的边被覆盖，因为它的至少一个端点不是叶子)和后边(同样，它的端点之一不是叶子，因为后边从顶点到它的祖先。叶子不能是叶子的祖先)。

2. 让我们考虑 dfs 树并忽略其余边。我将展示使用少于一半的非离开顶点来覆盖树边是不可能的。令 S 为最小顶点覆盖。考虑一个顶点 v , 这样 v不是叶子并且v不在 S 中(也就是说，v 由相关启发式返回，但它不在最佳答案中)。 v不是叶子，因此有一条边v -> u在 dfs 树中(其中 u 是 v 的后继者)。缘v -> u由 S 涵盖.因此，u在S .让我们定义一个映射 f来自不在 S 中的启发式返回的顶点作为f(v) = u (其中 v 和 u 与上一句中的含义相同)。注意 v是 u 的父级在 dfs 树中。但是一棵树中的任何顶点都只能有一个父节点!因此，f是注入(inject)剂。这意味着启发式返回的集合中但不在最佳答案中的顶点数不大于最佳答案的大小。这正是我们需要展示的。