NPC问题中几个基本定理的证明  

作　　者：郭蕾[1] 

机构地区：[1]常州纺织服装职业技术学院信息技术系,江苏常州213164

出　　处：《长江大学学报（自然科学版）》2011年第12期19-21,共3页Journal of Yangtze University(Natural Science Edition)

摘　　要：就NPC问题(NP-complete,NP完全问题)中的几个基本定理给出了证明。首先从基本的团问题、SAT问题和图的着色问题入手,证明了它们都属于NPC问题,再利用独立集、顶点覆盖、有向图、团、SAT和图的着色等问题本身的内在关系,对其他的定理做了一一证明。

关 键 词：NPC问题 SAT 着色 独立集 顶点覆盖 有向图 无向图 哈密顿道路 回路 

分 类 号：O157.5[理学—数学]