顶点覆盖问题

1. 顶点覆盖定义
2. 顶盖≤ρ clique
3. clique≤ρ顶点覆盖
4. 顶点覆盖ϵ NP

1）顶点覆盖：

定义：-它表示图G（V, E）中的一组顶点或节点, 从而提供了完整图的连通性

根据你创建的顶点覆盖的图形G, 顶点覆盖的大小= 2

2）顶点覆盖≤ρclique

在“顶点覆盖”图G中, 你有N个顶点, 其中包含一个“顶点覆盖”K。在其补语中必须存在大小为N-K的“派系大小”。

根据图G, 你拥有顶点数= 6的集团大小= N-K = 4

你也可以通过补充“顶点覆盖”图G来创建“派系”, 即以更简单的形式通过不存在边的边连接“顶点覆盖”图G中的顶点并删除所有存在的边

你将获得具有Clique Size = 4的图G

3）clique≤ρ顶点覆盖

在此过程中, 通过简化过程, 只需在多项式时间内对Clique图形G进行补充, 即可获得Clique的“顶点覆盖”形式。

4）顶点覆盖ϵ NP

众所周知, 你可以通过Clique获得“顶点覆盖”, 并将基于决策的NP问题转换为Clique, 首先必须将3CNF转换为SAT, 将3CNF转换为SAT, 然后将SAT转换为来自NP的CIRCUIT SAT。

NPC证明：

1. 从多项式到顶点覆盖率的缩减已在多项式时间内完成。以更简单的形式, 你可以在多项式时间内从Clique转换为Vertex Cover
2. 当将Vertex Cover转换为Clique并将Clique转换为3CNF并在多项式时间内也满足/验证输出时, 也已经进行了验证, 因此得出的结论是, 缩减和验证是在多项式时间内完成的, 这意味着Vertex Cover也可以使用人大