第十二章NP完全问题ppt课件.ppt

《第十二章NP完全问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《第十二章NP完全问题ppt课件.ppt（53页珍藏版）》请在三一办公上搜索。

1、第十二章 NP完全问题,12.1 P类和NP类问题12.2 NP完全问题12.3 co_NP类和NPI类问题,12.1 P类和NP类问题,12.1.1 P类问题12.1.2 NP类问题,12.1.1 P类问题,12.1.1 P类问题,12.1.1 P类问题,12.1.1 P类问题,12.1.1 P类问题,12.1.1 P类问题,12.1.2 NP类问题,12.1.2 NP类问题,12.1.2 NP类问题,12.1.2 NP类问题,12.1.2 NP类问题,12.1.2 NP类问题,12.2 NP完全问题,12.2.1 NP完全问题的定义12.2.2 几个典型的NP完全问题12.2.3 其他的N

2、P完全问题,12.2.1 NP完全问题的定义,12.2.1 NP完全问题的定义,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）,12.2.2.1 可满足性问题（SATISFIABILITY）,12.2.2.1 可满足性问题（SATISFIABILITY）,12.2.2.1 可满足性问题（SATISFIABILITY）,12.

3、2.2.2 三元可满足性问题（3_SATISFIABILITY）,12.2.2.2 三元可满足性问题（3_SATISFIABILITY）,12.2.2.2 三元可满足性问题（3_SATISFIABILITY）,12.2.2.2 三元可满足性问题（3_SATISFIABILITY）,12.2.2.2 三元可满足性问题（3_SATISFIABILITY）,12.2.2.3 图的着色问题（COLORING）,12.2.2.3 图的着色问题（COLORING）,12.2.2.3 图的着色问题（COLORING）,12.2.2.3 图的着色问题（COLORING）,12.2.2.3 图的着色问题（COL

4、ORING）,12.2.2.3 图的着色问题（COLORING）,12.2.2.4 集团问题（CLIQUE）,12.2.2.4 团问题（CLIQUE）,12.2.2.4 集团问题（CLIQUE）,12.2.2.4 集团问题（CLIQUE）,12.2.2.4 集团问题（CLIQUE）,12.2.2.5 顶点覆盖问题（VERTEX COVER）,12.2.2.5 顶点覆盖问题（VERTEX COVER）,12.2.2.5 顶点覆盖问题（VERTEX COVER）,12.2.2.5 顶点覆盖问题（VERTEX COVER）,12.2.2.5 顶点覆盖问题（VERTEX COVER）,12.2.3 其他的NP完全问题,12.2.3 其他的NP完全问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,