文章目录
一、独立集问题
二、独立集问题是 NP 完全问题证明思路
二、证明独立集问题是 NP 完全问题
一、独立集问题
----
无向图的独立集 , 指的是在无向图中找到点集的子集 , 使得它们两两之间..., 没有边相连 ;
下图中的无向图中 , 黄色的点集是独立集 ;
独立集问题也是一个
\rm NP
完全问题 ;
二、独立集问题是 NP 完全问题证明思路
----
证明一个命题是
\rm NP...该命题中 ; 也可以使用一个已经证明的
\rm NP
完全问题 , 在多项式时间内规约到 需要被证明的命题 ;
证明 独立集题 是
\rm NP
完全的 , 从已知的
\rm NP
完全问题出发..., 已知的
\rm NP
完全问题就是 3-SAT 问题 ,
如果 3-SAT 问题是
\rm NP
完全的话 ,
只要证明 3-SAT 问题 可以在 多项式时间内规约 到 独立集问题 中 ,...\lnot z
组成的点集 是独立子集 ;