点覆盖

习题预习

1. 给定一个图形，找出最小的点集合，使得图形中的每一条边都至少经过其中一个点。

2. 在一个无向图中，找到包含所有奇数度数节点的最小点集合。

3. 在一个有权重的无向图中，找到一个点集合，其权重之和最小，使得每一条边都至少经过其中一个点。

4. 在一个有向图中，找到一个点集合，使得每一条边的起始点或终止点都被包含，且点的数量最小。

5. 在一个二分图中，找到一个点集合，使得每一条边都至少经过其中一个点，且点的数量最小。

说明知识

Vertex Cover是一种图论中的问题，目的是找到一个最小的集合，可以覆盖一张无向图中所有的边。换句话说，就是找到一些点，让这些点所相连的边涵盖了整个图。

例如，下图中，有一个六个节点的无向图，其中的所有边都用虚线标记。如果要找到一个Vertex Cover，可以选择以下三个点：1、3和5。这三个点所连接的边（用实线表示）可以涵盖整个图中的所有边。

在这个例子中，这个Vertex Cover的大小为3，因为我们只需要三个节点就可以完全涵盖整个图了。Vertex Cover问题是一个NP完全问题，因此通常需要使用近似算法进行求解。

条列重点

1. Vertex Cover是一种图论问题，旨在找到最小的点集，使得该点集中的所有点都至少与一条边相邻。

2. Vertex Cover对于许多现实问题都有应用，例如电路板布线、城市交通网络设计等。

3. Vertex Cover问题属于NP完全问题，很难在多项式时间内找到最优解。

4. Vertex Cover问题有许多求解方法，包括暴力枚举、贪心算法、近似算法和各种精确算法。

5. 对于一个无向图G=(V,E)，其中V表示所有的顶点集合，E表示所有的边集合，一个点集C是V的一个子集，如果对于任意的(u,v)∈E，都有u∈C或v∈C，那么C称为G的一个点覆盖。

6. Vertex Cover问题的最小值可以用最小割问题转化求解。

7. 在实际应用中，Vertex Cover问题有时会被转化为其他问题求解，例如整数线性规划和布尔满足性问题。

8. Vertex Cover问题在计算机科学理论、算法和复杂性理论中都有广泛的应用，是研究和设计高效算法的重要题材之一。

知识测验

1. 假设你有一个无向图，每个节点都有一个权重。你的目标是找到一个最小的vertex cover，使得这些节点的权重总和最大。求最大权重总和。

答案：使用动态规划，令MCV(i)为图的前i个节点的最小vertex cover大小，W(i)为第i个节点的权重。则MCV(i)可表示为以下两种情况的较小值：

1. 第i个节点被选中，那么前i-2个节点就一定要成为vertex cover，所以MCV(i-2) + W(i)。

2. 第i个节点没有被选中，那么前i-1个节点就一定要成为vertex cover，所以MCV(i-1)。

3. 给定一个图，你需要从其中去掉k个节点，使得剩下的子图是一个独立集。求k的最小值。

答案：该问题等价于在原图上求最小vertex cover。可以用二分图匹配求解。

3. 给定一个无向图，每条边都有一个权重。求一个最小的vertex cover，使得所有边都至少有一个端点在vertex cover中。

答案：最小无权二分图匹配问题的变形，可以使用Konig定理转化为最大权二分图匹配问题。

4. 给定一个无向图，图中每个节点有颜色。求一个最小的vertex cover，使得每种颜色的节点至少有一个端点在vertex cover中。

答案：给每种颜色分别做出一个子图，然后对每个子图求一个最小完美匹配，最后将所有匹配的端点集合合并即可得到最小vertex cover。

5. 给定一个无向图，每个节点有一个预算和一个收入。你需要选择一个vertex cover，使得所有选中的节点的总预算不超过收入总和，并且收入总和最大。求最大收入。

答案：可以将问题转化为线性规划求解，令x_i为节点i是否被选中，则目标函数为max{c_ix_i}，约束条件为∑{b_ix_i}<=∑{b_i}，x_i∈{0,1}。使用整数规划技巧将x_i限制为整数，然后使用线性规划求解即可。