证明：-
- 子集和
- 顶点覆盖≤ρ子集覆盖
- 子集覆盖≤ρ顶点覆盖
- 子集和? NP
定义：-为获得并集而获得完整图形G的所有边之后的边子集数, 这称为子集覆盖。
根据图G, 你已经创建了Subset Cover = 2的大小
文章图片
v1{e1, e6}v2{e5, e2}v3{e2, e4, e6}v4{e1, e3, e5}v5{e4}v6{e3}
v3Uv4= {e1, e2, e3, e4, e5, e6} complete set of edges after the union of vertices.2）顶点覆盖≤ρ子集覆盖
在顶点N的图形G中, 如果存在大小为k的顶点覆盖, 则还必须存在大小为k的子集覆盖。如果你可以在多项式时间内从“顶点覆盖”减少为“子集覆盖”, 则表示你做对了。
3）子集覆盖≤ρ顶点覆盖
仅为了验证输出, 执行约简并创建Clique, 并且通过方程式, N-K也会验证Clique, 并且通过Clique你可以快速生成3CNF, 并在多项式时间内求解3CNF的布尔函数。你将获得输出。这表示输出已通过验证。
4）子机盖? NP：-
证明：-如你所知, 你可以通过“顶点覆盖”获得子集覆盖, 并通过“派系”获得“顶点覆盖”, 并将基于决策的NP问题转换为“派系”, 首先必须将3CNF和3CNF转换为SAT, 然后将SAT转换为CIRCUIT SAT来自NP。
NPC证明：
【子集和问题】已成功在多项式时间内从“顶点覆盖到子集覆盖”进行了约简
正如你在上述对话中所做的那样, 还已在多项式时间内验证了输出, 因此得出结论, SUBSET COVER也来自NPC。
独立套装 图G =（V, E）的独立集合是顶点的子集V’ ?V, 这样E中的每个边都入??射到V中的一个顶点上。独立集问题是在G中找到最大的独立集。找到小型独立集并不难, 例如, 小型独立集是一个单独的节点, 但是很难找到大型独立集。
文章图片
