表明顶点覆盖的启发式解最多是最优解的两倍
Show that the heuristic solution to vertex cover is at most twice as large as the optimal solution
我得到的启发式解决方案是：
- 对图执行深度优先搜索
- 删除所有叶子
- 剩下的图形成顶点覆盖
我的问题是："Show that this heuristic is at most twice as large as the optimal solution to the vertex cover"。我该如何显示？
坏消息：启发法不起作用。
严格来说，1 个孤立的顶点是问题的反例。
然而，启发式根本不提供顶点覆盖解决方案，即使您针对孤立顶点和 2 点团对其进行更正。
看一下顶点数从1到3的全连通图：
1 - 严格来说，孤立顶点不是叶子（它的度数为 0，而叶子是度数为 1 的顶点），因此启发式会保留它，而顶点覆盖不会
2 - 启发式将丢弃两片叶子，而顶点覆盖将至少保留其中的一片叶子
3 - 启发式将留下 1 个顶点，而顶点覆盖必须保留至少 2 个该团的顶点
我假设图是连通的（如果不是这样，我们可以针对每个组件分别解决这个问题）。
我还假设 dfs-tree 是有根的，叶子是在有根 dfs-tree 中没有子节点的顶点（这很重要。如果我们以不同的方式定义它，算法可能无法工作）。
我们需要展示的东西：
算法返回的顶点集合是顶点覆盖。事实上，在任何无向图的 dfs 树中只能有边的类型：树边（这样的边被覆盖，因为它的至少一个端点不是叶子）和后边（同样，它的端点之一不是叶子，因为后边从顶点到它的祖先。叶子不能是叶子的祖先）。
让我们考虑 dfs-tree 并忽略其余的边。我将展示使用少于一半的非离开顶点来覆盖树边是不可能的。令 S 为最小顶点覆盖。考虑一个顶点 v，使得 v 不是叶子并且 v 不在 S 中（即，v 由相关启发式返回但它不是最佳答案）。 v 不是叶子，因此 dfs-tree 中有一条边 v -> u（其中 u 是 v 的后继）。边 v -> u 被 S 覆盖。因此，u 在 S 中。让我们从不在 S 中的启发式返回的顶点定义映射 f 为 f(v) = u（其中 v 和 u 与前一句）。请注意，v 是 dfs 树中 u 的父级。但是一棵树中的任何顶点都只能有一个父节点！因此，f 是一个注入。这意味着启发式返回的集合中但不在最佳答案中的顶点数不大于最佳答案的大小。这正是我们需要展示的。
我得到的启发式解决方案是：
- 对图执行深度优先搜索
- 删除所有叶子
- 剩下的图形成顶点覆盖
我的问题是："Show that this heuristic is at most twice as large as the optimal solution to the vertex cover"。我该如何显示？
坏消息：启发法不起作用。 严格来说，1 个孤立的顶点是问题的反例。 然而，启发式根本不提供顶点覆盖解决方案，即使您针对孤立顶点和 2 点团对其进行更正。 看一下顶点数从1到3的全连通图：
1 - 严格来说，孤立顶点不是叶子（它的度数为 0，而叶子是度数为 1 的顶点），因此启发式会保留它，而顶点覆盖不会
2 - 启发式将丢弃两片叶子，而顶点覆盖将至少保留其中的一片叶子
3 - 启发式将留下 1 个顶点，而顶点覆盖必须保留至少 2 个该团的顶点
我假设图是连通的（如果不是这样，我们可以针对每个组件分别解决这个问题）。
我还假设 dfs-tree 是有根的，叶子是在有根 dfs-tree 中没有子节点的顶点（这很重要。如果我们以不同的方式定义它，算法可能无法工作）。
我们需要展示的东西：
算法返回的顶点集合是顶点覆盖。事实上，在任何无向图的 dfs 树中只能有边的类型：树边（这样的边被覆盖，因为它的至少一个端点不是叶子）和后边（同样，它的端点之一不是叶子，因为后边从顶点到它的祖先。叶子不能是叶子的祖先）。
让我们考虑 dfs-tree 并忽略其余的边。我将展示使用少于一半的非离开顶点来覆盖树边是不可能的。令 S 为最小顶点覆盖。考虑一个顶点
v，使得v不是叶子并且v不在S中（即，v由相关启发式返回但它不是最佳答案）。v不是叶子，因此 dfs-tree 中有一条边v -> u（其中u是v的后继）。边v -> u被S覆盖。因此，u在S中。让我们从不在S中的启发式返回的顶点定义映射f为f(v) = u（其中v和u与前一句）。请注意，v是 dfs 树中u的父级。但是一棵树中的任何顶点都只能有一个父节点！因此，f是一个注入。这意味着启发式返回的集合中但不在最佳答案中的顶点数不大于最佳答案的大小。这正是我们需要展示的。