计算机算法设计与分析 Chapter9计算机难解问题与NP 完全性.ppt

在非确定算法A的猜测阶段生成一个字符串S=C1C2.Cq在验证阶段把字符串S视为一个可能的着色方案即把S视为一个颜色序列把颜色Ci赋给顶点Vi(i=1.q)如果满足着色条件即相邻顶点不同色则返回true值算法的具体步骤为 1 检查q=n即S中应列出n个颜色可重复 2 检查S中的每个字符串是否在1.k之间否则不合格 3 检查输入串中的边对每条边(Vi,Vj)即(i,j)察看是否满足CiCj 如果三项