NP完全问题详解.ppt

1、a,1,第十二章 NP完全问题,12.1 P类和NP类问题 12.2 NP完全问题 12.3 co_NP类和NPI类问题,a,2,12.1 P类和NP类问题,12.1.1 P类问题 12.1.2 NP类问题,a,3,12.1.1 P类问题,a,4,12.1.1 P类问题,a,5,12.1.1 P类问题,a,6,12.1.1 P类问题,a,7,12.1.1 P类问题,a,8,12.1.1 P类问题,a,9,12.1.2 NP类问题,a,10,12.1.2 NP类问题,a,11,12.1.2 NP类问题,a,12,12.1.2 NP类问题,a,13,12.1.2 NP类问题,a,14,12.1.2

2、 NP类问题,a,15,12.2 NP完全问题,12.2.1 NP完全问题的定义 12.2.2 几个典型的NP完全问题 12.2.3 其他的NP完全问题,a,16,12.2.1 NP完全问题的定义,a,17,12.2.1 NP完全问题的定义2,a,18,a,19,a,20,12.2.2 几个典型的NP完全问题,12.2.2.1 可满足性问题（SATISFIABILITY） 12.2.2.2 三元可满足性问题（3_SATISFIABILITY） 12.2.2.3 图的着色问题（COLORING） 12.2.2.4 集团问题（CLIQUE） 12.2.2.5 顶点覆盖问题（VERTEX COVER

3、）,a,21,12.2.2.1 可满足性问题（SATISFIABILITY）,a,22,12.2.2.1 可满足性问题（SATISFIABILITY）,a,23,12.2.2.1 可满足性问题（SATISFIABILITY）,a,24,12.2.2.2 三元可满足性问题（3_SATISFIABILITY）,a,25,12.2.2.2 三元可满足性问题（3_SATISFIABILITY）,a,26,12.2.2.2 三元可满足性问题（3_SATISFIABILITY）,a,27,12.2.2.2 三元可满足性问题（3_SATISFIABILITY）,a,28,12.2.2.2 三元可满足性问题（

4、3_SATISFIABILITY）,a,29,12.2.2.3 图的着色问题（COLORING）,a,30,12.2.2.3 图的着色问题（COLORING）,a,31,12.2.2.3 图的着色问题（COLORING）,a,32,12.2.2.3 图的着色问题（COLORING）,a,33,12.2.2.3 图的着色问题（COLORING）,a,34,12.2.2.3 图的着色问题（COLORING）,a,35,12.2.2.4 集团问题（CLIQUE）,a,36,12.2.2.4 团问题（CLIQUE）,a,37,12.2.2.4 集团问题（CLIQUE）,a,38,12.2.2.4 集团

5、问题（CLIQUE）,a,39,12.2.2.4 集团问题（CLIQUE）,a,40,12.2.2.5 顶点覆盖问题（VERTEX COVER）,a,41,12.2.2.5 顶点覆盖问题（VERTEX COVER）,a,42,12.2.2.5 顶点覆盖问题（VERTEX COVER）,a,43,12.2.2.5 顶点覆盖问题（VERTEX COVER）,a,44,12.2.2.5 顶点覆盖问题（VERTEX COVER）,a,45,12.2.3 其他的NP完全问题,a,46,12.2.3 其他的NP完全问题,a,47,12.3 co_NP类和NPI类问题,a,48,12.3 co_NP类和NPI类问题,a,49,12.3 co_NP类和NPI类问题,a,50,12.3 co_NP