哈密顿道路和Grbner基

通过应用多项式理想理论和Gr bner基方法 ,得出了判断简单图中是否存在哈密顿道路的一种新方法 ,该方法简单、易懂 。

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

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