证明顶点覆盖是 NP 完全的

引言

图论是数学中一个至关重要的领域，它是由表示对象之间成对关系的数值系统组成的。在图论中，存在许多问题，其中之一就是顶点覆盖问题。在计算机科学和组合优化中，顶点覆盖是一个经典问题，在网络和电路设计等许多领域都有应用。

顶点覆盖问题的定义如下：

给定一个无向图 G=(V, E)，确定一个最小的顶点子集 V' ⊆ V，使得 E 中的每条边都至少与 V' 中的一个顶点相关联。换句话说，它要求覆盖图中所有边所需的最少顶点数。

顶点覆盖属于 NP 问题

这基本上意味着我们可以高效地测试一个解（一个顶点覆盖）的正确性。要验证一个顶点覆盖，我们所要做的就是确保图中的每条边至少有一个端点在顶点覆盖集中。由于这种验证方法具有多项式时间性质，因此顶点覆盖是一个 NP 问题。

顶点覆盖是 NP-hard 问题

• 为了证明顶点覆盖是 NP-hard 问题，我们必须证明每个 NP 问题都可以在多项式时间内归约到它。我们通过将一个著名的 NP-complete 问题简化为顶点覆盖来实现这一点。
• 布尔可满足性问题 (SAT) 是最广为人知的 NP-complete 问题之一。在 SAT 问题中，我们的任务是确定是否存在一个布尔公式的赋值，为其变量赋上真值，以确保该公式为真。
• 我们在多项式时间内构建一个从 SAT 到顶点覆盖的归约。为给定的 SAT 实例创建相应图的过程如下：
• SAT 公式中的每个变量在图中都有两个顶点，分别代表该变量及其否定形式。
• SAT 公式中的每个子句的顶点连接起来，在图中形成一个大小为三的团（clique），或称完全子图，代表该子句中的文字（literal）。
• 通过构建这样的图，我们保证了 SAT 公式的一个可满足赋值对应于图中一个同样大小的顶点覆盖。反之，SAT 公式的可满足赋值对应于所构建图的任何一个顶点覆盖。

程序代码

输出

代码解释

• 常量和全局变量：定义图和已访问顶点的全局变量，并定义顶点和边的最大数量常量。
• initializeGraph(int vertices): 将访问过的数组和邻接矩阵设置为它们的初始值。
• addEdge(int u, int v): 向图中添加一条边。
• printVertexCover(int vertices): 打印顶点覆盖中的顶点。
• findVertexCover(int vertices, int edges): 使用贪心策略找到顶点覆盖。
• 图的初始化：设置访问过的数组和图。
• 输入边和顶点的数量，然后列出要添加的边。
• 定位并打印顶点覆盖：使用 findVertexCover 函数来定位并打印顶点覆盖。
• 作为示例输出，显示构成顶点覆盖的顶点。

结论

顶点覆盖问题是计算复杂性理论领域中复杂性和挑战性的最佳例证之一。由于其 NP-complete 性，它凸显了看似简单的图论问题在计算机科学及其他各种领域中的广泛影响。