- 顶点覆盖定义
- 顶盖≤ρ clique
- clique≤ρ顶点覆盖
- 顶点覆盖? NP
定义：-它表示图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证明：
- 从多项式到顶点覆盖率的缩减已在多项式时间内完成。以更简单的形式, 你可以在多项式时间内从Clique转换为Vertex Cover
- 当将Vertex Cover转换为Clique并将Clique转换为3CNF并在多项式时间内也满足/验证输出时, 也已经进行了验证, 因此得出的结论是, 缩减和验证是在多项式时间内完成的, 这意味着Vertex Cover也可以使用人大
