子集覆盖

证明：-

1. 子集覆盖
2. 顶点覆盖 ≤ρ 子集覆盖
3. 子集覆盖≤ρ 顶点覆盖
4. 子集覆盖 ϵ NP

1) 子集覆盖

定义： - 在获得完整图 G 的所有边的并集后，子集的边数，称为子集覆盖。

根据创建的图 G，子集覆盖的大小=2

2) 顶点覆盖 ≤ρ 子集覆盖

在具有 N 个顶点的图 G 中，如果存在大小为 k 的顶点覆盖，则也必须存在大小为 k 的子集覆盖。 如果您可以在多项式时间内从顶点覆盖到子集覆盖的规约，这意味着您做对了。

3) 子集覆盖 ≤ρ 顶点覆盖

为了验证输出，执行规约并创建团，并通过一个方程，N-K验证团，通过团可以快速生成3CNF，并在多项式时间内求解3CNF的布尔函数。 您将获得输出。 这意味着输出已得到验证。

4) 子集覆盖 ϵ NP:-

证明： - 众所周知，您可以通过顶点覆盖获得子集覆盖，并通过团获得顶点覆盖，要将基于决策的 NP 问题转换为团，首先您必须将其转换为3CNF，然后将3CNF转换为SAT，最后将SAT转换为电路SAT，这是来自 NP 的。

NPC 的证明：-

规约已在多项式时间内成功地从顶点覆盖到子集覆盖完成

输出也已在多项式时间内得到验证，正如您在上面的对话中所做的那样，因此，得出结论，子集覆盖也属于 NPC。

独立集

图 G = (V, E) 的独立集是顶点 V'⊆V 的一个子集，使得 E 中的每条边最多与 V' 中的一个顶点相连。独立集问题是找到 G 中最大大小的独立集。找到小的独立集并不难，例如，一个小的独立集是单个节点，但找到大的独立集很难。