【计算理论】计算复杂性 ( 无向图独立集问题 | 独立集问题是 NP 完全问题证明思路 | 证明独立集问题是 NP 完全问题 )

一、独立集问题

---

无向图的独立集 , 指的是在无向图中找到点集的子集 , 使得它们两两之间 , 没有边相连 ;

下图中的无向图中 , 黄色的点集是独立集 ;

独立集问题也是一个 $\mathrm{N}\mathrm{P}$ 完全问题 ;

二、独立集问题是 NP 完全问题证明思路

---

证明一个命题是 $\mathrm{N}\mathrm{P}$ 完全问题 :

① 证明是 $\mathrm{N}\mathrm{P}$ 问题 : 首先证明该问题是 $\mathrm{N}\mathrm{P}$ 问题 ;

② 证明是最难的 $\mathrm{N}\mathrm{P}$ 问题 : 然后证明所有的 $\mathrm{N}\mathrm{P}$ 问题 , 可以在多项式时间内规约到 该命题中 ; 也可以使用一个已经证明的 $\mathrm{N}\mathrm{P}$ 完全问题 , 在多项式时间内规约到 需要被证明的命题 ;

证明 独立集题 是 $\mathrm{N}\mathrm{P}$ 完全的 , 从已知的 $\mathrm{N}\mathrm{P}$ 完全问题出发 , 已知的 $\mathrm{N}\mathrm{P}$ 完全问题就是 3-SAT 问题 ,

如果 3-SAT 问题是 $\mathrm{N}\mathrm{P}$ 完全的话 ,

只要证明 3-SAT 问题 可以在 多项式时间内规约 到 独立集问题 中 , 3-SAT $\le$ 独立集问题 ,

就可以证明 独立集问题 是 $\mathrm{N}\mathrm{P}$ 完全问题 ;

将 3-SAT 问题 可以在 多项式时间内规约 到 独立集问题 中 ,

给定一个 3-SAT 问题 的 布尔逻辑公式 ,

$\varphi =(\mathrm{x}\vee \mathrm{y}\vee \neg \mathrm{z})\wedge (\neg \mathrm{x}\vee \neg \mathrm{y}\vee \mathrm{z})\wedge (\neg \mathrm{x}\vee \mathrm{y}\vee \neg \mathrm{z})$

构造一个 无向图 ,

使得 布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个 $\mathrm{k}$ 独立集 ;

$\mathrm{k}$ 独立集就是无向图中 $\mathrm{k}$ 个节点子集 , 每两个节点之间都没有边相连 ;

证明过程 : 从 给定的 3-SAT 布尔逻辑公式 $\varphi =(\mathrm{x}\vee \mathrm{y}\vee \neg \mathrm{z})\wedge (\neg \mathrm{x}\vee \neg \mathrm{y}\vee \mathrm{z})\wedge (\neg \mathrm{x}\vee \mathrm{y}\vee \neg \mathrm{z})$ 中 , 构造出一个无向图 出来 , 使得该无向图可以满足 " 布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个 $\mathrm{k}$ 独立集 "

二、证明独立集问题是 NP 完全问题

---

任意给出一个 $3$ 合取范式 ,

$\varphi =(\mathrm{x}\vee \mathrm{y}\vee \neg \mathrm{z})\wedge (\neg \mathrm{x}\vee \neg \mathrm{y}\vee \mathrm{z})\wedge (\neg \mathrm{x}\vee \mathrm{y}\vee \neg \mathrm{z})$

将上述公式转为无向图 : 合取范式每个子项 , 转换为三元组 , 如下图所示 ;

无向图构造原则 : 互为否定的点集 , 连接在一起 ,

没有边相连 : 下图中 $\mathrm{x},\neg \mathrm{y},\neg \mathrm{z}$ 互相不为否定 , 三个点之间没有边相连 ;

没有边相连 : 下图中 $\mathrm{y},\neg \mathrm{x},\neg \mathrm{x}$ 互相不为否定 , 三个点之间没有边相连 ;

有边相连 : 下图中 $\neg \mathrm{z},\mathrm{z},\neg \mathrm{z}$ 有两个互相为否定 , 三个点之间有 $2$ 条边相连 ;

有边相连 : 下图中 $\mathrm{x},\neg \mathrm{x},\neg \mathrm{x}$ 有两个互相为否定 , 三个点之间有 $2$ 条边相连 ,

构造好的无向图 :

如果 $\varphi =(\mathrm{x}\vee \mathrm{y}\vee \neg \mathrm{z})\wedge (\neg \mathrm{x}\vee \neg \mathrm{y}\vee \mathrm{z})\wedge (\neg \mathrm{x}\vee \mathrm{y}\vee \neg \mathrm{z})$ 布尔逻辑公式可满足 ,

当且仅当 ,

上述最终形成的无向图中 , 一定存在着一个 $3$ 个节点组成的独立集 ;

布尔逻辑公式中 , 给定一组真值 ,

$\mathrm{x}=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e},\mathrm{y}=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e},\mathrm{z}=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$

那么 $\mathrm{x},\mathrm{y},\mathrm{z},\neg \mathrm{x},\neg \mathrm{y},\neg \mathrm{z}$ 中取值为真的就是独立子集 ,

因此 $\mathrm{x},\mathrm{y},\mathrm{z}$ 是独立子集 ;

布尔逻辑公式中 , 给定一组真值 ,

$\mathrm{x}=\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e},\mathrm{y}=随意,\mathrm{z}=\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}$

那么 $\mathrm{x},\mathrm{y},\mathrm{z},\neg \mathrm{x},\neg \mathrm{y},\neg \mathrm{z}$ 中取值为真的就是独立子集 ,

因此 一个 $\neg \mathrm{x}$ 两个$\neg \mathrm{z}$ 组成的点集 是独立子集 ;