文章目录

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

一、独立集问题

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

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

独立集问题也是一个

完全问题 ;

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

证明一个命题是

完全问题 :

① 证明是

问题 : 首先证明该问题是

问题 ;

② 证明是最难的

问题 : 然后证明所有的

问题 , 可以在多项式时间内规约到 该命题中 ; 也可以使用一个已经证明的

完全问题 , 在多项式时间内规约到 需要被证明的命题 ;

证明 独立集题 是

完全的 , 从已知的

完全问题出发 , 已知的

完全问题就是 3-SAT 问题 ,

如果 3-SAT 问题是

完全的话 ,

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

独立集问题 ,

就可以证明 独立集问题 是

完全问题 ;

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

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

构造一个 无向图 ,

使得 布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个

独立集 ;

独立集就是无向图中

个节点子集 , 每两个节点之间都没有边相连 ;

证明过程 : 从 给定的 3-SAT 布尔逻辑公式

中 , 构造出一个无向图 出来 , 使得该无向图可以满足 " 布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个

独立集 "

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

任意给出一个

合取范式 ,

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

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

没有边相连 : 下图中

互相不为否定 , 三个点之间没有边相连 ;

没有边相连 : 下图中

互相不为否定 , 三个点之间没有边相连 ;

有边相连 : 下图中

有两个互相为否定 , 三个点之间有

条边相连 ;

有边相连 : 下图中

有两个互相为否定 , 三个点之间有

条边相连 ,

构造好的无向图 :

如果

布尔逻辑公式可满足 ,

当且仅当 ,

上述最终形成的无向图中 , 一定存在着一个

个节点组成的独立集 ;

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

那么

中取值为真的就是独立子集 ,

因此

是独立子集 ;

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

那么

中取值为真的就是独立子集 ,

因此 一个

两个

组成的点集 是独立子集 ;